====== Berechenbarkeit ======
  * **Partielle Funktion** Funktion undefiniert => Programm terminiert nicht

===== "Intuitiv Berechenbar" =====
  * Es //existiert// ein Algorithmus, auch wenn dieser //nicht bekannt// ist.


===== Berechenbarkeitsmodelle =====
Äquivalent
  * TM
  * Mehrband TM
  * WHILE
  * GOTO
  * μ-Rekursiv
  * Registermaschiene
  * λ-Kalkül

Schwächere aber Äquivalent
  * LOOP
  * primitiv rekursiv

==== Mehrband TM ====
Einband TM <=> Mehrband TM

  * Ein Zustand
  * Mehre unabhängige Köpfe

Simulation kostet O(n²)
==== PROGRAMME ====
Vorbedingungen:
  * $x_1, x_2, \dots$ Eingabewerte
  * Alle anderen (per default) 0

Nachbedingungen:
  * $x_0$ Ergebniss


=== LOOP ===
  * ''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

=== WHILE ===
  * ''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**)

== Kleene-Normalform ==
"Alle WHILE-Programme können mit nur einem WHILE (aber mehreren LOOPs) geschrieben werden"

=== WHILE ===
  * ''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**''

==== Primitive Rekursion ====
| 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)$ |

==== μ-Rekursion ====
  * 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.


===== Gödel-Nummerierung =====
  - Symbole durchnummerieren
  - Aufsteigende folge von Primzahlen

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

===== Turing-berechenbar =====
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 //un//definiert:
  * Endlosschleife

===== Ackermann-Funktion =====
Ist //total//, trotzdem //nicht primitiv rekursiv// (aber μ-Rekursiv).

===== Reduzierbarkeit =====
==== Gegeben ====
  * $A \subseteq \Sigma^*$
  * $B \subseteq \Gamma^*$

==== Gesucht ====
Funktion f für die gild:
  * total
  * berechenbar
  * $\forall x \in \Sigma^* : x \in A \Leftrightarrow f(x) \in B$

==== Folgerung ====
Wenn $A \le B$ gilt (A auf B reduzierbar)
  * B entscheidbar => A entscheidbar
  * B semi-entscheidbar => A semi-entscheidbar
  * A unentscheidbar => B unentscheidbar

==== Anwendung ====
  * Ich will die //Unentscheidbarkeit von B beweisen//.
  * Ich tu die //Unentscheidbarkeit von A, einem Spezialfall, beweisen//.