LOOP und WHILE Programme

Question 1

Syntax von LOOP

Answer 1

• Variablen(x1, x2..)
• Konstanten(0 und 1)
• Symbole(:= + ;)
• Schlüsselwörter: LOOP DO ENDLOOP

Question 2

Zuweisungen im LOOP Programm

Answer 2

x_i:= x_j + c

Question 3

Hintereinanderausführung zweier LOOP Programme

Answer 3

P1; P2

Question 4

LOOP Konstrukt + Bedeutung

Answer 4

LOOP x_i DO P ENDLOOP

Bedeutung: P wird x_i mal hintereinander ausgeführt

Question 5

Initialisierung der LOOP/WHILE Programms

Answer 5

Die Eingabe ist in den Variablen x_1, …x_m enthalten, alle anderen Variablen werden mit 0 initialisiert

Question 6

Ergebnis der LOOP/WHILE Programms steht in Variabel

Answer 6

x0

Question 7

P ist Zuweisung x_i:= x_j + c , dann [P] (r1,…,rk) =

Answer 7

(r_1, …, r_i-1, r_j+c, r_i+1, …, r_k)

Question 8

P = P1; P2 , dann [P] (r1,…,rk) =

Answer 8

[P2] ([P1] (r_1, … r_k))

Question 9

P = LOOP x_i DO Q ENDLOOP, dann [P] (r1,…,rk) =

Answer 9

= [Q]^(r_i) (r_1, … r_k)

Question 10

IF kann mit einem … Programm simuliert werden

Answer 10

LOOP

Question 11

Syntax von WHILE

Answer 11

• Variablen(x1, x2..)
• Konstanten(0 und 1)
• Symbole(:= + ; ≠)
• Schlüsselwörter: WHILE DO ENDWHILE

Question 12

WHILE Konstrukt + Bedeutung

Answer 12

WHILE x_i ≠ 0 DO P ENDWHILE

Bedeutung: P wird so lange ausgeführt bis x_i den Wert 0 erreicht

Question 13

Jede …- berechenbare Funktion ist auch … - berechenbar.

Answer 13

LOOP, WHILE

Question 14

… Programme terminieren immer, aber … Programme terminieren nicht immer.

Answer 14

LOOP, WHILE

Question 15

Satz über Terminierung der LOOP Programme

Answer 15

Jedes LOOP Programm hält auf jeder möglichen Eingabe nach endlich vielen Schritten an.

Question 16

LOOP ist… (Turing-mächtig/ nicht Turing-mächtig)

Answer 16

nicht Turing-mächtig

Question 17

WHILE ist… (Turing-mächtig/ nicht Turing-mächtig)

Answer 17

Turing-mächtig

Question 18

Definition von Ackermann Funktion:

Answer 18

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

Question 19

Ackermann Funktion mit ersten Parameter fixiert:

Answer 19

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

Question 20

Sei P= WHILE x_i ≠ 0 DO P ENDWHILE. Dann ist P=

Answer 20

= [Q]^l (r1,…, rk) für die kleinste Zahl l, für die die i-te Komponente von [Q]^l (r1,…, rk) gleich 0.

Question 21

Satz von Ackermann

Answer 21

Es existieren berechenbare totale Funktionen f: N^k -> N die nicht LOOP berechenbar sind.

Question 22

Definition UpArrow - Notation

Answer 22

a ↑m b = 
1 wenn b=0
a∙b wenn m=0
a^b wenn m=1 
a ↑(m-1) (a ↑m  (b-1))

Question 23

A(m, n) =

Answer 23

2 ↑(m-2) (n+3) - 3 für m ≥ 2

Question 24

Die Ackermann Funktion ist..

Answer 24

Turing-berechenbar

Question 25

Monotonie Verhalten der Ackermann Funktion: für m ≥ m’ oder n ≥ n’ folgt:

Answer 25

A(m, n) ≥ A(m’, n’)

Question 26

Vergleichen Sie A(m+1, n-1) mit A(m,n)

Answer 26

A(m+1, n-1) ≥ A(m,n)

Question 27

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

Answer 27

f_P( ⃗a) = b_1+ … + b_k

Summe

Question 28

Definition Wachstumsfunktion F_P : N → N

Answer 28

F_P(n) = max{ f_P( ⃗a) | ⃗a ϵ N^k mit a_1 + … + a_k ≤ n}

Question 29

Wachstumslemma

Answer 29

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

Question 30

Die Ackermann-Funktion ist.. (LOOP-berechenbar/ nicht LOOP-berechenbar)

Answer 30

nicht LOOP-berechenbar

Question 31

Die Ackermann-Funktion ist.. (WHILE-berechenbar/ nicht WHILE-berechenbar)

Answer 31

WHILE-berechenbar

Question 32

Die modifiziertes Vorgängerfunktion ist…

Answer 32

LOOP-berechenbar