BuK-Übung09

Aus ProgrammingWiki

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.

(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)

ausführen

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:

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

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:

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