BuK-Übung09

WHILE-berechenbarkeit der Ackermann-Peter-Funktion

Weisen sie nach, dass die Ackermann-Peter-Funktion (AP-Funktion) WHILE-berechenbar ist.

Die AP-Funktion ist definiert durch:

AP(0, y) = y + 1
AP(x, 0) = AP(x - 1, 1); x > 0
AP(x, y) = AP(x - 1, AP(x, y - 1)); x, y > 0

Im folgenden werden 3 Beweise demonstriert, welche allerdings jeweils eine Bedingung mit sich bringen.

Beweis 1:

Der erste konstruktive Beweise setzt zunächst voraus, das die AP-Funktion in einer Turing-Vollständigen Sprache implementiert wird. Da Racket eine Turing-Vollständigen Sprache ist, kann diese hierfür verwendet werden.

Wenn man nun den Satz zu Grunde legt, wonach jede Turing-berechenbare Funktion auch WHILE-berechenbar und jede WHILE-berechenbare Funktion und Turing-berechenbar ist, ist auch die AP-Funktion WHILE-berechenbar.

Beweis 2:

Für den zweiten Beweis bedient man sich der Möglichkeit, das für ein WHILE-Programm Stacks zur Verfügung stehen. Diese sind durch die folgenden 3 Befehle definiert.

INIT

initialisiert einen leeren Stack

PUSH(x)

legt den Wert x auf dem Stack ab so das er an der obersten Position ist

POP

liest verbrauchend den Wert auf der obersten Position und gibt diesen zurück

Nun kann man einen Stack verwenden um die AP-Funktion in einem WHILE-Programm zu implementieren.

Wenn man sich die Visualisierung des Stacks über den Programmverlauf hinweg vor Augen hält, ist diese Lösung sogar recht intuitiv. Hierzu hilft es zunächst diesen auf zu schreiben. Im folgenden Beispiel wird das Ergebnis für AP(2, 2) errechnet.