Nicht berechenbare Funktionen: ein Beispiel
Jede Turing-Maschine läßt sich eindeutig als natürliche Zahl codieren.
Unter dem speziellen Halteproblem versteht man folgendes Problem:
• gegeben: natürliche Zahl m • gefragt: terminiert Turing-Maschine mit Code m bei Eingabe m?
Problem repräsentierbar als Funktion f: Nat --> {0, 1}, f(m) = 1 gdw TM mit Code m hält bei Eingabe m, f(m) = 0 sonst
<=> M bei Eingabe n liefert 0
<=> TM mit Code n hält nicht bei Eingabe n
<=> M' hält nicht bei Eingabe n
Funktion f ist nicht berechenbar!!
Angenommen es gäbe TM M, die f berechnet. Konstruiere daraus TM M' wie folgt: M' führt erst M aus, danach wird getestet, ob das Band den Wert 0 hat. Falls ja terminiert M', falls nein geht M' in Endlosschleife. Sei n der Code von M'. Es gilt: