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.

Dieser Aufschrieb stellt nun auch die Arbeitsweise des WHILE-Programms dar. Die Zahlen, welche jeweils auf einer Zeile sind, liegen in genau jener Reihenfolge auf dem Stack vor. Die oberste Zahl befindet sich dabei auf der rechten Position. Zum Start sind es die beiden werte, welche in Programmzeile 2 und 3 auf dem Stack abgelegt werden. Das Programm wird anschließend so lang ausgeführt, bis nur noch ein Wert, das Endergebnis, auf dem Stack liegt und dieser Wert in Variable x_0 zurück gegeben werden kann.

Nun wird in jedem Schleifendurchlauf eine Regel der AP-Funktion auf die oberen beiden Werte im Stack angewendet. Meist ist dies die dritte und letzte Regel. Zum Beispiel geht AP(2, 1) über in AP(1, AP(2, 0)). Dies wird ebenfalls in der Programmzeile 12 realisiert, welche die Werte 2 und 1 des Stacks durch die Werte 1, 2 und 0, in genau dieser Reihenfolge, ersetzt. Im Falle von 2 und 0 wird mit der Programmzeile 10 die zweite Regel angewendet und AP(2, 0) in AP(1, 1) überführt. Die erste Regel, und somit Programmzeile 8, findet Anwendung wenn der vorletzte Wert 0 ist. In diesem Fall wird nur der letzte Wert plus 1 auf den Stack abgelegt.