Warum ist das Halteproblem halb entscheidbar?

7

Dies ist bekannt über das Halteproblem und die Halbentscheidbarkeit:

Das Halteproblem besagt, dass wir für eine gegebene Eingabe x und eine Maschine H nicht sagen können, ob die Maschine H bei Eingabe x anhält oder nicht.

Eine Sprache gilt als halbentscheidbar, wenn es eine Turing-Maschine gibt, die anhält, wenn ein Wort zur Sprache gehört (JA-Fälle), und kann ablehnen oder in eine Endlosschleife gehen, wenn das Wort nicht zur Sprache gehört (KEIN Fall). .

Nun können wir beim Anhalten des Problems nicht sagen, ob die Maschine anhält, selbst wenn die Eingabe zur Sprache gehört (JA-Fälle). Wie ist es dann halbentscheidbar? Ich denke, es sollte nicht rekursiv aufzählbar oder unentscheidbar sein.

computability turing-machines halting-problem semi-decidability Zephyr
quelle
"Jetzt können wir beim Anhalten des Problems nicht sagen, ob die Maschine anhält, selbst wenn die Eingabe zur Sprache gehört." Warum nicht? Die Maschine muss anhalten, um das Wort zu akzeptieren. Ich bin mir auch nicht sicher, ob es so etwas wie halbentscheidbar gibt. Ich weiß nur entscheidbar oder unentscheidbar. Das Problem des Anhaltens ist unentscheidbar.
Benutzer nicht gefunden
2
Beachten Sie, dass dies überhaupt nichts mit dem Turing-Test zu tun hat.
Raphael
@ArghyaChakraborty Halbentscheidbar bedeutet, dass für jedes Problem eine Turing-Maschine für dieses Problem vorhanden ist, die immer für akzeptierte Eingaben beendet wird, aber für alle anderen Eingaben entweder beendet wird oder nicht. (Ups, ich habe gerade bemerkt, dass OP es geschrieben hat), aber es ist eine Sache.
Micrified
@Owatch Ok, jetzt verwirrst du mich ... ist die nächste Aussage wahr? "Jetzt können wir beim Anhalten des Problems nicht sagen, ob die Maschine angehalten wird, selbst wenn die Eingabe zur Sprache gehört"
Benutzer nicht gefunden
@ArghyaChakraborty Ich sage Ihnen nur, dass der Begriff "halbentscheidbar" gültig ist und wie das OP ihn definiert hat. Wenn Sie mich nach dem Problem des Anhaltens in Bezug auf dieses Wort fragen möchten, kann ich das wohl auch beantworten. "Beim Anhalten des Problems können wir nicht sagen, ob die Maschine angehalten wird, selbst wenn die Eingabe zur Sprache gehört": False. Jede Maschine in der Haltesprache wird immer für Eingaben beendet, die zur Sprache gehören.
Micrified

Antworten:

15

Tl; dr: "(sagen) ob es anhält oder nicht" und "(sagen) ob es anhält" sind nicht dasselbe. Verwenden Sie Mathematik, um Verwirrung durch Sprachmehrdeutigkeit zu vermeiden.

Das Halteproblem besagt, dass wir für eine gegebene Eingabe x und eine Maschine H nicht sagen können, ob die Maschine H an der Eingabe x anhält oder nicht.

Nein, das steht nicht. Das Halteproblem ist das Rechenproblem der Entscheidung, ob auf anhält , wenn und als Eingabe gegeben sind. Es ist wichtig zu beachten, dass "entscheiden" hier "Ja sagen, wenn es so ist, und Nein sagen, wenn es nicht ist" bedeutet.H.xxH.

Die Unentscheidbarkeit des Stoppproblems besagt, dass es keinen einzelnen Algorithmus (Turing-Maschine) gibt, der das Stoppproblem für alle und löst .H.x

Beim Anhalten des Problems können wir nicht sagen, ob die Maschine angehalten wird, selbst wenn die Eingabe zur Sprache gehört (JA-Fälle). Wie ist es dann halbentscheidbar?

Nach der obigen Klarstellung sollte Ihre Verwirrung hier klar sein. Es ist egal, was "wir sagen können". Das "Semi-Stopping-Problem" ist gelockert: Der Algorithmus muss immer noch "Ja" sagen, wenn auf anhält , aber er kann tun, was er will, wenn dies nicht der Fall ist (außer Antwort "Ja").H.x

Dies ist trivial zu implementieren: Führen Sie einfach aufH.x. Wenn es anhält, antworten Sie mit "Ja". Wenn nicht, spielt es keine Rolle, da wir eine Schleife durchführen dürfen.

Raphael
quelle
Die Aussage, die ich über das Anhalten des Problems schrieb, betraf also tatsächlich die Unentscheidbarkeit des Anhaltens des Problems? Nach Ihrer Meinung ist das Problem des Halbstopps rekursiv aufzählbar und daher halbentscheidbar. Ist das eigentliche Halteproblem also unentscheidbar und nicht halbentscheidbar? Es tut mir leid, wenn ich triviale Fragen stelle, ich bin neu in diesem Bereich.
Zephyr
"Also war die Aussage, die ich über das Anhalten des Problems schrieb, tatsächlich über die Unentscheidbarkeit des Anhaltens des Problems?" -- Ja. In TCS ist "Problem" ein technisches, nicht mit dem normalen englischen Wort zu verwechseln. Siehe auch hier . "Ist das eigentliche Halteproblem also unentscheidbar und nicht halbentscheidbar?" - Nein. Ich bin dort ein wenig informell gewesen (daher die Anführungszeichen): Es ist das Halteproblem, aber ausgedrückt als Halbentscheidbarkeit. Das Stoppproblem ist unentscheidbar, aber halbentscheidbar.
Raphael
Nach Ihren Aussagen zur Unentscheidbarkeit gibt es keinen Algorithmus, der das Halteproblem für alle H und x löst. Dies bedeutet, dass kein Algorithmus entscheiden kann, ob H auf x anhält, wenn x und H als Eingabe angegeben werden. Selbst wenn wir eine Eingabe geben, die zur Sprache gehört, kann der Algorithmus nicht entscheiden, ob er anhält, so dass er völlig unentscheidbar sein sollte.
Zephyr
1
Es gibt kein "völlig unentscheidbares". Und nein, kein Algorithmus kann entscheiden , aber er kann immer noch halb entscheiden. Dies sind verschiedene Begriffe; Sie sollten die formalen Definitionen überprüfen. Intuitive Analogie: Bis nach Ihrem Tod können Sie niemals mit Zuversicht sagen, dass "niemals ein Maulwurf auf meinen Kopf kacken wird". Aber wenn es passiert, können Sie mit absoluter Sicherheit sagen: "Ein Maulwurf hat auf meinen Kopf gekackt".
Raphael
4
Wenn die Frage des Anhaltens unentscheidbar ist, heißt das nicht, dass ich manchmal nicht entscheiden kann, ob es anhält. Zum Anhalten von Instanzen kann ich entscheiden, dass sie angehalten werden, indem ich nur warte, bis sie angehalten werden. In Fällen, in denen nicht angehalten wird, kann ich manchmal den Beweis erbringen, dass sie nicht angehalten werden, und das entscheidet über sie.
Gnasher729