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