LOOP und WHILE Programme Flashcards
Syntax von LOOP
- Variablen(x1, x2..)
- Konstanten(0 und 1)
- Symbole(:= + ;)
- Schlüsselwörter: LOOP DO ENDLOOP
Zuweisungen im LOOP Programm
x_i:= x_j + c
Hintereinanderausführung zweier LOOP Programme
P1; P2
LOOP Konstrukt + Bedeutung
LOOP x_i DO P ENDLOOP
Bedeutung: P wird x_i mal hintereinander ausgeführt
Initialisierung der LOOP/WHILE Programms
Die Eingabe ist in den Variablen x_1, …x_m enthalten, alle anderen Variablen werden mit 0 initialisiert
Ergebnis der LOOP/WHILE Programms steht in Variabel
x0
P ist Zuweisung x_i:= x_j + c , dann [P] (r1,…,rk) =
(r_1, …, r_i-1, r_j+c, r_i+1, …, r_k)
P = P1; P2 , dann [P] (r1,…,rk) =
[P2] ([P1] (r_1, … r_k))
P = LOOP x_i DO Q ENDLOOP, dann [P] (r1,…,rk) =
= [Q]^(r_i) (r_1, … r_k)
IF kann mit einem … Programm simuliert werden
LOOP
Syntax von WHILE
- Variablen(x1, x2..)
- Konstanten(0 und 1)
- Symbole(:= + ; ≠)
- Schlüsselwörter: WHILE DO ENDWHILE
WHILE Konstrukt + Bedeutung
WHILE x_i ≠ 0 DO P ENDWHILE
Bedeutung: P wird so lange ausgeführt bis x_i den Wert 0 erreicht
Jede …- berechenbare Funktion ist auch … - berechenbar.
LOOP, WHILE
… Programme terminieren immer, aber … Programme terminieren nicht immer.
LOOP, WHILE
Satz über Terminierung der LOOP Programme
Jedes LOOP Programm hält auf jeder möglichen Eingabe nach endlich vielen Schritten an.
LOOP ist… (Turing-mächtig/ nicht Turing-mächtig)
nicht Turing-mächtig
WHILE ist… (Turing-mächtig/ nicht Turing-mächtig)
Turing-mächtig
Definition von Ackermann Funktion:
A : N^2 → N mit
A(0, n) = n+1, für n ≥ 0
A(m+1, 0) = A(m, 1), für m ≥ 0
A(m+1, n+1) = A(m, A(m+1, n)), für m,n ≥ 0
Ackermann Funktion mit ersten Parameter fixiert:
A(0, n) = n+1 A(1, n) = n+2 A(2, n)= 2n+3 A(3,n)= 2^(n+3) - 3 A(4,n) = 2^(2^(2)....) - 3, mit n+3 viele Zweien
Sei P= WHILE x_i ≠ 0 DO P ENDWHILE. Dann ist P=
= [Q]^l (r1,…, rk) für die kleinste Zahl l, für die die i-te Komponente von [Q]^l (r1,…, rk) gleich 0.
Satz von Ackermann
Es existieren berechenbare totale Funktionen f: N^k -> N die nicht LOOP berechenbar sind.
Definition UpArrow - Notation
a ↑m b = 1 wenn b=0 a∙b wenn m=0 a^b wenn m=1 a ↑(m-1) (a ↑m (b-1))
A(m, n) =
2 ↑(m-2) (n+3) - 3 für m ≥ 2
Die Ackermann Funktion ist..
Turing-berechenbar
Monotonie Verhalten der Ackermann Funktion: für m ≥ m’ oder n ≥ n’ folgt:
A(m, n) ≥ A(m’, n’)
Vergleichen Sie A(m+1, n-1) mit A(m,n)
A(m+1, n-1) ≥ A(m,n)
Betrachte ein fixes LOOP Programm mit k Variablen x_1, …, x_k. Für die Anfangswerte ⃗a = (a_1, …, a_k) ϵ N^k der Variable, definieren wir f_P( ⃗a) = ….. als … aller Ergebniswerte in [P] ( ⃗a) = (b_1, …, b_k).
f_P( ⃗a) = b_1+ … + b_k
Summe
Definition Wachstumsfunktion F_P : N → N
F_P(n) = max{ f_P( ⃗a) | ⃗a ϵ N^k mit a_1 + … + a_k ≤ n}
Wachstumslemma
Für jedes LOOP Programm P existiert eine natürliche Zahl m_P, sodass für alle n ϵ N gilt: F_P(n) < A(m_P, n).
Die Ackermann-Funktion ist.. (LOOP-berechenbar/ nicht LOOP-berechenbar)
nicht LOOP-berechenbar
Die Ackermann-Funktion ist.. (WHILE-berechenbar/ nicht WHILE-berechenbar)
WHILE-berechenbar
Die modifiziertes Vorgängerfunktion ist…
LOOP-berechenbar
