BuK/IIm11/BuK-Übung09

Wiki-Quelltext dieser Seite.

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.

'''erste Möglichkeit:'''

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>

'''zweite Möglichkeit:'''

In der Hilfestellung auf Folie 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>

Die Stackoperationen können durch ein WHILE-Programm simuliert werden. Dafür wird die Codierungsfunktion c: $N^2 \rightarrow N$ und ihre Umkehrfunktionen e, f verwendet. c, e und f sind privitiv rekursiv, und damit auch LOOP- (und erst recht WHILE-) berechenbar.

Sei $(n_1, n_2, ... ,n_k)$ der Inhahlt eines Stacks, wobei $n_1$ das oberste Stackelement ist. Mit Hilfe der Funktion c wird eine solche Zahlenfolge durch eine einzige Zahl n wie folgt dargestellt:

$n = c(n_1, c(n_2, ... , c(n_k,0)))$

e liefert erstes Argument von c(x,y) zurück: e(c(x,y)) = x 
f zweites Argument: f(c(x,y)) = y

Die Stackoperationen werden wie folgt programmiert:

INIT(stack) wird simuliert durch: n:=0

PUSH(a, stack) wird simuliert durch n:= c(a,n)

POP(stack) wird simuliert durch:

r := e(n);

n := f(n);

RETURN r;

Die Größe des Stacks wird durch f(n) berechnet.

e ist durch folgendes Programm berechenbar:

<code>
xm := 1; 
LOOP x1 do  
IF x1 ≥  xm THEN 
   x1 := x1 – xm; 
   xm := xm + 1; 
ELSE x0 := x1 END;
</code>

f ist durch folgendes Programm berechenbar:

<code>
xm := 1; 
LOOP x1 do  
IF x1 ≥  xm THEN 
   x1 := x1 – xm; 
   xm := xm + 1; 
ELSE x0 := (xm – 1) – x1; END;
</code>

c ist durch folgendes Programm berechenbar:

c(x,y) = sum(x + y) + x
Beispiel: c(2,1) =  1+2+3+2 = 8 

<code>
x1 = x + y;
SUM := 0;
LOOP x1 do
  LOOP x1 do
    SUMTEMP := SUMTEMP + 1;
  END;
  SUM:= SUM + SUMTEMP;
END;
RETURN SUM + x;
</code>

Quelle:

http://www.informatik.uni-leipzig.de/~brewka/papers/Berechenbarkeit3-5.pdf