Diskussion:Beweisarchiv: Theoretische Informatik: Berechenbarkeit: Halteproblem

Problem beim ersten Beweis (fehlerhaft?)

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:

$M_{K}$ hält $\Leftrightarrow$ ${\tilde {M}}$ (mit Eingabe <${\tilde {M}}$>) hält $\Leftrightarrow$ $M$ (mit Eingabe <${\tilde {M}}$>) hält nicht. (vgl. (*))

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

Nein. $M$ 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 $M_{K}$ löst das Halteproblem. Jetzt definieren wir die Turingmaschine ${\tilde {M}}$.

Define ${\tilde {M}}(x)=\mathrm {if} \ M_{K}(x(x))\ \mathrm {then} \ \mathrm {LOOP} \ \mathrm {else} \ \mathrm {terminate}$

Es gilt also für alle Eingaben $x$ folgendes: ${\tilde {M}}(x)$ hält genau dann wenn $x(x)$ nicht hält.

Jetzt betrachten wir ${\tilde {M}}({\tilde {M}})$ indem wir es einfach ${\tilde {M}}$ in die letzte Gleichung für $x$ einsetzen: ${\tilde {M}}({\tilde {M}})$ hält genau dann wenn ${\tilde {M}}({\tilde {M}})$ nicht hält.

Widerspruch!

[anonymes Einhorn] 01:32, Jan. 2017