This flashcard is just one of a free flashcard set. See all flashcards!
38
Beweis: Satz von Rice
Unterprogrammtechnik:
Sei
eine TM, die L(S) entscheidet. Konstruiere eine TM 
, die 
entscheidet und als Unterprogramm aufruft. (Widerspruch zu unentscheidbar)
Sei u die überall undefinierte Funktion.
1. Fall:
Sei
eine Funktion aus S. (Ex. aufgrund Vors. 
). Die TM arbeitet so:
1.) Eingabe keine korrekte GN <M>: verwirft die Eingabe
2.) Konstruiere aus der GN <M> eine TM M* mit folgendem Verhalten:
(a) Ignoriere die Eingabe x. Simuliere M auf Eingabe
auf einer dafür reservierten Spur (von M*).
(b) Berechne f(x), simuliere M auf Eingabe x.
=> M* berechnet also nur f(x), wenn M in Schritt (a) auf gehalten hat.
3.) startet auf <M*> und akzeptert, wenn akzeptiert.
Sei
eine TM, die L(S) entscheidet. Konstruiere eine TM , die entscheidet und als Unterprogramm aufruft. (Widerspruch zu unentscheidbar)Sei u die überall undefinierte Funktion.
1. Fall:
Sei
eine Funktion aus S. (Ex. aufgrund Vors. ). Die TM arbeitet so:1.) Eingabe keine korrekte GN <M>: verwirft die Eingabe
2.) Konstruiere aus der GN <M> eine TM M* mit folgendem Verhalten:
(a) Ignoriere die Eingabe x. Simuliere M auf Eingabe
auf einer dafür reservierten Spur (von M*).(b) Berechne f(x), simuliere M auf Eingabe x.
=> M* berechnet also nur f(x), wenn M in Schritt (a) auf
gehalten hat.3.)
startet auf <M*> und akzeptert, wenn akzeptiert.