BuK/IIm11/BuK-Übung09

Wiki-Quelltext dieser Seite.

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


<code id="4fc4f69ccc49d">
(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="4fc4f69ccc502">
(AP 2 2)
</run>


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:

<code id="4fc4fda5771d5">
INIT;  
PUSH(x); 
PUSH(y); 
WHILE size ≠ 1 DO      % size: Größe des Stacks 
  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 
END; 
x0 := POP
</code>