Ist der Satz von Turing-Maschinen, der bei allen Eingaben in höchstens 50 Schritten stoppt, entscheidbar?

19

Sei . Ich muss entscheiden, ob F entscheidbar oder rekursiv aufzählbar ist. Ich denke, es ist entscheidend, aber ich weiß nicht, wie ich es beweisen soll.F={M:M is a TM which stops for every input in at most 50 steps}

Meine Gedanken

Dieser "50 Schritte" Teil dreht sofort das R- Zeichen für mich. Wenn es für eine bestimmte Eingabe wäre, wäre es entscheidbar. Hier ist es jedoch für jede Eingabe. Wenn ich es auf unendliche Eingaben überprüfe, denke ich, dass das Problem co-RE ist , dh, seine Ergänzung ist akzeptabel.

Vielleicht kann ich die Konfigurationen überprüfen und feststellen, dass alle Konfigurationen nach 50 Schritten nicht zum Akzeptieren führen. Wie mache ich das?

Jozef
quelle

Antworten:

21

Betrachten wir das allgemeinere Problem von Maschinen, die nach höchstens Schritten anhalten , für einige . (Das Folgende ist eine wesentliche Vereinfachung einer früheren Version dieser Antwort, ist jedoch praktisch gleichwertig.)NN1

Wie Swegi in einer früheren Antwort bemerkt , sind nur die Zellen auf dem Band signifikant , wenn die Maschine nach höchstens Schritten anhält . Dann genügt es, die Maschine auf allen Eingabezeichenfolgen der Form zu simulieren , von denen es eine endliche Zahl gibt.0 , 1 , , N - 1 MN0,1,,N1MxΣN

  • Wenn eine dieser Simulationen durch dasÜbergang bedeutet dies, dass jede Eingabezeichenfolge, die mit beginnt, eine Zeichenfolge ist, für die die Maschine nicht innerhalb der ersten Schritte anhält.NthNxN
  • Wenn alle diese Simulationen durch das anhaltenÜbergang, dann hält innerhalb von Schritten an allen Eingaben beliebiger Länge an (von denen die Teilzeichenfolge der Länge alles ist, worauf sie jemals einwirkt).NthN NMNN
Niel de Beaudrap
quelle
Und- Nehme ich an, dass , dessen Länge größer als ist, automatisch verworfen wird? NxN
Jozef
Warum kann es innerhalb der N Rechenschritte nicht zu mehr als N Zellen springen?
Jozef
@Jozef: die Simulationen nur durchlaufen alle möglichen Eingabezeichenfolgen der Länge N . Sie könnten weitere Zeichenfolgen durchlaufen, aber Sie werden nichts mehr lernen, da ohnehin nur die ersten N Symbole von Bedeutung sind. Der Grund, warum es nicht weiter als N Zellen gehen kann , ist, dass Turing-Maschinen (oder die Standarddefinition von ihnen) nur eine Zelle pro Schritt bewegen.
Niel de Beaudrap
Richtig, ich habe es verstanden. Sie kümmern sich also nur um die ersten N Symbole jedes Wortes, und Sie überprüfen alle Kombinationen davon. Warum haben Sie die Konfigurationsbeschreibung gelöscht?
Jozef
Es ist immer noch sichtbar, wenn Sie sich die vorherigen Änderungen ansehen. Ich habe es dahingehend überarbeitet, weil die andere Antwort vielleicht interessant war, aber vieles, was es "interessant" machte, diente nur dazu, die Tatsache zu verschleiern, dass die Entscheidungsprozedur nicht mehr oder weniger ist, als für alle möglichen Eingaben der Länge simulieren . Ich dachte, es wäre besser, die Antwort auf etwas viel Unkomplizierteres zu überarbeiten, und das hat im Grunde die Wurzel dessen, was das Problem entscheidbar macht. NMN
Niel de Beaudrap
4

