Äquivalent
Schwächere aber Äquivalent
Einband TM ⇔ Mehrband TM
Simulation kostet O(n²)
Vorbedingungen:
Nachbedingungen:
x := x + c
x := x - c
(wird nicht kleiner 0)P;P
LOOP x DO P END
(so oft, wie x
zu beginn war)LOOP ⇒ Nur endliche Schleifen ⇒ Nur totale Funktionen
x := x + c
x := x - c
(wird nicht kleiner 0)P;P
LOOP x DO P END
(so oft, wie x
zu beginn war)WHILE x
$\ne$ 0 DO P END
(⇐ Neu)„Alle WHILE-Programme können mit nur einem WHILE (aber mehreren LOOPs) geschrieben werden“
M: x := x + c
M: x := x - c
(wird nicht kleiner 0)P;P
M: GOTO M
M: IF x = c THEN GOTO M
M: HALT
Konstanten | $f() = 42$ |
Argument Auswahl (Projektion) | $f(x, y, z) = y$ |
Successor | $f(n) = n+1$ |
Einsetzen | $f(n) = g(n, h(n))$ |
Primitive Rekursion | $f(0, x_1, \dots, x_k) = g(x_1, \dots, x_k)$ |
$f(n, x_1, \dots, x_k) = h(f(n-1, x_1, \dots, x_k), n-1, x_1, \dots, x_k)$ |
n
mit dem $f(n, x_1, \dots, x_k) = 0$ wird.$2^39 \cdot 3^1 \cdot 5^9$
Vorbedingungen:
–Start–
Nachbedingungen wenn definiert:
Nachbedingungen wenn undefiniert:
Ist total, trotzdem nicht primitiv rekursiv (aber μ-Rekursiv).
Funktion f für die gild:
Wenn $A \le B$ gilt (A auf B reduzierbar)