Ich bin in diesem PDF auf das folgende Problem gestoßen:
Bei einem TM M, ob M jemals ein nicht leeres Symbol schreibt, wenn es auf dem leeren Band gestartet wird.
Die angegebene Lösung lautet wie folgt:
Lassen Sie die Maschine nur leer schreiben Symbol. Dann ist seine Anzahl von Konfigurationen in der Com-Berechnung auf w q × 2, wobei q die Anzahl von Zuständen von M ist; Der Faktor 2 ist für die Auswahl bezüglich. die Richtung der Kopfbewegung; Es gibt keinen Faktor für das geschriebene Symbol, da dieses immer leer ist. Das Problem ist also entscheidbar und wird von der folgenden Maschine entschieden: Eingabe (M, w), M auf w für q × 2 Schritte ausführen; Wenn es jemals ein nicht leeres Symbol schreibt, hören Sie mit Ja auf. Wenn M niemals ein nicht leeres Symbol schreibt, stoppen Sie ohne Antwort.
Zweifel:
Q1. Wie sicher ist, dass alle qx 2-Konfigurationen durchgeführt werden? beim Ausführen von qx 2 Schritte auf w? Einige Konfigurationen werden möglicherweise in zwei Schritten wiederholt.
Q2. Die Frage lautet „beim Starten am“ leeres Band „, aber die Antwort versuchte, TM auf einer nicht leeren Zeichenfolge w zu simulieren. Wie macht es Sinn?
Antwort
Q1: Ein Status kann wiederholt werden. Der Punkt ist, dass, wenn ein Zustand wiederholt wird und noch kein nicht leeres Symbol geschrieben wurde, Sie wissen, dass die Turing-Maschine niemals anhalten wird, da sie notwendigerweise beim Durchlaufen einiger der bisher angetroffenen Zustände stecken bleibt. Da keiner der Zustände des Zyklus dazu führte, dass das TM ein nicht leeres Symbol schrieb, schrieb das TM niemals ein nicht leeres Symbol.
Nach $ 2q $ Schritte, entweder wurde ein nicht leeres Symbol geschrieben und Sie können mit „Ja“ antworten, oder alle geschriebenen Symbole waren leer und (mindestens) ein Zustand muss zweimal oder mehrmals aufgetreten sein, was bedeutet, dass Sie können mit „Nein“ antworten.
F2: Ich vermute, dass $ w $ wird irgendwo als leere Zeichenfolge definiert. Wenn das TM mit einer beliebigen Zeichenfolge $ w $ gestartet werden kann, funktioniert eine Variation der obigen Lösung weiterhin. Angenommen, der Kopf des TM beginnt am Anfang von $ w $ . Die Anzahl der Zustände erhöht sich um einen Faktor von höchstens $ 1+ | w | $ , um alle möglichen Zustände des Bandes zu berücksichtigen (wenn nur leere Symbole geschrieben werden Dann enthält das Band immer eines der Suffixe $ 1+ | w | $ von $ w $ ). Wenn der Kopf irgendwo anfangen kann, ist dieser Faktor höchstens $ 1+ | w | ^ 2 $ .
Kommentare
- In Q1. Meinen Sie ", entweder wurde ein nicht leeres Symbol geschrieben, und Sie können ja antworten … und Sie können nein "? Weil die Frage " fragt, ob M jemals ein nicht leeres Symbol " schreibt. In Q2. " wurde nicht in der Anzahl der Zustände erhalten, die der Anzahl der Teilmengen von Positionen von w entsprechen, die durch ein leeres Symbol überschrieben wurden "
- Du hast recht. Ich habe meine Antwort korrigiert. Ich habe auch den letzten Teil klargestellt.