Diskussion:Beweisarchiv: Theoretische Informatik: Berechenbarkeit: Halteproblem

Aus Wikibooks
Zur Navigation springen Zur Suche springen

Problem beim ersten Beweis (fehlerhaft?)[Bearbeiten]

Bei speziellen Halteproblem ist im Beweis der Wurm drin. Insbes. folgt die letzte Zeile im Beweis NICHT aus (*). Wohlmöglich sollte es so lauten: Es gilt:

hält (mit Eingabe <>) hält (mit Eingabe <>) hält nicht. (vgl. (*))

Widerspruch! Wieschoo 16:08, 8. Aug. 2013 (CEST)Antworten[Antworten]


Nein. ist quasi eine lokale Variable im Text der Erklärung. Die Erklärung nochmal in anderer Pseudosyntax in der ich lokale, gebundene Variablen klein schreibe und die spitzen Klammern für die Kodierung auslasse.

Also, wir nehmen an löst das Halteproblem. Jetzt definieren wir die Turingmaschine .

Define

Es gilt also für alle Eingaben folgendes: hält genau dann wenn nicht hält.

Jetzt betrachten wir indem wir es einfach in die letzte Gleichung für einsetzen: hält genau dann wenn nicht hält.

Widerspruch!

[anonymes Einhorn] 01:32, Jan. 2017