CoboCards App FAQ & Wünsche Feedback
Sprache: Deutsch Sprache
Kostenlos registrieren  Login

Zu dieser Karteikarte gibt es einen kompletten Satz an Karteikarten. Kostenlos!

Alle Oberthemen / Mathematik / Berechenbarkeit / Berechenbarkeit I
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.
Neuer Kommentar
Karteninfo:
Autor: hemag
Oberthema: Mathematik
Thema: Berechenbarkeit
Veröffentlicht: 16.03.2010

Abbrechen
E-Mail

Passwort

Login    

Passwort vergessen?
Deutsch  English