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
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.

Neuer Kommentar
Karteninfo:
Autor: hemag
Oberthema: Mathematik
Thema: Berechenbarkeit
Veröffentlicht: 16.03.2010

Abbrechen
E-Mail

Passwort

Login    

Passwort vergessen?
Deutsch  English