Wenn in nicht mehr als 50 Schritten anhält, sind die Positionen, die auf dem normalerweise unendlichen Band erreichen kann, begrenzt. Somit kann das unendliche Band durch ein endliches simuliert werden. Dies bedeutet, dass das Band von einem endlichen Automaten simuliert werden kann. Daraus folgt, dass eine Turingmaschine , die in nicht mehr als 50 Schritten stoppt, einem endlichen Automaten ähnlich ist .M M M 'MMMM

Sei die Menge der Zustände von , die Menge der akzeptierenden Zustände und das Alphabet. Dann bauen wir die Menge der Zustände von wie folgt auf: wobei die Position des Lese- / Schreibkopfes über dem Band ist. Wir können die Position auf da die Anzahl der zulässigen Rechenschritte die Anzahl der erreichbaren Positionen begrenzt.M F Q Γ Q ' M ' Q ' = { n , q , s , p , a QMFQΓQMp { - 50 , . . . , 50 }Q={n,q,s,p,a|n{0,...,50}qQ,sΓ,p{50,...,50},aqF}p{50,...,50}

Ein Zustand des endlichen Automaten bedeutet dann, dass wir uns im Zustand des ursprünglichen Automaten befinden, mit auf dem Band an der Position wo sich auch der Lese- / Schreibkopf befindet positioniert ist, nach dem ten Rechenschritt. Der Zustand ist ein akzeptierender Zustand, wenn .M ' q s p n a t r u en,q,s,p,aMqspnatrue

Das Transformieren des Übergangsverhältnisses einer Betonwälzmaschine ist etwas aufwändiger, aber für die ursprüngliche Frage nicht erforderlich, da es ausreicht, um zu zeigen, dass der Zustandsraum endlich ist (und wir daher nur jeden Eingang mit einer Länge von höchstens 50 testen können Symbole auf jedem solchen Automaten). Die Idee ist, eine neue Übergangsrelation zu erstellen, die von einem Zustand in einen Zustand in geht der te Rechenschritt, wenn der Übergang in der ursprünglichen Übergangsrelation war.n + 1 , q ' , s ' , p ' , a 'n q , s , p q ' , s ' , p 'n,q,s,p,an+1,q,s,p,anq,s,pq,s,p

Swegi
quelle
Wie simulieren Sie die Speicherung auf dem Band, dh die Möglichkeit, bereits gelesene Symbole auf einem endlichen Automaten erneut aufzurufen?
Niel de Beaudrap
@NieldeBeaudrap: Sie zählen den gesamten Zustandsraum auf, dh Sie führen eine Modellprüfung des endlichen Bandes und des Kontrollautomaten der Turingmaschine durch.
Swegi
1
Angesichts der Tatsache, dass das OP grundlegende Fragen zur Berechenbarkeit von Turing-Maschinen stellt, möchten Sie diese Skizze möglicherweise in etwas vollständigeres packen. (Ich selbst habe den Ausdruck "Modellprüfung" noch nie zuvor in einem Computerkontext gehört.) Im Kontext würde ich typischer Weise annehmen, dass Sie mit "endlichem Automaten" einen DFA oder ähnliches meinen, sofern Sie nichts anderes angegeben haben, und mir ist nicht klar, was würde der Eingabe des DFA in einer solchen Konstruktion entsprechen. Wenn Sie nur ein Diagramm meinen, das mögliche Trajektorien des TM darstellt, dann stimme ich zu.
Niel de Beaudrap
Mit Modellprüfung des endlichen Teils des Bandes meine ich im Grunde das, was Sie in Ihrer Antwort geschrieben haben: Testen Sie einfach jede Eingabe mit einer Größe von höchstens 50 und prüfen Sie, ob ein akzeptierender Zustand erreicht ist.
Swegi
1
Ich wünschte, die Leute würden aufhören, den Mythos zu verbreiten, dass ein Turing-Maschinenband unendlich sein muss. Tut es nicht - es kann endlich sein, solange es nach Bedarf erweitert wird.
Reinierpost