VL-09: LOOP und WHILE Programme I

Question 1

Wie ist die LOOP Programmiersprache syntaktisch aufgebaut?

Answer 1

Variablen: x0, x1, x2, …
Konstanten: 0, 1
Symbole: :=, +, ;
Schlüsselwörter: LOOP, DO, ENDLOOP

Zuweisung: xi := xj + c
mit Variablen xi, xj und Konstante c

Hintereinanderausführung: P1 ; P2
mit Programmen P1 und P2

LOOP-Konstrukt: LOOP xi DO P1 ENDLOOP
mit Variable xi und Programm P1

Question 2

Welche zusätzlichen syntaktischen Elemente hat die WHILE Programmiersprache?

Answer 2

Symbole: !=
Schlüsselwörter: WHILE, ENDWHILE

WHILE-Konstrukt: WHILE xi != 0 DO P ENDWHILE
mit Variable xi und Programm P

Question 3

Wie ist der initiale Zustand eines LOOP bzw. WHILE Programms? Wie wird die Eingabe übermittelt?

Answer 3

• Eingabe: Variablen x1 - xn
• Alle anderen Variablen = 0

Question 4

Sind LOOP und WHILE turing-mächtig?

Answer 4

WHILE ja
LOOP nein

Question 5

Wie ist die Ackermann-Funktion definiert?

Answer 5

(m,n) -> Z
A(0, n) = n + 1
A(m + 1, 0) = A(m, 1)
A(m + 1, n + 1) = A(m, A(m + 1, n))

Question 6

Was ist die UpArrow Notation?

Answer 6

a ↑m b := 1 wenn b = 0
a ↑m b := a · b wenn m = 0
a ↑m b := a^b wenn m = 1
a ↑m b := a ↑m−1(a ↑m (b − 1)) sonst

Question 7

Wie lässt sich die Ackermann Funktion mit der UpArrow Notation beschreiben?

Answer 7

A(1, n) = 2 + (n + 3) − 3
A(2, n) = 2 · (n + 3) − 3
A(3, n) = 2 ↑ (n + 3) − 3
A(4, n) = 2 ↑↑ (n + 3) − 3
A(5, n) = 2 ↑↑↑ (n + 3) − 3
A(m, n) = 2 ↑m−2 (n + 3) − 3

• A wächst sehr stark mit steigendem m

Question 8

Wie lässt sich beweisen, dass WHILE turing mächtig ist?

Answer 8

• Induktiv
• Simulation einer TM durch WHILE Programm:

Variablen:
- Zustand
- Band vor Kopf
- Symbol unter Kopf
- Band nach Kopf (Inverse)

Schritt:
- Update Zustand
- Update Symbol unter Kopf
- Bewege Kopf L/N/R

Ablauf:
1. Initialisierung
2. WHILE Zustand != Endzustand DO
IF Zustand = x AND Kopf = y DO z …
….