Betrügt der Beweis der Unentscheidbarkeit des Halteproblems durch Umkehrung der Ergebnisse?

Ich habe Probleme, Turings Problem zu verstehen.

Sein Beweis geht davon aus, dass es eine magische Maschine die bestimmen könnte, ob ein Computer für eine bestimmte Eingabe für immer anhalten oder eine Schleife bilden würde. Dann schließen wir eine andere Maschine an, die die Ausgabe umkehrt, und wir haben einen Widerspruch, und daher kann nicht existieren.$H$$H$

Ich mache mir Sorgen, dass es den Anschein hat, als ob wir sagen, eine Antwort sei falsch, weil wir sie umgekehrt haben. Analog dazu, wenn es eine Maschine mit dem Namen gibt, die bei bestimmten Eingaben eine korrekte und bei anderen eine falsche Antwort ausgibt. Dann fügen wir eine weitere Maschine hinzu, die das Ergebnis von umkehrt, sodass die Kombination der beiden Maschinen im Widerspruch zu der Definition von steht. Die beiden Maschinen generieren jetzt falsche Antworten für Eingaben, für die definiert ist, um korrekte Antworten auszugeben, und geben korrekte Antworten für Eingaben aus, für die definiert ist, um falsche Antworten auszugeben. Wäre dies ein Widerspruch, und es gibt keine Maschine, die bei einigen Eingaben die richtige Antwort und bei anderen die falsche Antwort ausgibt?$A$$A$$A$$A$$A$

Kurzfassung: Die Ausgaben der Maschinen sind nicht korrekt oder falsch, sie sind nur widersprüchlich, was beweist, dass die ursprüngliche Maschine, die entscheidet, ob die Eingabemaschine an der angegebenen Zeichenfolge anhält oder nicht, nicht existieren kann.

Lange Version : Zuerst skizzieren wir den Beweis (oder mindestens eine Version davon - es gibt viele).

1. Es sei angenommen , dass wir eine Turing Maschine , ob die Turing Maschine entscheidet M stoppt am Eingang x oder nicht.$\mathrm{HALT}(\langle M\rangle, x)$$M$$x$
2. Verwendung von konstruieren wir eine Maschine F L I P ( ⟨ M ⟩ , x ) , die verwendet H A L T zu überprüfen , ob M stoppt auf x oder nicht, dann das Gegenteil der Fall ist, das heißt , wenn M stoppt auf x , F L I P Schleifen, wenn M nicht bei x anhält , F L I P hält an.$\mathrm{HALT}$$\mathrm{FLIP}(\langle M\rangle, x)$$HALT$$M$$x$$M$$x$$\mathrm{FLIP}$$M$$x$$\mathrm{FLIP}$
3. Schließlich schaffen wir eine TM (I guten Namen lief), die die Beschreibung eines TM und läuft nimmt F L I P mit Eingang ( ⟨ M ⟩ , ⟨ M ⟩ ) , Ausgabe unabhängig F L I P Ausgänge.$\mathrm{C}(\langle M \rangle)$$\mathrm{FLIP}$$(\langle M \rangle, \langle M \rangle)$$\mathrm{FLIP}$

Es ist wichtig zu beachten, dass jeder dieser Schritte einfach zu implementieren ist, solange der Entscheider existiert. F L I P muss nur H A L T verwenden , um zu überprüfen, was zu tun ist, und C dupliziert nur seine Eingabe, um zu F L I P zu gelangen .$\mathrm{HALT}$$\mathrm{FLIP}$$\mathrm{HALT}$$\mathrm{C}$$\mathrm{FLIP}$

Der Widerspruch entsteht , wenn wir sehen , was passiert , wenn wir laufen . Entweder wird C angehalten, wenn es selbst eingegeben wird, oder nicht. H A L T wird dies entscheiden:$\mathrm{C}(\langle\mathrm{C}\rangle)$$\mathrm{C}$$\mathrm{HALT}$

• Wenn stoppt am Eingabe ⟨ C ⟩ , H A L T wird sagen , Y e s , aber dann F L I P wird Schleife, so C Schleife wird, im Widerspruch zu H A L T .$\mathrm{C}$$\langle\mathrm{C}\rangle$$\mathrm{HALT}$$\mathsf{Yes}$$\mathrm{FLIP}$$\mathrm{C}$$\mathrm{HALT}$
• Wenn auf Eingangsschleifen ⟨ C ⟩ , H A L T wird sagen , N o , aber dann F L I P wird angehalten, so dass C wird auch halt, im Widerspruch zu H A L T .$\mathrm{C}$$\langle\mathrm{C}\rangle$$\mathrm{HALT}$$\mathsf{No}$$\mathrm{FLIP}$$\mathrm{C}$$\mathrm{HALT}$

