Stoppen Sie das Problem für die feste Turierungsmaschine und einen festen Eingang

Question

Es ist bekannt, dass das Halteproblem unentschieden ist, selbst wenn wir entweder die Turing-Maschine $ M $ oder Der Eingang $ W $ .

Was ist, wenn wir sowohl die Maschine als auch den Eingang behoben haben?Dh ist es für jede feste Turniermaschine $ M_0 $ und jeder feste Eingabe $ w_0 $ das $ M_0 $ hält auf $ w_0 $ als Input?

Answer 1

Es ist bekannt, dass das Halteproblem unentschieden ist, selbst wenn wir entweder die Turing-Maschine $ M $ oder Der Eingang $ W $ .

Sie müssen über diese Erklärung sorgfältiger sein. Es stimmt nicht für jede feste Turing-Maschine $ M $ dass das Halting-Problem $ \ Text {Halt} _m $ (Entscheiden von Eingang $ W $ Wenn $ M $ auf $ W $ ) ist unentschlossen. Wenn beispielsweise $ M $ eine Maschine ist, die immer hält, können wir leicht entscheiden, $ \ Text {Halt} _m $ nur indem Sie "Ja" ausgeben.

Was Sie wahrscheinlich sagen wollten, ist die folgenden Fakten, die wahr sind:

.

1. gibt es eine Turing-Maschine $ M $ so, dass das Problem $ \ text {halt} _m $ (entscheiden Sie sich an Input $ W $ Wenn $ M $ Hält auf $ W $ ) ist unentschlossen.

2. für alle Wörter $ W $ , das Problem $ \ Text { Halt} _w $ (entscheiden Sie sich für Eingabe $ M $ Wenn $ M $ auf < Span-Klasse="Math-Container"> $ W $ ) ist unentschlossen.

Insbesondere für die Tatsache 1, können wir $ M $ als Universal-Turing-Maschine annehmen.

Was ist, wenn wir sowohl die Maschine als auch den Eingang behoben haben? Dh ist es für jede feste Turniermaschine $ M_0 $ und jeder feste Eingabe $ w_0 $ das < Span-Klasse="Math-Container"> $ M_0 $ hält auf $ w_0 $ als Input?

Ja, das Problem wird trivial enttäuschbar. Definieren Sie die Sprache $ \ Text {Halt} _ {m_0, w_0} $ Um das Problem zu entscheiden, ob $ M_0 $ hält auf $ w_0 $ . Beachten Sie jedoch, dass dieses Problem keine Eingabe mehr hat, dass die Antwort von der Antwort abhängt, da beide Dinge, die die Antwort von der Antwort von der Antwort abhängen kann ( $ M_0 $ und $ w_0 $ ) sind jetzt fixiert, dh Teil der Sprachdefinition, nicht Teil der Eingabe. Das bedeutet, dass die Antwort nur "Ja" oder "Nein" ist. So können wir dieses Problem also entscheiden, entweder mit einem Programm, das immer "Ja", oder ein Programm, das immer "Nein" sagt.

Dies ist eine häufige Fallstricke über die Entmindung: Es ist nur nützlich, um zu fragen, ob ein Problem entschieden ist oder nicht, wenn die Anzahl der möglichen Eingänge unendlich ist. Wenn es nur endlich viele mögliche Eingaben gibt, dann Alle Probleme werden enttäuschbar. Sie haben gefragt, ob ein Problem mit nur einer möglichen Eingabe (der leere Eingabe) entschieden ist, und die Antwort darauf ist immer ja.