BuK-Übung09

Aus ProgrammingWiki
< BuK < IIm11
Archivierte Version vom 2012-05-29T17:58:34+00:00. Aktuelle Version

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. 




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:

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

Jede Stackoperation kann 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 primitiv 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 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:
r := e(n);
n := f(n);
RETURN r;
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 

x1 = x + y;
SUM := 0;
LOOP x1 do
 LOOP x1 do
   SUMTEMP := SUMTEMP + 1;
 END;
 SUM:= SUM + SUMTEMP;
END;
RETURN SUM + x;

e ist durch folgendes Programm berechenbar:

xm := 1; 
LOOP x1 do  
IF x1 ≥  xm THEN 
  x1 := x1 – xm; 
  xm := xm + 1; 
ELSE x0 := x1 END;
f ist durch folgendes Programm berechenbar:

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

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