Eine Frage zu einer Turingmaschine mit einem nutzlosen Zustand

OK, hier ist eine Frage aus einem früheren Test in meiner Klasse "Theorie der Berechnung":

Ein nutzloser Zustand in einem TM ist ein Zustand, der niemals in eine Eingabezeichenfolge eingegeben wird. Es sei Beweisen Sie, dass unentscheidbar ist.U S E L E S S T

$$\mathrm{USELESS}_{\mathrm{TM}} = \{\langle M, q \rangle \mid q \text{ is a useless state in }M\}.$$ $\mathrm{USELESS}_{\mathrm{TM}}$

Ich glaube, ich habe eine Antwort, bin mir aber nicht sicher, ob sie richtig ist. Wird es in den Antwortbereich aufnehmen.

Dies ist aus dem Halteproblem eindeutig reduzierbar. Wenn eine Maschine am Eingang nicht stoppt, ist jeder Endzustand "nutzlos". Bei einer Eingabe für das Halteproblem ist es einfach, zu konstruieren , das bei jeder Eingabe anhält (daher ist sein Endzustand nicht nutzlos), wenn und nur wenn bei anhält . Auf diese Weise können Sie das entscheiden, wenn Sie , was einen Widerspruch ergibt.x M , x M x M x U S E L E S S T $M$$x$$M,x$$M_x$$M$$x$$\mathrm{USELESS}_{\mathrm{TM}}$

Für die Zwecke dieses Beweises nehmen wir an, dass entscheidbar ist, einen Widerspruch anzuzeigen.$\mathrm{USELESS}_{\mathrm{TM}}$

Erstellen Sie TM , das Folgendes ausführt :$R$

• Konvertiert TM in einen Pushdown-Automaten mit einem entspannten Stapel (dh keine LIFO-Anforderung). Dies entspricht einem gerichteten Graphen, der den Übergang zwischen Zuständen detailliert .P $M$$P$$M$
• Markieren Sie den Startzustand von .$P$
• Beginnen Sie vom Startzustand an mit einer Breitensuche entlang jeder ausgehenden Kante, die jeden nicht markierten Knoten markiert.
• Wenn die Suche beendet wird und nicht markierte Knoten vorhanden sind, die mit übereinstimmen , akzeptieren Sie ; sonst ablehnen .$q$

Erstellen Sie dann TM = "On input $$$S$

1. Erstellen Sie TM wie oben gezeigt.$R$
2. Führen Sie auf .$q$$R$
3. Wenn akzeptiert zurückgibt, akzeptieren Sie ; wenn ablehnt, ablehnen " $R$$R$

Wenn also ein Entscheider für dann ist ein Entscheider für (das Akzeptanzproblem). Da sich als unentscheidbar erwiesen hat (siehe Michael Sipser Theory of Computation Theorem 4.11 auf Seite 174), haben wir einen Widerspruch erreicht. Daher ist die ursprüngliche Hypothese falsch und ist unentscheidbar.U S E L E S S T M S A T M A T M U S E L E S S T $R$$\mathrm{USELESS}_{\mathrm{TM}}$$S$$A_{\mathrm{TM}}$$A_{\mathrm{TM}}$$\mathrm{USELESS}_{\mathrm{TM}}$