Benutzer:Dirk Hünniger/turing

• Sei h eine Funktion die feststellt ob eine beliebige Funktion f für eine beliebige Eingabe x hält.
• konkret soll sie einen 1 zurückgeben falls f(x) hält und eine 0 anderenfalls. (1)
• sei g welche eine Funktion f als Parameter erhält und prüft ob h(f,f)=0 gilt. (2)
  • Falls ja soll g eine 0 zurückgeben
  • Falls nein soll g in eine Endlosschleife gehen.
• Frage was ist g(g)
  • Möglichkeit a: g(g) gibt 0 zurück
    • Dann muss offenbar h(g,g)=0 gelten, wegen (2)
    • Dann muss aber g(g) ewig laufen wegen (1) und kann daher keine 0 zurückgeben
    • Das ist eine Widerspruch daher kann Möglichkeit a nicht eintreten.
  • Möglichkeit b: g(g) läuft geht in eine Endlosschleife
    • Dann muss offenbar h(g,g)≠0 gelten.
    • Dann bleibt wegen (1) nur h(g,g)=1
    • Dann muss g(g) halten wegen (1)
    • Dies ist ebenfalls ein Widerspruch, daher kann auf Möglichkeit b nicht eintreten.
• Also bleibt nur der Fall, dass bereits die Annahme das es h gäbe falsch ist.
• Also kann es h nicht geben.
• Man kann also kein Programm schreiben, dass für jedes beliebiges andere Programm feststellt ob es terminiert oder nicht.
• Gute Nacht