Warum ist das Halteproblem für LBA entscheidbar?

Ich habe in Wikipedia und einigen anderen Texten gelesen, dass

Das Problem des Anhaltens ist für [...] linear begrenzte Automaten (LBAs) und deterministische Maschinen mit endlichem Speicher [...] entscheidbar .

Aber früher steht geschrieben, dass das Halteproblem ein unentscheidbares Problem ist und daher kann TM es nicht lösen! Da LBA als eine Art von TM definiert sind, sollte dasselbe nicht für sie gelten?

turing-machines automata undecidability halting-problem linear-bounded-automata user5507
quelle

Mit einem TM können Sie feststellen, ob eine LBA an einer bestimmten Eingabe anhält, indem Sie durch Simulation prüfen, ob sie beispielsweise in O (2 ^ 2 ^ n) Schritten anhält. Jeder LBA, der länger arbeitet, steckt in einer Endlosschleife. Das heißt nicht, dass LBAs das Halteproblem für allgemeine TMs lösen können!

Yonatan N

Endliche Automaten sind ebenfalls eine Art von TM.

Raphael

@Raphael Sie können solche Fragen nicht bearbeiten. Sie haben die Bedeutung der Frage geändert, sodass meine vorhandene Antwort nicht mehr zum Thema gehört, während die andere Antwort nicht mehr zum Thema gehört und jetzt zum Thema gehört.

Babou

@babou Ich sehe nicht, wie ich die Bedeutung der Frage geändert habe, und ich sehe nicht, wie eine der beiden Fragen die Frage nicht beantwortet hat (obwohl sie unterschiedliche Ansätze verwenden).

Raphael

@Rap Bei der ursprünglichen Frage geht es mehr um den logischen Diskurs als um die formale Rechtfertigung von LBA-Eigenschaften, und das haben Sie aus dem Titel entfernt. Für mich ist klar, dass das OP, auch wenn nachgewiesen werden kann, dass das Anhalten für LBAs entscheidend ist, sich fragt, wie es mit anderen Aussagen in Bezug auf die Einbeziehung von LBAs in TMs und die Unentscheidbarkeit des Anhaltens für TMs vereinbar ist (kann ich zurückschneiden?). . Übrigens keine Absicht, Yuvals Antwort herabzusetzen. Ich gehe davon aus, dass er die meisten Stimmen bekommt, denn danach strebt die Leserschaft (was an sich ein pädagogisches Problem ist), auch wenn ich mich nicht hingeben werde.

Babou

Antworten:

$S$ $A$ $Q$ $QSA^S$ $QSA^S$ $QSA^S$ Schritte und sehen, ob es innerhalb dieses Zeitrahmens anhält.

Yuval Filmus
quelle

Warum funktioniert dieses Argument für nicht deterministische Maschinen?

Raphael

Aufgrund des Satzes von Savitch.

Yuval Filmus

Ich kannte (oder erinnere mich nicht) von Savitchs Theorem außer dem Namen (ich habe nie viel Komplexität gemacht). Ich bin mir jedoch nicht sicher, ob es so verwendet werden kann, da es für Entscheidungsverfahren, dh das Anhalten von Berechnungen, gilt, während die Entscheidbarkeit des Anhaltens genau das ist, was bewiesen werden muss. Der Beweis könnte angepasst werden, um raumgebundene Halbentscheidungen einzuschließen, aber es scheint einfacher zu sein, getrennt zu beweisen, dass das Anhalten für raumgebundenes TM entscheidbar ist, wodurch raumgebundene Halbentscheidungen in vollständige Entscheidungen umgewandelt werden. Dies entspricht in etwa der Vorgehensweise von Hopcroft-Ullman-79 in ihrem Lemma 12-1, bevor der Satz von Savitch bewiesen wird.

Babou

Ich könnte es sein, dass ich das missverstehe, aber ist die Antwort, das Programm buchstäblich auszuführen und zu prüfen, ob es in einer Endlosschleife steckt oder nicht?

Mikayla Maki

@TrentonMaki Ja, das ist genau so.

Yuval Filmus

Sie scheinen mit einem logischen Problem festzustehen.

Aus der Tatsache, dass es Bücher gibt, die Sie nicht lesen können, können Sie nicht schließen, dass Sie kein Buch lesen können.

