BuK/IIm12/BuK-Übung09

Wiki-Quelltext dieser Seite.

<language>Scheme</language>
== 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.

<code id="simareic_ap_funktion" rows="9">
(define AP
  (lambda (x y)
  (if (= x 0)
      (+ y 1) 
      (if (= y 0)
          (AP (- x 1)1) 
          (AP (- x 1) (AP x (- y 1)))
          )
      )))
</code>

<run id="simareic_ap_funktion">
(AP 3 2)
</run>

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. 

<code id="simareic_ap_funktion2" rows="4">
INIT;
PUSH(x);
PUSH(y);
WHILE size != 1 DO
  y = POP;
  x = POP;
  IF x = 0 THEN
    PUSH(y+1);
  ELSE IF y = 0 THEN
    PUSH(x-1); PUSH(1);
  ELSE
    PUSH(x-1); PUSH(x); PUSH(y-1);
  END
END
x0 = POP;
</code>

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.
<code id="simareic_ap_aufschrieb" rows="10">
AP(2, 2)
AP(1, AP(2, 1))
AP(1, AP(1, AP(2, 0)))
AP(1, AP(1, AP(1, 1)))
AP(1, AP(1, AP(0, AP(1, 0))))
AP(1, AP(1, AP(0, AP(0, 1))))
AP(1, AP(1, AP(0, 2)))
AP(1, AP(1, 3))
AP(1, AP(0, AP(1, 2)))
AP(1, AP(0, AP(0, AP(1, 1))))
AP(1, AP(0, AP(0, AP(0, AP(1, 0)))))
AP(1, AP(0, AP(0, AP(0, AP(0, 1)))))
AP(1, AP(0, AP(0, AP(0, 2))))
AP(1, AP(0, AP(0, 3)))
AP(1, AP(0, 4))
AP(1, 5)
AP(0, AP(1, 4))
AP(0, AP(0, AP(1, 3)))
AP(0, AP(0, AP(0, AP(1, 2))))
AP(0, AP(0, AP(0, AP(0, AP(1, 1)))))
AP(0, AP(0, AP(0, AP(0, AP(0, AP(1, 0))))))
AP(0, AP(0, AP(0, AP(0, AP(0, AP(0, 1))))))
AP(0, AP(0, AP(0, AP(0, AP(0, 2)))))
AP(0, AP(0, AP(0, AP(0, 3))))
AP(0, AP(0, AP(0, 4)))
AP(0, AP(0, 5))
AP(0, 6)
 = 7
</code>