LOOP-, WHILE-, und GOTO-Berechenbarkeit

Question 1

LOOP - Wertebereich der Variablen

Answer 1

Die Variablen dürfen nur Werte aus den natürlichen Zahlen haben.

Question 2

LOOP - Variablen

Answer 2

x_0, x_1, …

Die Variablen können nur Werte der Natürlichen Zahlen annehme.

Question 3

LOOP - Konstanden

Answer 3

0, 1, 2, …

Question 4

LOOP - Trennsymbole

Answer 4

• ;
• :=

Question 5

LOOP - Operationen

Answer 5

+, -

Question 6

LOOP - Schlüsselwörter

Answer 6

LOOP, DO, END

Question 7

LOOP - Eingabe

Answer 7

Eingabe: x_1, … , x_k
(alle anderen Variablen x_i = 0)

Question 8

LOOP - Berechnungsergebnis

Answer 8

Wert von x_0 am Programmende

Question 9

LOOP - Addition

Answer 9

x_i := x_j + c

(x_i, x_j Variablen, c \in \N)

Question 10

Subtraktion

Answer 10

x_i := max{x_j - c, 0}

max da x_i >= 0 sein muss.

(x_i, x_j Variablen, c \in \N)

Question 11

LOOP - Sequenz

Answer 11

P_1;P_2

erst P_1, dann P_2

(P_1,P_2 LOOP Programme)

Question 12

LOOP - Schleife

Answer 12

LOOP x_i DO P END

Anzahl Durläufe = Wert von x_i vor der Anweisung!

(x_i Variable, P LOOP Programm)
x_i darf nicht durch P verändert werden.

Question 13

LOOP - x_i := x_j

Answer 13

x_i := x_j + 0

Question 14

LOOP - x_i := c

Answer 14

x_i := x_j + c (für ein x_j mit x_j = 0)

Question 15

LOOP - IF x_i = 0 THEN P END

Answer 15

x_j := 1;
LOOP x_i DO x_j := 0 END;
LOOP x_j DO P END;

Question 16

LOOP - x_0 := x_1 + x_2

Answer 16

x_0 := x_1;
LOOP x_2 DO x_0 := x_0 + 1 END

Question 17

WHILE - Programme - Aufbau

Answer 17

WHILE-Programme = LOOP-Programme + WHILE-Schleife

Question 18

WHILE - While Schleife

Answer 18

WHILE x_i != 0 DO P END

wiederhole P bis x_i = 0; x_i darf durch P modifiziert werden!

(x_i Variable, P WHILE Programm)

Question 19

terminierung von WHILE-Programmen

Answer 19

Die While-Schleife erlaubt es Programme zu schreiben die nie Terminieren werden. (Mit einer Endlosschleife)

Question 20

WHILE - Berechnungsergebnis

Answer 20

Berechnungsergebnis: Wert von x_0 am Programmende (falls Programm terminiert).

Question 21

LOOP-/While-Berechnebarkeit - Definition

Answer 21

Question 22

Berechnung von Funktionen mit LOOP-Programmen

Answer 22

LOOP-Programme berechnen nur totale Funktionen.

Question 23

Könne LOOP-Programme nicht terminieren?

Answer 23

Nein.

Daher könne LOOP-Programme nur totale Funktionen berechnen.

Question 24

Sind alle totalen intuitiv berechenbaren Funktionen über den natürlichen Zahlen LOOP-berechenbar?

Answer 24

Nein, aber WHILE-Berechenbar.

Question 25

WHILE-Programme & Turing-Maschinen - Theorem

Answer 25

Jede WHILE-berechenbare Funktion ist Turing-berechenbar.

Question 26

GOTO-Programme - Definition

Answer 26

Question 27

GOTO- und WHILE-Programme - Mächtigkeit

Answer 27

• Jede GOTO-berechenbare Funktion ist WHILE-berechenbar.
• Jede WHILE-berechenbare Funktion ist GOTO-berechenbar.

Question 28

Mächtigkeit von WHILE, GOTO und Turing

Answer 28

Question 29

GOTO-Berechenbarkeit

Answer 29

Analog zu WHILE-Berechenbarkeit.

Question 30

Mit wie vielen WHILE-Schleifen kann man jedes WHILE-Programm darstellen?

Answer 30

Jedes WHILE-Programm kann mit einer einzigen WHILE-Schleife dargestellt werden.