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 aufgezeigt.


<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, da in WHILE-Programmen keine rekursiven Programmaufrufe definiert sind.

Erklärung von PUSH, POP und Init:

PUSH(x) legt x auf den Stack ab,

POP entfernt das oberste Stackelement und liefert dessen Wert,

INIT initialisiert den leeren Stack.


Mit Hilfe dieser Stackoperationen kann die Ackermann-Funktion wie folgt, als WHILE-Programm dargestellt werden: 

<code>
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 verwendet werden, da sie wiederum durch WHILE-Programme ausdrückbar sind. Für die Stackoperationen werden die Codierungsfunktion c: $N^2 \rightarrow N$ und ihre Umkehrfunktionen e, f verwendet. c, e und f sind primitiv rekursiv und damit auch LOOP- sowie WHILE-berechenbar.

Der Inhalt eines Stacks sei $(n_1, n_2, ... ,n_k)$, dabei ist $n_1$ das oberste Stackelement. 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 das erste Argument von c(x,y) zurück: e(c(x,y)) = x 

f liefert das zweite 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:

<code>
r := e(n);

n := f(n);

RETURN r;
</code>

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

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>

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>


Quelle:

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