Ich versteh die einfach nicht, die µ-rekursiven Funktionen.

µ-rekursive bzw. partiell rekursive Funktionen sind mächtiger als primitive Rekursion. Man kann nun partielle Funktionen berechnen wobei µ-Rekursion die Mächtigkeit von While-Schleifen hat (im Gegensatz zu primitiv-rekursiven Funktionen die lediglich die Mächtigkeit einer Programmierung mit For-Schleifen haben).

Die Menge der µ-rekursiven Funktionen erhält man durch eine Erweiterung der Menge der primitiv-rekursiven Funktionen mit dem µ-Operator.


Wofür es da ist, ist klar. Aber wie funktioniert es? Und was genau macht der µ-Operator? Die eher kryptische Definition

[img]http://blackspell.de/files/livejournal/m-rekursion.png[/img]

habe ich mir mittlerweile schon oft genug durchgelesen und auch Google habe ich schon des öfteren gefragt… aber dennoch verschließt sich mir der Sinn (oder eher die Funktionsweise) des Ganzen. Auch die Ackermann-Funktion ist mir ein Rätsel.

Könnte das hier nicht bitte irgendwer halbwegs verständlich erklären?

Unter

http://3773.rapidforum.com/topic=101680110758&startid=#168011075820244556

habe ich das schonmal zu erklären versucht.
Falls dir das nicht weiterhilft, kannst du
ja nochmal fragen.

Wenn ich es richtig gelesen habe, funktioniert das Ganze so:

Aus einer Ausgangsfunktion f mit r Argumenten entsteht durch Anwendung des µ-Operators eine Funktion [img]http://mokrates.de/cgi-bin/texstring?%5Cpsi[/img] mit r-1 Argumenten.

Aus [img]http://mokrates.de/cgi-bin/texstring?f(x_1%2C%5Cldots%2Cx_%7Br%7D)[/img] wird [img]http://mokrates.de/cgi-bin/texstring?%5Cpsi(x_1%2C%5Cldots%2Cx_%7Br-1%7D)[/img]. Und diese Funktion [img]http://mokrates.de/cgi-bin/texstring?%5Cpsi[/img] berechnet nun ein y mit dem [img]http://mokrates.de/cgi-bin/texstring?f(x_1%2C%5Cldots%2Cx_%7Br-1%7D%2Cy)%3D0[/img], sofern [img]http://mokrates.de/cgi-bin/texstring?f(x_1%2C%5Cldots%2Cx_%7Br-1%7D%2Cx)[/img] für alle x < y definiert ist.


Warum sagt man eigentlich "durch Anwendung des µ-Operators". Ein µ-Operator kommt doch eigentlich niemals vor, oder?

Wie auch immer. Wenn ich eine Funktion [img]http://mokrates.de/cgi-bin/texstring?g(x_1%2Cx_2)[/img] hätte mit

g(1,0) = 2
g(1,1) = 1
g(1,2) = 0,

dann wäre nach Anwendung des µ-Operators die Psi-Funktion [img]http://mokrates.de/cgi-bin/texstring?%5Cpsi(1)%3D2[/img], da damit g(1,y) bzw. g(1,psi(1)) = 0…

Und wäre jetzt g(1,1) nicht definiert, gäbe es kein Ergebnis. Oder etwa nicht? Und ist das alles?

Aus [img]http://mokrates.de/cgi-bin/texstring?f(x_1%2C%5Cldots%2Cx_%7Br%7D)[/img] wird [img]http://mokrates.de/cgi-bin/texstring?%5Cpsi(x_1%2C%5Cldots%2Cx_%7Br-1%7D)[/img]. Und diese Funktion [img]http://mokrates.de/cgi-bin/texstring?%5Cpsi[/img] berechnet nun ein y mit dem [img]http://mokrates.de/cgi-bin/texstring?f(x_1%2C%5Cldots%2Cx_%7Br-1%7D%2Cy)%3D0[/img], sofern [img]http://mokrates.de/cgi-bin/texstring?f(x_1%2C%5Cldots%2Cx_%7Br-1%7D%2Cx)[/img] für alle x < y definiert ist.

Ja, und zwar das kleinste solche y.

Warum sagt man eigentlich "durch Anwendung des µ-Operators".
Ein µ-Operator kommt doch eigentlich niemals vor, oder?

Man schreibt dann [img]http://mokrates.de/cgi-bin/texstring?%5Cpsi%3D%5Cmu%20f[/img].

Wie auch immer. Wenn ich eine Funktion [img]http://mokrates.de/cgi-bin/texstring?g(x_1%2Cx_2)[/img] hätte mit

g(1,0) = 2
g(1,1) = 1
g(1,2) = 0,

dann wäre nach Anwendung des µ-Operators die Psi-Funktion psi(1)=2,
da damit g(1,y) bzw. g(1,psi(1)) = 0…

Ganz genau.

Und wäre jetzt g(1,1) nicht definiert, gäbe es kein Ergebnis.

Richtig. "Gäbe es kein Ergebnis" heißt genauer: psi(1)
wäre nicht definiert. Weil es dann keine Nullstelle gibt, sodass
[img]http://mokrates.de/cgi-bin/texstring?g(1%2C%5Ccdot)[/img] auf allen kleineren Werten definiert ist.

Und ist das alles?

Man könnte noch erwähnen, dass psi(1)
auch dann nicht definiert wäre, wenn
z.B. g(1,2)=0 und g(1,1)=undefiniert
wäre.

Mich interessiert auch der µ-Operators, ich versteh die Beispielaufgabe nicht ganz…

Wie auch immer. Wenn ich eine Funktion [img]http://mokrates.de/cgi-bin/texstring?g(x_1%2Cx_2)[/img] hätte mit

g(1,0) = 2
g(1,1) = 1
g(1,2) = 0,

dann wäre nach Anwendung des µ-Operators die Psi-Funktion [img]http://mokrates.de/cgi-bin/texstring?%5Cpsi(1)%3D2[/img], da damit g(1,y) bzw. g(1,psi(1)) = 0…

Und wäre jetzt g(1,1) nicht definiert, gäbe es kein Ergebnis. Oder etwa nicht? Und ist das alles?

[img]http://mokrates.de/cgi-bin/texstring?%5Cpsi(1)%3D2[/img] kommt doch zustande, weil bei g(1,0) = 2 das zweite Argument (die 0) "wegfällt", oder? Die 'Begründung': "da damit g(1,y) bzw. g(1,psi(1)) = 0…" aber versteh ich nicht… bzw. wie findet man das y mit f(arg_1,..,arg_n-1) = 0 ?

Ich weiss das alles hier ist ein alter Thread, denke aber dass ich kein neues Thema deswegen aufmachen sollte…

Mich interessiert auch der µ-Operators, ich versteh die Beispielaufgabe nicht ganz…

[img]http://mokrates.de/cgi-bin/texstring?%5Cpsi(1)%3D2[/img] kommt doch zustande, weil bei g(1,0) = 2 das zweite Argument (die 0) "wegfällt", oder? Die 'Begründung': "da damit g(1,y) bzw. g(1,psi(1)) = 0…" aber versteh ich nicht… bzw. wie findet man das y mit f(arg_1,..,arg_n-1) = 0 ?

Ich weiss das alles hier ist ein alter Thread, denke aber dass ich kein neues Thema deswegen aufmachen sollte…

Achtung, der µ-Operator setzt nicht
in der letzten Argumentstelle 0 ein!

Hast du das und das hier schon gelesen?
Wenn dir das nicht weiterhilft, kannst du ja
nochmal fragen. [img]http://www.fb18.de/gfx/23.gif[/img]