Zu sagen, dass das Problem des Anhaltens für Turing Machines (TM) nicht entschieden werden kann, bedeutet nur, dass es Maschinen gibt, für die es keine Möglichkeit gibt, durch ein einheitliches Verfahren zu bestimmen, ob sie anhalten oder nicht, das immer anhält.

Es gibt jedoch Turingmaschinen, die anhalten. Nehmen Sie nun eine Untergruppe von Turing-Maschinen, die Nice Turing Machines (NTM) genannt wird, so dass sie nur Turing-Maschinen enthält, die genau dann anhalten, wenn das Band eine gerade Anzahl von Symbolen enthält. Wenn bekannt ist, dass eine Maschine M aus dieser Gruppe stammt, können Sie auf einfache Weise entscheiden, ob M anhält: Sie überprüfen, ob die Anzahl der Bandsymbole gerade ist (es sind nur zwei Finger erforderlich).

Diese Prozedur funktioniert jedoch nicht für TM, die nicht im NTM-Satz enthalten sind. (schade!)

Das Problem des Anhaltens ist also für das NTM entscheidend, nicht jedoch für das TM im Allgemeinen, obwohl das NTM-Set im TM-Set enthalten ist.

Dies ist tatsächlich kritisch und wird manchmal vergessen, wenn das Unentscheidbarkeitsergebnis interpretiert wird.

Es kann durchaus sein, dass man beweisen kann, dass eine wichtige Eigenschaft für eine sehr große Familie mathematischer oder rechnerischer Objekte unentscheidbar ist.

Das bedeutet nicht, dass Sie aufhören sollten, nach einer Lösung zu suchen, sondern nur, dass Sie keine für die ganze Familie finden.

Sie können dann relevante Unterfamilien identifizieren, für die die Lösung des Problems weiterhin wichtig ist, und versuchen, Algorithmen bereitzustellen, um zu entscheiden, ob die Eigenschaft für Mitglieder dieser kleineren Familie gilt.

In der Regel ist das Anhalten für TM im Allgemeinen unentscheidbar, für große und nützliche Familien von Automaten, die alle als Sonderfälle von TM angesehen werden können, ist es jedoch oft sehr einfach zu entscheiden.

babou
quelle

"Zu sagen, dass das Problem des Anhaltens für Turing Machines (TM) nicht entschieden werden kann, bedeutet nur, dass es Maschinen gibt, für die es keine Möglichkeit gibt, durch ein Verfahren zu bestimmen, ob sie anhalten oder nicht, das immer anhält." - Nicht ganz richtig. Für jedes gegebene TM ist das Halteproblem entscheidbar. Es ist die allgemeine Entscheidung Problem , das unentscheidbar ist, dh es gibt keinen ein Algorithmus, der sich mit allen TMs. (Ich denke, dies muss für Anfänger sehr, sehr deutlich gemacht werden. Siehe das Pi-Problem .)

Raphael

Ein unmittelbares Beispiel ist die Menge aller TMs, die immer gültig sind. Deines fügt etwas mehr Geschmack hinzu, weil es außerhalb der normalen Hierarchie liegt.

Raphael

Richtig. Ich hätte "einheitliche Prozedur" sagen sollen, aber es war implizit in meinem Kopf, als ich "Prozedur, die immer anhält" sagte. Es ist jedoch richtig, dass eine Prozedur für eine Maschine korrekt funktioniert und für andere Maschinen alles tun kann. Nun ... - - - - - - - Was den zweiten Kommentar betrifft, habe ich zuerst geschrieben. Ich habe es mir dann anders überlegt, weil ich dachte, mein Beispiel wäre intuitiv leichter zu verstehen, da die Auswahl der Maschinen nicht so direkt von der zu entscheidenden Eigenschaft abhängt (obwohl es eng ist).

Babou

Kurz gesagt, A LBA hat eine endliche Anzahl von Konfigurationen, z. B. D. Daher können wir D-Schritte ausführen und das Ergebnis abschließen. Läuft es mehr als D-Schritte, so kann man nach dem Pigeonhole-Prinzip sagen, es steckt in einer Endlosschleife.

SiluPanda
quelle

Was bedeutet dies für die bestehende Antwort ? Dies scheint es nur zu wiederholen, weniger detailliert. Ich weiß zwar zu schätzen, dass Sie versuchen, einen Beitrag zu leisten, wir möchten jedoch vermeiden, dass vorhandene Antworten wiederholt werden, und uns stattdessen auf die Beantwortung von Fragen konzentrieren, die noch keine gute Antwort haben.