BuK-Übung09

Aus ProgrammingWiki

< BuK < IIm11

Archivierte Version vom 2012-05-29T17:54:23+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.

(define AP
  (lambda (x y)
  (if (= x 0)
      (+ y 1) 
      (if (= y 0)
          (AP (- x 1)1) 
          (AP (- x 1) (AP x (- y 1)))
          )
      )))

(AP 2 2)

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

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

BuK-Übung09

Suche