Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.
Definition µ-Rekursion
Hab nirgendwo eine gescheite Definition zur µ-Rekursion gefunden bzw auch keine Aufgaben dazu?
Könnte man das so definieren:
µ-Rekursion ist die um den µ-Operator erweiterte primitive Rekursion, mit dem sich die kleinste Nullstelle der Funktion feststellen lässt.
Stimmt das ungefähr, oder isses falsch? Kam eigentlich jemals µ-Rekursion (außer, dass mans definieren sollte) in ner Klausur dran?
naja… so stimmts net ganz. Der Punkt ist, dass primitiv-rekursive Funktionen TOTAL sind, dass heisst sie sind für ganz N[SUB]0[/SUB] definiert. Es gibt nun aber Funktionen, die nicht für jede Eingabe definiert sind, z.B. eben log oder quotient oder ähnliches. Um zu beweisen, dass die AUCH berechenbar sind, brauchst du ein etwas anderes Schema, eben das mit dem µ-Operator.
Zu den berechenbaren Funktionen gehörten somit alle, bei denen sich die Berechenbarkeit entweder mit prim-Rekursion ODER mit µ-Rekursion beweisen lässt!
Ich hoff dass meine Auffassung korrekt ist… Garantie übernehm´ ich aber keine! :-p
Falls du eine genaue Definition von y-Rekursion brauchst: Auf dem Loesungsvorschlag zum Uebungsblatt 9 ist das finde ich ganz gut erklaert. Vor allem ist es kurz . Aber im rest, stimme ich tsunami zu.
fredator