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.