Wie ist Turings Lösung für das Halteproblem nicht einfach „Failure By Design“?

Es fällt mir schwer, Turings Lösung für das Halteproblem als Logiker und nicht als Ingenieur zu sehen.

Hier ist mein Verständnis des Halteproblems:

Sei die Menge aller Turingmaschinen. $M$

Lassen für alle die Turing - Maschinen in die Menge aller Eingänge sein . $i$$M$

Sei jedes Element in ein Element in . $M$$i$

Die booleschen Werte und seien Elemente in . $true$$false$$i$

Sei eine Funktion, die zurückgibt: $h(M,i)$

• $true$ wenn und nur wenn anhält $M(i)$
• $false$ genau dann, wenn nicht anhält $M(i)$

Sei eine Turingmaschine in , die:$p(M)$$M$

• ruft$h(M,M)$
• wird genau dann angehalten, wenn zurückgibt$h(M,M)$$false$
• hört nicht genau dann auf, wenn zurückkehrt$h(M,M)$$true$

Was passiert, wenn wir anrufen? $p$ durch Vorbeigehen $p$ zu sich selbst, $p(p)$?

Der Teil, mit dem ich Probleme habe, ist die Implementierung $p(M)$ damit es nicht aufhört wann $h(M,M)$ ist $true$. Mein Bauch versteht diesen Ansatz wie folgt:

Eine Methode gegeben $h()$ das funktioniert und eine Methode $p()$ entworfen, um zu brechen $h()$Wenn wir diese Methoden kombinieren, um eine Maschine zu bauen, ist diese Maschine kaputt.

Ich verstehe, dass Beweis durch Widerspruch ein gültiger Ansatz zur Problemlösung in der formalen Logik ist, aber diese spezielle Anwendung von Beweis durch Widerspruch scheint irgendwie fehlerhaft zu sein.

Was vermisse ich?

Im Folgenden werde ich eine Maschine unterscheiden $M$ aus seiner Beschreibung, die die Beschreibung von bezeichnet $M$ durch $\langle M\rangle$.

Spezifikation des Stopp-Tester-Programms, $H$

$H$ nimmt als Eingabe ein Paar $(\langle M\rangle, i)$, wo $\langle M\rangle$ ist die Beschreibung der Maschine $M$, und $i$ ist die Eingabe von $M$.

$H$hält bei jedem Eingangspaar an$(\langle M\rangle, i)$ und gibt die richtige Antwort zurück, nämlich:

$H(\langle M\rangle, i)$gibt genau dann true zurück , wenn$M$ hält bei der Eingabe an $i$.

Angenommen, es gibt eine solche Maschine $H$, wir können benutzen $H$ als Unterprogramm zum Erstellen eines Programms $P$ wie folgt:

Spezifikation des "perversen" Programms $P$

$P$ nimmt als Eingabe eine Beschreibung, $\langle M\rangle$einer Maschine $M$.

$P$funktioniert bei jeder Eingabe korrekt$\langle M\rangle$nämlich

$P(\langle M\rangle)$ hält genau dann an, wenn $M$ stoppt nicht bei Eingabe $\langle M\rangle$.

Der Schlüssel zu diesem Argument ist, wenn wir eine Maschine definieren können$H$dass satiffies die Spezifikation oben, dann können wir eine Maschine bauen$P$ das erfüllt die zweite Spezifikation.

Jedoch, $P$wenn gegeben $\langle P\rangle$zeigt unmögliches Verhalten,

$\qquad\qquad\qquad P(\langle P\rangle)$ hält genau dann an, wenn $P(\langle P\rangle)$ hört nicht auf

Damit $P$erfüllt nicht seine zweite Anforderung an mindestens einen Eingang und folglich muss es der Fall sein, dass$H$ kann seine Anforderung nicht erfüllen, daher können wir folglich nicht machen $H$ wie angegeben.

Jetzt $H$ kann sich sehr gut so verhalten, wie es bei vielen Eingaben angegeben ist $(\langle M\rangle, i)$Der Punkt ist jedoch, dass kein Stopp-Tester erstellt werden kann, der mit allen möglichen Eingaben funktioniert .

So könnte ein Logiker das Problem angehen:

$h(M,i)$ ist per Definition die allgemeine Falllösung für das Halting-Problem.

$(1)$ $h(M, i)$ muss feststellen können, ob oder nicht$M$hält für alle an $M$(dh eine uneingeschränkte Menge von$M$ ).

$p(M)$ ist ein Element in $M$.

$(2)$ Die folgenden Aussagen sind äquivalent:

• $p(M)$ hält genau dann an, wenn $h(M,M)$ kehrt zurück $false$
• $p(M)$ hält genau dann an, wenn $p(M)$ hört nicht auf

$(3)$ Darüber hinaus sind die folgenden Aussagen gleichwertig:

• $p(M)$ hört nicht genau dann auf, wenn $h(M,M)$ kehrt zurück $true$
• $p(M)$ hört nicht genau dann auf, wenn $p(M)$ hält an

Beide $(2)$ und $(3)$ sind Widersprüche.

$h(M,i)$- Die allgemeine Falllösung für das Halteproblem - kann nicht richtig bestimmen, ob$p(M)$ hält an, widerspricht $(1)$. Daher gibt es keine allgemeine Falllösung für das Halteproblem.

Du sagst:

