BuK-Übung09

Weisen Sie nach, dass die AP-Funktion

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

WHILE-berechenbar ist.

Nach den Sätzen, dass jede Turing-berechenbare Funktion auch WHILE-berechenbar und jede WHILE-berechenbare Funktion auch Turing-berechenbar ist, wird mit der Angabe eines Programmes für die Ackermann-Peter-Funktion in einer Turing-Vollständigen Sprache auch die WHILE-Berechenbarkeit der AP-Funktion gezeigt.

In der Hilfestellung auf Seite 22 wird die Ackermann-Funktion mit Hilfe eines Stacks simuliert:

Erklärung von PUSH, POP und Init:

PUSH(x) legt x auf den Stack ab,

POP entfernt oberstes Stackelement und liefert dessen Wert,

INIT initialisiert leeren Stack.

Mit Hilfe dieser Stackoperationen kann die Ackermann-Funktion als WHILE-Programm aufgeschrieben werden: