LOOP-, WHILE-, und GOTO-Berechenbarkeit Flashcards
LOOP - Wertebereich der Variablen
Die Variablen dürfen nur Werte aus den natürlichen Zahlen haben.
LOOP - Variablen
x_0, x_1, …
Die Variablen können nur Werte der Natürlichen Zahlen annehme.
LOOP - Konstanden
0, 1, 2, …
LOOP - Trennsymbole
- ;
- :=
LOOP - Operationen
+, -
LOOP - Schlüsselwörter
LOOP, DO, END
LOOP - Eingabe
Eingabe: x_1, … , x_k
(alle anderen Variablen x_i = 0)
LOOP - Berechnungsergebnis
Wert von x_0 am Programmende
LOOP - Addition
x_i := x_j + c
(x_i, x_j Variablen, c \in \N)
Subtraktion
x_i := max{x_j - c, 0}
max da x_i >= 0 sein muss.
(x_i, x_j Variablen, c \in \N)
LOOP - Sequenz
P_1;P_2
erst P_1, dann P_2
(P_1,P_2 LOOP Programme)
LOOP - Schleife
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.
LOOP - x_i := x_j
x_i := x_j + 0
LOOP - x_i := c
x_i := x_j + c (für ein x_j mit x_j = 0)
LOOP - IF x_i = 0 THEN P END
x_j := 1;
LOOP x_i DO x_j := 0 END;
LOOP x_j DO P END;
LOOP - x_0 := x_1 + x_2
x_0 := x_1;
LOOP x_2 DO x_0 := x_0 + 1 END
WHILE - Programme - Aufbau
WHILE-Programme = LOOP-Programme + WHILE-Schleife
WHILE - While Schleife
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)
terminierung von WHILE-Programmen
Die While-Schleife erlaubt es Programme zu schreiben die nie Terminieren werden. (Mit einer Endlosschleife)
WHILE - Berechnungsergebnis
Berechnungsergebnis: Wert von x_0 am Programmende (falls Programm terminiert).
LOOP-/While-Berechnebarkeit - Definition
Berechnung von Funktionen mit LOOP-Programmen
LOOP-Programme berechnen nur totale Funktionen.
Könne LOOP-Programme nicht terminieren?
Nein.
Daher könne LOOP-Programme nur totale Funktionen berechnen.
Sind alle totalen intuitiv berechenbaren Funktionen über den natürlichen Zahlen LOOP-berechenbar?
Nein, aber WHILE-Berechenbar.
