[ Inhalt ] [ Index ]

Die Ackermann-Funktion

 

Im letzten Abschnitt haben wir gezeigt, daß der folgende Satz gilt:

Satz:
Es gibt Turing-berechenbare Funktionen, die nicht primitiv rekursiv sind.

Bereits 1928 hat Ackermann   eine Funktion angegeben, die nicht primitiv rekursiv ist.

Zu ihrer Definition verwendete er ein Rekursionsschema, das nicht durch primitive Rekursion formuliert werden kann.

Die Idee ist, daß diese Funktion schneller als alle primitiv rekursiven Funktionen wächst.

Wenn wir die Addition, Multiplikation und Exponentiation betrachten, stellen wir fest, daß alle diese Funktionen nach dem gleichen Schema gebaut sind. Bezeichnen wir die Funktionen mit erhalten wir

Ackermann machte nun aus dem Index n ein Argument der Funktion

Damit ergibt sich:

f(n', x, y') = f(n, f(n', x, y), x)

Dieses Schema läßt sich nicht primitiv rekursiv formulieren.

Außerdem sieht man, daß das x unverändert ''durchgereicht'' und nur als Argument von verwendet wird. Also lassen wir x weg und erhalten:

f(n', y') = f(n, f(n', y))

Wir benennen n in x um:

f(x', y') = f(x, f(x', y)) z.B. f(1,1) = f(0, f(1,0)).

Für den Rekursionsanfang setzen wir daher:

f(0, y) = y'

f(x', 0) = f(x, 1)

In der Praxis findet diese Funktion Verwendung, um die Effizienz von Prozeduraufrufmechanismen zu testen.

Den formalen Beweis, daß die Ackermann-Funktion   nicht primitiv rekursiv ist, findet man in [3].

Die primitiv rekursiven Funktionen verwenden im Prinzip nur die Nachfolgerfunktion; dennoch lassen sich mit ihnen nahezu alle interessanten Funktionen beschreiben.

Was man tun muß, um alle totalen Turing-berechenbaren Funktionen beschreiben zu können, werden wir im nächsten Abschnitt untersuchen.

Primitiv rekursive Prädikate

Logische Prädikate   sind Aussagen, die entweder wahr oder falsch sind.

Äquivalent sind dazu Funktionen, die nur zwei Werte annehmen können, z.B. 0 oder 1; oder etwas allgemeiner den Wert 0 und Werte .

Wir verknüpfen nun Prädikate und primitiv rekursive Funktionen zu primitiv rekursiven Prädikaten    

Definition: (primitiv rekursives Prädikat [6])
Wenn eine n-stellige Funktion f primitiv rekursiv ist, so heißt das Prädikat P primitiv rekursives Prädikat, wenn gilt:

Die Funktion f liefert also genau dann den Wert 0, wenn P gilt.

f bezeichnet man auch als charakteristische Funktion   von P.

In [3] findet man eine große Kollektion primitiv rekursiver Prädikate; wir sehen uns nur einige davon an:

Gleichheitsbeziehung:

Dabei ist mit

Ähnlich kann man zeigen, daß primitiv rekursive Prädikate sind.

Jedes primitiv rekursive Prädikat ist entscheidbar, da man ja nur die zugehörige primitiv rekursive Funktion berechnen muß.

Es ist interessant (und hilfreich), daß man aus mehreren primitiv rekursiven Prädikaten weitere Prädikate zusammensetzen kann, die dann auch primitiv rekursiv sind. Wir zeigen, daß man für das zusammengesetze Prädikat eine primitiv rekursive Funktion finden kann, die die Bedingung aus der Definition erfüllt.

Negation  :
Sei Q ein primitiv rekursives Prädikat, g die charakteristische Funktion. Dann gilt:

Dabei ist

Konjunktion  :
Seien Q, R primitiv rekursive Prädikate, q, r die charakteristischen Funktionen. Dann gilt:

Alternative  :
Seien Q, R primitiv rekursive Prädikate, q, r die charakteristischen Funktionen. Dann gilt:

Der Konjunktion entspricht also die Addition, der Alternative das Produkt der charakteristischen Funktionen.