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