[ Inhalt ] [ Index ]

-rekursive Funktionen

Wenn wir z.B. das Prädikat x teilt y betrachten, können wir x festhalten und fragen: Welches ist das kleinste y, daß von x geteilt wird?

So erhalten wir eine Funktion, die jedem x das kleinste y zuordnet, das von x geteilt wird. (Nicht besonders interessant, aber wir werden sehen...)

Dieses Minimum-Problem kann man auch in C formulieren:

y = 0;
while(!p(x,y)) y++;

Seltsamerweise kann man dies mit Hilfe primitiv rekursiver Funktionen nicht formulieren.

Die Schleife liefert das erste ab, für das das Prädikat p(x,y) wahr wird, also die charakteristische Funktion f(x,y) den Wert 0 liefert.

Man beachte, daß f(x,y) für alle Werte definiert sein muß.

Definition: (unbeschränkter -Operator)
Sei P ein (n+1)-stelliges Prädikat und existiere zu ein eindeutiges, kleinstes y mit true, dann bezeichnen wir dieses y mit

ist der unbeschränkte -Operator.   

Falls ein solches y nicht existiert, definieren wir

Zu diesem Prädikat definieren wir f wie folgt:

Wenn P entscheidbar ist und ein solches y existiert, ist f Turing-berechenbar.

Dazu testet man einfach

Dieses Vorgehen bezeichnet man auch als Anwendung des -Operators im Normalfall.

Falls y nicht existiert, kann es sein, daß die Berechnung nicht abbricht, sonst wird das letzte Argument ausgegeben, sobald die Berechnung den Wert true liefert.

Wir bemerken noch, daß die unbeschränkte Minimalisierung weder durch primitive Rekursion noch durch Einsetzung formuliert werden kann.

Diese beiden Konzepte sind also zu schwach, um die Schleifen höherer Programmiersprachen zu formulieren.

Der eingeschränkte -Operator

Definition: (eingeschränkter -Operator [6])
Der Ausdruck

definiert das kleinste z zwischen 0 und y einschließlich, für das gilt, falls es ein solches z gibt, sonst 0.

Wir sprechen vom eingeschränkten -Operator.

  Aus dem eingeschränkten -Operator gewinnt man eine Funktion

Im Gegensatz zum allgemeinen -Operator hat die Funktion f (n+1) Stellen.

steht für .

Satz:
Ist P ein primitiv rekursives Prädikat, so ist die Funktion f ebenfalls primitiv rekursiv.

Mit Hilfe des eingeschränkten -Operators kann man nun zeigen, daß diverse interessante Funktionen primitiv rekursiv sind.

Beispiel:
Die Funktion p(n), die die n-te Primzahl berechnet, ist primitiv rekursiv:

p(0) = 2

Die Eigenschaft Pr(x), daß x Primzahl ist, ist primitiv rekursiv, da man sie aus primitiv rekursiven Prädikaten zusammensetzen kann:

Im Zusammenhang mit der Gödelisierung werden wir noch die Funktion exp(n,x) benötigen, die angibt, mit welchem Exponenten die n-te Primzahl p(n) in x vorkommt.

Auch diese Funktion können wir mit dem eingeschränkten -Operator formulieren:

Die Funktion berechnet also das kleinste z, so daß x von nicht mehr geteilt wird.

-rekursive Funktionen

Wir werden nun die Anwendung des unbeschränkten -Operators im Normalfall zu den Konstruktionsprinzipien der primitiv rekursiven Funktionen hinzufügen.

        Definition: ( -rekursive Funktionen [6])
Eine Funktion heißt -rekursiv, wenn sie aus den drei Grundfunktionen der primitiv rekursiven Funktionen, durch Einsetzung, primitive Rekursion oder durch Anwendung des -Operators im Normalfall aufgebaut ist.

-rekursive Prädikate definieren wir analog zu primitiv rekursiven Prädikaten.

-rekursive Funktionen sind Turing-berechenbar  .

-rekursive Prädikate sind entscheidbar.

-Rekursivität ist ''mehr'' als primitive Rekursivität, wie der folgende Satz zeigt.

Satz:
Die Ackermann-Funktion ist -rekursiv.

Beweisskizze:
Der Beweis findet sich natürlich in [3]. Wir skizzieren die Idee. Zunächst betrachten wir die Berechnungsschritte für f(2,1):

0. f(2,1) 2,1

1. f(1,f(2,0)) 1,2,0

2. f(1,f(1,1)) 1,1,1

3. f(1,f(0,f(1,0))) 1,0,1,0

4. f(1,f(0,f(0,1))) 1,0,0,1

5. f(1,f(0,2)) 1,0,2

6. f(1,3) 1,3

7. f(0,f(1,2)) 0,1,2

8. f(0,f(0,f(1,1))) 0,0,1,1

9. f(0,f(0,f(0,f(1,0)))) 0,0,0,1,0