Da jeder Schritt in der Konstruktion eindeutig korrekt ist, können wir nur den Schluss ziehen, dass nicht existieren kann; wir haben einen Fall konstruiert , wo , egal was sie sagt, H A L T nicht möglich kann entscheiden , was zu Ausgang, dh das Problem unentscheidbar ist. Nur um wirklich ein bisschen auf den Punkt zu hämmern, H A L T kann nicht existieren - das heißt, es kann kein TM geben, das das Halteproblem entscheidet -, weil es mindestens einen Fall gibt, den wir explizit konstruiert haben, in dem es kein logisches gibt mögliche Antwort. Denken Sie daran, dass ein Entscheider nicht die falsche Antwort ausgeben darf und etwas ausgeben muss, aber in dem Fall, dass wir konstruiert haben, sind beide möglichen Antworten falsch.$\mathrm{HALT}$$\mathrm{HALT}$$\mathrm{HALT}$

Sie sprechen über zwei verschiedene Bedeutungen von „Widerspruch“.

In Ihrer Analogie widersprechen sich die Maschine A und ihre gespiegelte Modifikation nur in dem Sinne, dass ihre Ausgaben immer unterschiedlich sind. (Zum Beispiel können sie zwei Testfunktionen für ganze Zahlen implementieren, " x ≤ 5?" Und " x > 5?") Das ist sicherlich eine Sache, die "Widerspruch" im alltäglichen Gebrauch bedeuten kann, aber es ist nicht das, was damit logisch gemeint ist Beweise.

In logischen Beweisen bedeutet es etwas Stärkeres: etwas, das einfach unmöglich ist. ZB eine Funktion, die bei allen Eingaben mehr als 5 "true" und bei allen Eingaben weniger als 10 "false" zurückgibt - das ist im engeren Sinne widersprüchlich, da bei beispielsweise 7 die Ausgabe beide "true" sein müsste. und "falsch", aber das ist nicht dasselbe. Turings Argumentation zeigt, dass das Stopp-Programm im engeren Sinne widersprüchlich ist: Unter der Annahme, dass es zu etwas führt, was unmöglich ist oder bereits als falsch bekannt ist.

Hier ist ein weiterer Beweis dafür, dass das Stopp-Problem nicht zu entscheiden ist. Wir sagen, dass ein Programm einen String x ausgibt, wenn es anhält und x ausgibt . (Wenn das Programm niemals anhält, gibt es keine Zeichenfolge aus.) Definieren Sie f ( n ) als die Länge der längsten Zeichenfolge, die von einem C-Programm mit einer Länge von höchstens n ausgegeben wird .$x$$x$$f(n)$$n$

Angenommen, das Halteproblem wäre entscheidend. Dann kann mit einem C-Programm berechnet werden:$f(m)$

Führen Sie bei Eingabe alle haltenden C-Programme mit einer Länge von höchstens m aus und bestimmen Sie deren Ausgabe. Liefert die Länge der maximalen Ausgabe.$m$$m$

Das bedeutet, dass wir für jedes ein Programm P m schreiben können , das f ( m ) + 1 Nullen ausgibt . Wie lang ist P m ? Es gibt eine feste C-Programmvorlage mit einem Platzhalter, der P m implementiert . Der Platzhalter sollte mit der Konstante m gefüllt sein . Angabe von m Takes | m | Zeichen (hier ist | m | die Länge der Dezimaldarstellung von m ), wobei | m | ≈ log $m$$P_m$$f(m)+1$$P_m$$P_m$$m$$m$$|m|$$|m|$$m$ . Die Vorlage nimmt einige feste Anzahl T von Zeichen, und so die Länge von P m ist T + log 10 m . Wenn wir m groß genugwählen( m = 2 T würdeausreichen), haben wir T + log 10 m ≤ m , und so ist f ( m ) mindestens die Größe der von P m ausgegebenen Zeichenkette, dh f ( m ) ≥ f ( m ) + $|m| \approx \log_{10} m$$T$$P_m$$T + \log_{10} m$$m$$m=2T$$T + \log_{10} m \leq m$$f(m)$$P_m$$f(m) \geq f(m) + 1$. Wir haben einen Widerspruch erreicht.