Ist es entscheidend, ob ein TM eine Position auf dem Band erreicht?

14

Ich habe diese Fragen aus einer alten Prüfung, die ich zu lösen versuche. Für jedes Problem ist die Eingabe eine Codierung einiger Turing Maschine M .

Für eine ganze Zahl c>1 und die folgenden drei Probleme:

  1. Stimmt es, dass M für jede Eingabe x die nicht übergibt ? x | + c|x|+c Position beim Laufen auf x ?

  2. xmax{|x|c,1}x

  3. Stimmt es, dass M für jede Eingabe nicht die Position überschreitet, wenn es auf läuft ?x(|x|+1)/cx

Wie viele Probleme sind entscheidbar?

Problem Nummer (1) befindet sich meiner Meinung nach in wenn ich das richtig verstehe, kann ich alle Eingaben parallel ausführen und stoppen, wenn einige Eingaben diese Position erreicht haben, und um zu zeigen, dass dies nicht der in kann ich das Komplement von Atm darauf reduzieren . Ich konstruiere eine Turing-Maschine wie folgt: für eine Eingabe überprüfe ich, ob eine Berechnungshistorie ist, wenn ja, dann läuft richtig und hört nicht auf, wenn nicht, dann hört es auf.coRERRMyyM

Für (3) glaube ich, dass es entscheidend ist, da für alle Turing-Maschinen immer in der ersten Zelle des Streifens bleiben, da sie für eine Zeichenfolge die erste Zelle passieren können, also ich müssen alle Zeichenfolgen der Länge 1 für Schritte simulieren (Ist das richtig?) und prüfen, ob ich nur die erste Zelle in allen Schritten verwende.c2|Q|+1

Ich weiß nicht wirklich, was ich damit anfangen soll (2).

Jozef
quelle
1) Nehmen Sie ein einseitiges Endlosband an? 2) Was ist ATM?
Raphael
1) Ja, 2) das Akzeptanzproblem.
Jozef

Antworten:

9

Jede Situation, in der gefragt wird, ob eine Turing-Maschine auf einen endlichen Abschnitt des Bandes (z. B. mit der Länge ) bei einer bestimmten Eingabe beschränkt ist, ist entscheidbar.n

Das Argument funktioniert wie folgt. Betrachten Sie die Turingmaschine, das Band und die Position der Turingmaschine auf dem Band. Insgesamt haben diese eine endliche Anzahl von Konfigurationen. Konkret gibt es nur mögliche Konfigurationen. Γ ist die Menge der Bandsymbole und Q ist die Menge der Zustände. Ich werde das Wort "Konfiguration" weiterhin verwenden, um den Zustand der Turing-Maschine in Kombination mit dem Zustand des Bandes und seiner Position auf dem Band für den Rest dieser Antwort zu beschreiben, aber das ist kein Standardvokabular.t=n|Γ|n|Q|ΓQ

Führen Sie die Maschine aus und behalten Sie alle früheren Konfigurationen im Auge. Wenn es jemals über Punkt hinausgeht , geben Sie "Ja, M passiert Position n " zurück. Ansonsten liegt die Maschine irgendwo zwischen 0 und . Wenn die Maschine jemals eine Konfiguration wiederholt - ihr Status, die Symbole auf dem Band und ihre Position auf dem Band stimmen mit den vorherigen überein - geben Sie "nein, M passiert Position n nie " zurück.nMnnMn

Nach dem Pidgeonhole-Prinzip muss dies in nicht mehr als Schritten geschehen . Alles oben Genannte ist also entscheidend. nach maximal t + 1 simulierten schritten erhalten sie eine antwort.t+1t+1

Ein kurzer Hinweis zur Funktionsweise: Wenn sich die Maschine, das Band und seine Position auf dem Band wiederholen, muss zwischen diesen Wiederholungen eine Folge von Konfigurationen liegen. Diese Sequenz wird erneut ausgeführt und führt ein weiteres Mal zu derselben Konfiguration - die Maschine befindet sich in einer Endlosschleife. Das liegt daran, dass wir jeden Aspekt der Turing-Maschine im Auge behalten. Nichts außerhalb der Konfiguration kann sich auf das Geschehen auswirken. Wenn sich eine Konfiguration wiederholt, wird sie erneut wiederholt, mit einer identischen Reihe von Konfigurationen dazwischen.