10. f(0,f(0,f(0,f(0,1)))) 0,0,0,0,1

11. f(0,f(0,f(0,2))) 0,0,0,2

12. f(0,f(0,3)) 0,0,3

13. f(0,4) 0,4

14. 5 5

Die einzelnen Zahlenfolgen erhöhen wir nun alle jeweils um 1, um von 0 verschiedene Werte zu erhalten und verwenden sie als Exponenten der Primzahlen. (Man erinnere sich an die Codierung der Turing-Maschinen)

0. f(2,1) 2,1 72

1. f(1,f(2,0)) 1,2,0 540

2. f(1,f(1,1)) 1,1,1 900

3. f(1,f(0,f(1,0))) 1,0,1,0 2100

4. f(1,f(0,f(0,1))) 1,0,0,1 2940

5. f(1,f(0,2)) 1,0,2 1500

6. f(1,3) 1,3 324

7. f(0,f(1,2)) 0,1,2 2250

8. f(0,f(0,f(1,1))) 0,0,1,1 7350

9. f(0,f(0,f(0,f(1,0)))) 0,0,0,1,0 16170

10. f(0,f(0,f(0,f(0,1)))) 0,0,0,0,1 25410

11. f(0,f(0,f(0,2))) 0,0,0,2 10290

12. f(0,f(0,3)) 0,0,3 3750

13. f(0,4) 0,4 486

14. 5 5 64

Aus einer Gödelnummer   kann man nun die entsprechende Konstantenfolge berechnen. So erhalten wir eine Funktion g(x,y,z), wobei x,y die Argumente der Ackermann-Funktion und z die Nummer des Berechnungsschritts sind.

Die Schritte nach dem Abschluß der Berechnung setzen wir konstant auf den letzten Wert -- im Beispiel also 64.

Man kann nun zeigen, daß g(x,y,z) primitiv rekursiv ist.

Dazu machen wir eine Fallunterscheidung:

g(x,y,0) dies ist die Gödelnummer des 0-ten Berechnungsschritts, also der Folge x,y und damit .

Damit haben wir den Anfang und müssen nun den Wert von g(x,y,z') aus g(x,y,z) berechnen. Dazu berechnen wir aus g(x,y,z) die Folge und unterscheiden vier Fälle:

1. n = 1: Dies kann nur der Wert des letzten Schritts sein. Also setzen wir g(x,y,z') = g(x,y,z), da ja nach diesem Schritt g(x,y,z) konstant sein soll.
2. n > 1 und : dies entspricht dem Fall f(0,y) als letztem Glied in der Funktionsschachtelung f(...f(0,y)...). Den nächsten Wert erhalten wir durch ''Vergödeln'' von .
3. n > 1 und : dies entspricht dem Fall f(x',0) als letztem Glied in der Funktionsschachtelung f(...f(x',0)...). Den nächsten Wert erhalten wir durch ''Vergödeln'' von . V ist die primitiv rekursive Vorgängerfunktion.
4. n > 1 und und : dies ist der Fall f(x',y') als letztem Glied in der Funktionsschachtelung f(...f(x',y')...). Den nächsten Wert erhalten wir durch ''Vergödeln'' von .

Der letzte Schritt n in der Berechnung, ist nun der Schritt, ab dem g konstant bleibt. Und das kann man mit dem -Operator formulieren:

Der Wert von g im Schritt z ist ist derselbe wie im Schritt z', und n ist das kleinste z mit dieser Eigenschaft. Wir können nun n als Funktion von x und y auffassen:

Da g primitiv rekursiv ist, ist -rekursiv.

ist das Ergebnis von g nach dem letzten Berechnungsschritt der Ackermann-Funktion f, also die Gödelnummer des Ergebnisses (von f). Um dieses Ergebnis zu erhalten, müssen wir mit der Funktion exp den Exponenten bestimmen, als der das Ergebnis auftritt, und davon mit V den Vorgänger berechnen.

Zum Abschluß noch einige grundlegende Sätze, deren Beweise man in [3] findet.

Satz:
Jede -rekursive Funktion ist Turing-berechenbar.

Um dies zu zeigen, stellt man die Realisierung des -Operators im Normalfall durch eine Turing-Maschine dar, läßt bei 0 beginnen, wendet die Turing-Maschine, die P entscheidet, darauf an und erhöht z solange, bis P wahr wird.

Satz:
Jede total Turing-berechenbare Funktion ist -rekursiv.

Die Beweisidee ist ähnlich zum Beweis der -Rekursivität der Ackermann-Funktion.

Diese Äquivalenzen zeigen einmal mehr, daß es sich bei den Turing-berechenbaren Funktionen offenbar genau um die Funktionen handelt, die man irgendwie mechanisch berechnen kann.

Und das hatten wir in der Church-Turing-These   ja auch schon festgestellt.