Was ist My Rekursion

Hallo Forum,

ich habe die My-Rekursion nicht ganz verstanden. Könntet Ihr mir helfen?
Nehmen wir als Grundlage diesen Artikel: http://de.wikipedia.org/wiki/M-Rekursion

1. Was soll passieren wenn ich den my Operator auf eine Funktion anwende? (Siehe Definition im Wiki)
1a) Ich habe f(x)=y. Wobei x ein Parameter darstellt und keinen Tupel. Mit dem My Operator müsste sich die Dimension des Tupels um eins verringern, was aber nicht geht. Kann ich My nur auf Fkt mit 2 oder mehr parametern anwenden?

1b) Wenn ich also f(x1, x2) habe und wende My an:
Dann ist das Ergebnis von My_f(x2) = {
Die Menge aller Werte für x2 auf die die folgenden Bedingungen zutreffen:
- f(x1, x2) muß 0 sein
- f(x1 + i,x2) muß für alle i definiert sein.
}
Kann mir jemand erklären was das soll? Wenn mir jemand einen SortierAlgo gibt schreibt er im Vorwort das das Ziel sortieren sei...

2. Zu dem zweiten Definitionsabschnitt im Wiki Artikel:
Die Grundfunktionen sind mir klar. Wie bei Primitiv Rekursiv...
Die anderen kann ich im mathematischen Sinne korrekt lesen. Aber was soll das?

3. Gibt es vielleicht einen anderen Namen für My-Rekursion, so dass ich im Internet nachschlagen könnte?

4. Das ist ein Beispiel für primitive Rekursion:
Fakultät(n+1) = Fakultät(n)*(n+1)
Fakultät(1) = 1
Könnte jemand ein Beispiel für My-Rekursion posten?

Vielen Dank

Andreas

CStoll

1. Ja, µ-Rekursion macht nur Sinn für mehrstellige Funktionen. Und dann liefert µf(x2) den kleinsten Wert x1, für den (a) f(x1,x2)=0 und (b) f(x',x2) ist definiert für alle Werte x'<x1.

2. Du kannst alle µ-rekursiven Funktionen erzeugen, indem du von den Basisfunktionen ausgehst und sie per Komposition, (normaler) primitiver Rekursion und µ-Rekursion (siehe 1) kombinierst. Und die µ-rekursiven Funktionen sind genau die turing-berechenbaren Funktionen, also letzlich alles, was ein Computer berechnen kann.

4. Etwas weiter unten in dem von dir verlinkten Artikel sind auch einige Beispiele für µ-rekursive Funktionen angegeben (OK, die meisten dieser Beispiele sind eher theoretischer Natur).