Es ist also entscheidend, das Band auf einen endlichen Teil der Zeichenfolge zu beschränken. Wenn alle möglichen Eingabezeichenfolgen , liegt das Problem daher für alle drei Fragen in KOR . Sie haben dies vielleicht bereits erkannt (zwischen Ihren Ideen für 1 und 3 und Ran Gs Antwort für 2 scheint es sowieso vollständig gelöst zu sein), aber ich dachte, es könnte sich dennoch lohnen, etwas zu posten.coRE

SamM
quelle
"Wenn die Maschine jemals eine Konfiguration wiederholt, [...] geben Sie" nein "zurück - das ist falsch. Eine nicht deterministische Maschine führt möglicherweise mehrmals eine Schleife aus und fährt dann fort.
Raphael
1
Wir sprechen hier von Turingmaschinen, von denen nicht angenommen wird, dass sie nicht deterministisch sind. Wenn es nicht deterministisch wäre, simulieren Sie die deterministische Version.
SamM
Gute Erklärung. Siehe auch die erste Version meiner Antwort (die ich überarbeite, sobald ich feststellte, dass das OP nicht ganz danach gefragt hat ..)
Ran G.
@Sam: Es funktioniert umgekehrt: Wenn nicht anders angenommen, kann eine Turing-Maschine nicht deterministisch sein. Was ist eine "deterministische Version"? Wenn Sie eine vollständige Entfaltung der Auswahl meinen, verliert eine wiederholte Konfiguration an Bedeutung, da sie in verschiedenen Zweigen auftreten kann.
Raphael
2
@Raphael Die Standardmethode hierfür ist ein Konfigurationsdiagramm: Die Scheitelpunkte sind dieselben Konfigurationen, die Sam definiert hat, und es gibt eine gerichtete Kante von Konfiguration A nach B, wenn der NTM in einem einzigen Schritt von A nach B wechseln kann. Das Diagramm ist endlich und und ob die Maschine anhält, ist eine einfache Frage zur Erreichbarkeit des Diagramms. Dies zeigt auch, dass eine Teilmenge von D T I M E ( 2 O ( s ) ) istNSPACE(s)DTIME(2O(s))
Sasho Nikolov
4

(2) ist (3) sehr ähnlich, und die gleiche Überlegung, die Sie für (3) hatten, gilt auch hier: Beachten Sie, dass Maschinen in eine seltsame Eigenschaft haben - sie lesen nicht die gesamte Eingabe (sie erreichen sie nie) letzte c Bits.) Und das gilt für jede Eingabe.L2c

Ok, nun betrachten wir nur Eingaben bis zur Länge . Für jede von ihnen gibt es nur zwei Optionen: Die Maschine hält an, ohne den Kopf zu bewegen, oder sie bewegt den Kopf. Wenn es den Kopf um ein x bewegt (mit | x |c ), befindet sich diese Maschine aufgrund dieser Eingabe x nicht in L 2 . Ansonsten behaupte ich, die Maschine sei in L 2 . Da es niemals den Kopf bewegt, hat es keine Ahnung, wie groß die Eingabe ist! Dies bedeutet, dass es sich für alle Eingaben der Länge | gleich verhält x | > c . Daher L 2 entscheidbar ist.cx|x|cL2xL2|x|>cL2

Ran G.
quelle
Wie rechnen Sie nicht deterministische Maschinen ab?
Raphael
Ich habe NTMs nicht in Betracht gezogen, aber es sollte ziemlich gleich sein. Für alle Wörter mit einer Länge bis zu die Anzahl der Konfigurationen, in denen sich das NTM befinden kann, ohne dass der Kopf bewegt wird, endlich. c
Ran G.
Ja, aber dein Argument geht kaputt. Sie können nicht in endlicher Zeit (durch einfache Simulation) feststellen, ob ein NTM eine bestimmte Position verlässt.
Raphael
|x|exp(|x|)
|x||Q|M