Der Teil, mit dem ich Probleme habe, ist die Implementierung $p(M)$ damit es nicht aufhört wann $h(M,M)$ ist $true$. Mein Bauch versteht diesen Ansatz wie folgt:

Eine Methode gegeben $h()$ das funktioniert und eine Methode $p()$ entworfen, um zu brechen $h()$Wenn wir diese Methoden kombinieren, um eine Maschine zu bauen, ist diese Maschine kaputt.

Das Problem ist, dass $p()$ ist NICHT zum Brechen ausgelegt $h()$ist es konzipiert, um zu verwenden $h()$- und die Nutzung ist gültig UND funktioniert! Außer, es funktioniert nicht, wenn die Eingabe ist$p()$, was beweist, dass es nicht für alle Eingaben funktioniert .

Was bedeutet, dass $h()$ existiert bestenfalls nicht $hminus()$existiert. Das ist nicht wichtig$p()$ ist kaputt, wichtig ist das $h()$ existiert nicht.

Wenn jemand sagt, dass er geschrieben hat $h()$ Sie wissen, dass sie sich irren oder lügen, wenn sie daran arbeiten wollen $h()$ Sie verschwenden dein Geld und so weiter.

Es legt Grenzen für das fest, was entschieden werden kann und was nicht und welche Ressourcen dafür benötigt werden.

Wenn jemand die Frage stellt: Können wir feststellen, ob $p()$hält bei dieser Eingabe an? Die möglichen Antworten darauf sind: (a) ja - es tut, (b) ja - es tut nicht (c) ja - aber wir wissen derzeit nicht, ob es tut oder nicht und schließlich (d) nein - es ist unmöglich, den einen oder anderen Weg zu beweisen.

Es kann äußerst nützlich sein, schnell feststellen zu können, ob die Antwort (c) oder (d) lautet. Denken Sie daran, Halting sagt nicht, dass wir ein bestimmtes nicht beweisen können$p()$Halting, Halting sagt, wir können keine allgemeine Lösung haben, die für jede Eingabe funktioniert. Beschränken Sie entweder$p()$ oder die Eingabe und die Antwort ist ziemlich häufig ja, das ist trivial.

Sie sollten nicht mit "Zerbrochenheit" darüber nachdenken, da es eine Vielzahl von absolut legitimen Programmen gibt, die für immer ausgeführt werden sollen. Daher ist es nicht unbedingt "kaputt", für immer zu laufen.

pist der folgende einfache Algorithmus, vorausgesetzt, wir haben bereits eine Funktion h(X,Y), die zurückgibt, truewenn die Maschine Xmit der Eingabe anhält, Yund zurückgibt, falsewenn dies nicht der Fall ist.

function p(M)
    if (h(M,M)) then
        while (true) do
        endwhile;
    return;

Es gibt einen weiteren Beweis durch Widerspruch, den Sie vielleicht besser mögen, nach dem Vorbild von Berrys Paradoxon. Für eine Turingmaschine$T$, Lassen $N(T)$die Ausgabe der Turing-Maschine sein, wenn sie auf einem leeren Band ausgeführt wird, interpretiert als Zahl; möglicherweise$N(T)$ist undefiniert, wenn die Maschine nie anhält. Lassen$X_n$ sei die kleinste Zahl, die von einer Turingmaschine höchstens nicht produziert werden kann $n$Zustände (eine solche Anzahl existiert, da es endlich viele solcher Turingmaschinen gibt). Angenommen, das Halteproblem wäre lösbar. Dann könnten wir eine Turing-Maschine konstruieren, die den folgenden Algorithmus implementiert:

1. Schreiben Sie die binäre Codierung von $n$ auf dem Band.
2. Gehen Sie alle Turingmaschinen mit höchstens durch $n$ Berechnen Sie für jeden von ihnen, der anhält, die Zahl, die sie berechnen.
3. Geben Sie die kleinste Zahl aus, die in Schritt 2 nicht angezeigt wird $X_n$.

Die letzten beiden Stufen können unter Verwendung einer festen Turingmaschine mit implementiert werden $C$ Staaten, und die erste mit einem Extra $\log_2 n$Zustände. Insgesamt erhalten wir eine Turingmaschine mit$\log_2 n + C$ Zustände, die berechnen $X_n$. Wann$n$ groß genug ist, erreichen wir seitdem einen Widerspruch $\log_2 n + C \leq n$: Auf der einen Seite, $X_n$ sollte nicht mit einer Turing-Maschine berechenbar sein $n$Zustände; Auf der anderen Seite berechnet die obige Maschine dies nur mit$\log_2 n + C \leq n$ Zustände.

Ich habe diesen Beweis von Ran Raz gehört .

Der Punkt des Halteproblems besteht darin, dass es mit einem Algorithmus unmöglich ist, zu entscheiden, ob ein gegebener Algorithmus anhält. Natürlich können Sie Algorithmen angeben, die immer anhalten (für alle gegebenen Eingaben). Sie können dies jedoch nicht für alle Algorithmen entscheiden (z. B.)$p$) mit einem Algorithmus, daher kein Algorithmus $h$ kann existieren.

Gegeben $p(p(A)))$für einen gegebenen Algorithmus $A$. Wenn$h$ sagt Ihnen $A$ hält an, dann das innere $p$ wird nicht und die äußere $p$ wird false zurückgeben. Wenn$M$ hält das Innere nicht auf $p$ wird nicht aufhören, sondern die äußere $p$ wird false zurückgeben. Daher kann h nicht entscheiden, ob p anhalten wird.