Zu dieser Karteikarte gibt es einen kompletten Satz an Karteikarten. Kostenlos!
34
Beweis: Das Halteproblem ist nicht rekursiv
Zum Zweck des Widerspruchs nehmen wir an, dass H entscheidbar ist. Dann gib es eine TM 
, die H entscheidet.
Konstruieren nun eine TM
, die als Unterprgramm aufruft und 
entscheidet.
( ist unentscheidbar, als kann es nicht geben)
arbeitet wie folgt:
1.) Auf Eingabe w, berechne i, so dass gilt
2.) Berechne nun Gödelnummer der i-ten TM:
3.) Starte als Unterprogramm auf Eingabe 
4.) Falls akzeptiert, simuliere 
auf w und übernehme deren Akzeptanzverhalten
5.) Falls verwirft, so verwirf
Korrektheit:
1.Fall:
=> akzeptiert 
, da auf w hält=> akzeptiert w
2.Fall:
=> akzeptiert, falls w verwirft oder verwirft, falls nicht hält (also weder verwirft noch akzeptiert)=>in beiden Fällen: verwirft w.
, die H entscheidet.Konstruieren nun eine TM
, die als Unterprgramm aufruft und entscheidet.(
ist unentscheidbar, als kann es nicht geben) arbeitet wie folgt:1.) Auf Eingabe w, berechne i, so dass gilt
2.) Berechne nun Gödelnummer der i-ten TM:
3.) Starte
als Unterprogramm auf Eingabe 4.) Falls
akzeptiert, simuliere auf w und übernehme deren Akzeptanzverhalten5.) Falls
verwirft, so verwirfKorrektheit:
1.Fall:
=> akzeptiert , da auf w hält=> akzeptiert w2.Fall:
=> akzeptiert, falls w verwirft oder verwirft, falls nicht hält (also weder verwirft noch akzeptiert)=>in beiden Fällen: verwirft w.