Berechenbarkeit

• Partielle Funktion Funktion undefiniert ⇒ Programm terminiert nicht

• Es existiert ein Algorithmus, auch wenn dieser nicht bekannt ist.

Äquivalent

• TM
• Mehrband TM
• WHILE
• GOTO
• μ-Rekursiv
• Registermaschiene
• λ-Kalkül

Schwächere aber Äquivalent

• LOOP
• primitiv rekursiv

Einband TM ⇔ Mehrband TM

• Ein Zustand
• Mehre unabhängige Köpfe

Simulation kostet O(n²)

Vorbedingungen:

• $x_1, x_2, \dots$ Eingabewerte
• Alle anderen (per default) 0

Nachbedingungen:

• $x_0$ Ergebniss

• 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

• Wie Primitive Rekursion
• Zusätzlich μ-Operator
  • Erzeugt neue Funktion mit n-1 Argumenten
  • Liefert erstes/kleinstes n mit dem $f(n, x_1, \dots, x_k) = 0$ wird.

1. Symbole durchnummerieren
2. Aufsteigende folge von Primzahlen

$2^39 \cdot 3^1 \cdot 5^9$

Vorbedingungen:

• deterministische TM
• Eingabewerte nacheinander auf Band
• Lesekopf am Anfang

–Start–

Nachbedingungen wenn definiert:

• TM Hält
• Nur Ergebnis auf Band
• Lesekopf am Anfang

Nachbedingungen wenn undefiniert:

• Endlosschleife

Ist total, trotzdem nicht primitiv rekursiv (aber μ-Rekursiv).

• $A \subseteq \Sigma^*$
• $B \subseteq \Gamma^*$

Funktion f für die gild:

• total
• berechenbar
• $\forall x \in \Sigma^* : x \in A \Leftrightarrow f(x) \in B$

Wenn $A \le B$ gilt (A auf B reduzierbar)

• B entscheidbar ⇒ A entscheidbar
• B semi-entscheidbar ⇒ A semi-entscheidbar
• A unentscheidbar ⇒ B unentscheidbar

• Ich will die Unentscheidbarkeit von B beweisen.
• Ich tu die Unentscheidbarkeit von A, einem Spezialfall, beweisen.