Definieren des Halteproblems für nicht deterministische Automaten

18

Die primäre Definition von Turing machine (TM), zumindest in meinem eigenen Nachschlagewerk (Hopcroft + Ullman 1979), ist deterministisch.

Daher ist mein eigenes Verständnis des Halteproblems in erster Linie für deterministisches TM, obwohl mir bewusst ist, dass es für andere Arten von Automaten in Betracht gezogen werden kann.

Mir ist auch aufgefallen, dass Determinismus oft mehr oder weniger implizit in der Art und Weise ist, wie Menschen sich oft auf TM oder auf das Problem des Stillstands beziehen. Die Wikipedia-Seite zum Problem des Anhaltens ist ein gutes Beispiel dafür.

Es scheint jedoch keinen Grund für eine solche Einschränkung zu geben. Bei einer Familie von Automaten, die nicht deterministisch sein kann, kann das Halteproblem für folgt definiert werden: $\mathcal F$ $\mathcal F$

Gibt es eine einheitliche Entscheidungsprozedur, so dass bei gegebenem Automaten und einer Eingabe entschieden werden kann, ob eine Stopp-Berechnung von für die Eingabe . $A\in\mathcal F$ $x$ $A$ $x$

(Dies ist nicht ganz dasselbe wie zu sagen, dass die Berechnung von $A$ mit Eingabe $x$ beendet wird.)

Tatsächlich scheint dies die einzige Möglichkeit zu sein, Diskussionen über das Halteproblem von linear gebundenen Automaten ( Linear Bounded Automata, LBA), bei denen es sich in erster Linie um nicht deterministische Automaten handelt, sinnvoll zu gestalten .

Meine Frage ist also, ob ich richtig bin und ob es einen Grund (und welchen Grund) für diese anscheinend zweitklassige Behandlung des Halteproblems für nicht deterministische Automaten gibt.

turing-machines automata nondeterminism halting-problem linear-bounded-automata babou
quelle

Wenn Sie der Meinung sind, dass bei dieser Frage etwas nicht stimmt, teilen Sie uns dies bitte mit, damit wir alle von Ihrem Wissen profitieren und den Beitrag für alle Benutzer verbessern können. Vielen Dank.

Babou

12

Ich denke, es gibt ein paar Gründe, warum wir uns für nicht deterministische Modelle weniger mit dem Problem des Anhaltens befassen.

Das erste ist, dass es tatsächlich zwei relevante Halteprobleme für ein ND-Modell gibt. Bei einer Eingabe und einer nicht deterministischen Maschine : $x$ $M$

Gibt es einen gültigen Lauf von auf der anhält? $M$ $x$
Gibt es einen gültigen Lauf von auf der nicht anhält? dh halten alle gültigen läufe an? $M$ $x$

Für deterministische Maschinen sind diese identisch, da an einer Eingabe genau ein gültiger Lauf von vorliegt . Bei nicht deterministischen Maschinen kann es jedoch zu mehreren Durchläufen kommen. Welches Sie interessiert, hängt von Ihrer Anwendung ab. $M$ $x$

Zweitens sind nicht deterministische Modelle bereits unrealistisch: Sie setzen voraus, dass Sie entweder eine magische Box haben, die Ihnen den Weg zeigt, den Sie einschlagen müssen, oder dass Sie irgendeine Form von unendlicher Parallelität haben. Da nicht deterministische und deterministische Turing-Maschinen eine äquivalente Leistung haben, wandeln Sie die Maschine in den meisten Fällen einfach in eine deterministische um, bevor Sie sich Gedanken über das Anhalten machen.

Als eine Erweiterung davon ist es uns egal, weil es mindestens so schwer ist, etwas über eine nicht deterministische Maschine zu beweisen, wie etwas über eine äquivalente deterministische Maschine zu beweisen. Wir wissen bereits, dass es keine Lösung für das deterministische Halteproblem gibt. Daher ist es wirklich nützlich, andere Probleme zu beweisen, die durch Reduzierungen nicht zu entscheiden sind. Und es wird immer weniger Arbeit sein, sich auf das Problem des deterministischen Stillstands zu beschränken, da es einfacher ist als das nicht deterministische Gegenstück.

jmite
quelle

Sie geben an: " Bei nicht deterministischen Maschinen kann es jedoch zu mehreren Durchläufen kommen. Welcher davon für Sie von Interesse ist, hängt von Ihrer Anwendung ab. " Können Sie diese Aussage anhand eines Beispiels veranschaulichen? Dann geben Sie an, " Sie wandeln die Maschine einfach in eine deterministische um, bevor Sie sich Gedanken über das Anhalten machen ". Wie geht das für einen LBA?

Babou

LBAs sind eine Teilmenge nicht deterministischer Turingmaschinen, so dass sie immer mit der üblichen Methode in deterministische Turingmaschinen umgewandelt werden können. Ich vermute, dass es eine spezielle Konstruktion gibt, die verwendet werden kann, um in eine Maschine mit bestimmten Eigenschaften umzuwandeln, sodass wir die zusätzliche Fähigkeit behalten können, die wir von LBAs erhalten. Ich denke, es wird aussehen wie ein Backtracking-Algorithmus, bei dem der lineare Raum verwendet wird, außer dass der Aufrufstapel möglicherweise exponentiell groß sein könnte (ich bin nicht sicher, ich müsste ihn nachschlagen).

jmite

Betrachten Sie für mehrere Pfade zwei Maschinen

, eine, die bei Eingabe

immer anhält , und eine, die für

niemals anhält . Wir können ein neues LBA

erstellen, das mit der nicht deterministischen Auswahl eines Booleschen Werts beginnt. Wenn true ausgewählt wird, wird

für Eingabe x ausgeführt. Wenn false ausgewählt wird, wird

auf

. Jede Wahl von wahr und falsch ist ein anderer "Lauf". Hält diese Maschine für

? Es gibt einen Pfad, in dem

angehalten wird , aber nicht für alle Pfade, in denen

gelesen wird .

M_{1}, M_{2}

$M_1, M_2$

x

$x$

x

$x$

M

$M$

M_{1}

$M_1$

M_{2}

$M_2$

x

$x$

x

$x$

x

$x$

x

$x$

Jmite

1

@HendrikJan Es scheint, dass das Stoppen von NLBA eher mit dem Theorem von Savitch angegangen wird . Aber es ändert die lineare Grenze in eine quadratische.

Babou

1

@Raphael Damit meine ich, dass Sie, um das Problem

unentscheidbar zu machen, zeigen, dass Sie

, um ein anderes unentscheidbares Problem zu simulieren. Da es eine einfache injektive Zuordnung von DTMs zu NTMs gibt, ist jede Reduzierung von NTM-Anhalten auch eine Reduzierung von DTM-Anhalten. In der Regel ist es weniger arbeitsaufwendig, das DTM-Anhalten zu reduzieren, da es sich um ein weniger schwieriges Problem handelt, das Sie simulieren möchten.

P

$P$

P

$P$

Jmite

4

Das Stopp-Problem ist der Inbegriff -komplette Problem, da es wie gesagt werden kann: $\Sigma_1$

. $H(P,x) \leftrightarrow \exists c \, \text{ s. t. $c$ is a halting computing of $P$ on $x$}$

Dies deutet darauf hin, dass Ihre Definition korrekt ist. Im Allgemeinen ist jeder vollständige Definition "korrekt". $\Sigma_1$

Yuval Filmus
quelle

Leider weiß ich so gut wie nichts über arithmetische Hierarchien. Habe ich Recht, wenn ich verstehe, dass

teilentscheidbare Probleme darstellt? Was ist mit:

Σ_{1}

$\Sigma_1$

. Ich frage, weil existenzielle und universelle Quantifizierungen in verschiedenen Klassen zu enden scheinen, aber für mich ist alles verschwommen.

ist auch halbentscheidbar.

K (P, x) \leftrightarrow \forall c, c is a computing of P on x ⟹ c is halting.

$K(P,x)\leftrightarrow\forall c, c\text{ is a computing of $P$ on $x\implies c$ is halting.}$

K

$K$

Babou

Ich hatte Angst, dass Sie antworten würden. Ich habe gefragt, weil ich denke, dass ich ein Halbentscheidungsverfahren dafür habe. Entweder ist mein Beweis falsch oder ich habe mein Problem falsch formalisiert. Grundsätzlich ist es der Vorschlag von jmite, dass nicht deterministisches Anhalten an Eingabe

definiert werden kann, indem alle Berechnungen an

angehalten werden müssen. Und ich glaubte bis jetzt, dass ich eine Halbentscheidung dafür hatte.

x

$x$

x

$x$

Babou

Eigentlich ist deine Definition aus einem anderen Grund nicht gut: Was meinst du mit "

hält an"? Entweder meinst du, dass

, das a priori nur eine unvollständige Berechnung ist, tatsächlich vollständig ist. In diesem Fall ist

niemals wahr, da Sie

als leere Berechnung annehmen können . In jedem anderen Fall ist nicht klar, dass die Beschreibung von

endlich ist, und es ist auch nicht klar, dass das Prädikat "

hält an" berechenbar ist.

c

$c$

c

$c$

K (P, x)

$K(P,x)$

c

$c$

c

$c$

c

$c$

Yuval Filmus

Das Problem liegt also in der Tat in

aber wahrscheinlich nicht

-vollständig.

Π_{1}

$\Pi_1$

Π_{1}

$\Pi_1$

Yuval Filmus

Danke und Entschuldigung für meine naive Lektüre. Ich dachte, dass das verwendete

für "vollständige" Berechnungen steht, was anscheinend ein Fehler in der quantifizierten Domäne ist. Ich vermute, man kann nur zählbare Domänen verwenden, und der Satz von nicht stoppenden Berechnungen eines nicht deterministischen TM ist nicht geeignet. Ich denke auch, die Quantifizierer sagen uns, wie schlecht die Berechenbarkeit sein mag, bieten aber keine Garantie dafür, dass es so schlecht ist. Es scheint also, dass der Vorschlag von jmite nicht einfach direkt im erforderlichen "Format" ausgedrückt werden kann, aber mein Halbentscheidungsverfahren ist möglicherweise korrekt.

c

$c$

Babou

2

Sie sagen, es gibt eine "offensichtliche Behandlung zweiter Klasse" des Halteproblems für nicht deterministische Maschinen. Es scheint, dass der Nichtdeterminismus erst lange nach Turings Erschaffung des deterministischen TM historisch betrachtet wurde und dies möglicherweise etwas mit dem Forschungsschwerpunkt auf diesem Gebiet zu tun hat. Der Hauptpunkt hierbei ist jedoch, dass das nichtdeterministische Problem leicht auf das deterministische Problem reduziert werden kann, so dass man nur das deterministische Problem "ohne Verlust der Allgemeinheit" untersuchen muss.

Um der Idee der "2. Klasse" entgegenzuwirken, wird hier mindestens eine Referenz / Arbeit vorgestellt, die das Halteproblem für nicht deterministische Maschinen untersucht und nützliche / tiefe Verbindungen findet. Einige Indizien weisen darauf hin, dass die CS-Forschung so umfangreich / spezialisiert ist, manchmal wurden in den meisten Bereichen Forschungsarbeiten durchgeführt, die sogar eng erscheinen, und sie können sich nahezu bedeutungslos oder haarspaltend nähern, um unterschiedliche Probleme in ihrer Bedeutung einzustufen. und ganz im Gegenteil, Nichtdeterminismus scheint ein sehr tiefgreifendes / allgegenwärtiges / übergreifendes Konzept in CS zu sein (offene Schlüsselfragen wie P gegen NP sind auf ihm) und dieser Aspekt wird wahrscheinlich noch lange in der Zukunft fortbestehen.

Ein parametrisiertes Halteproblem / Chen, Flum

Abstrakt. Das parametrisierte Problem p-Halt nimmt eine nichtdeterministische Turingmaschine M und eine natürliche Zahl n als Eingabe, wobei die Größe von M der Parameter ist. Es wird gefragt, ob jeder akzeptierende Lauf von M auf leerem Eingabeband mehr als n Schritte dauert. Dieses Problem liegt in der Klasse XPuni, der Klasse "Uniform XP", wenn ein Algorithmus darüber entscheidet, welcher für die feste Maschine M im Zeitpolynom in n abläuft. Es zeigt sich, dass verschiedene offene Probleme verschiedener Bereiche der theoretischen Informatik mit p-Halt Halt XPuni verwandt oder sogar gleichwertig sind. Somit bildet diese Aussage eine Brücke, die es ermöglicht, Äquivalenzen zwischen Aussagen verschiedener Bereiche (Beweistheorie, Komplexitätstheorie, deskriptive Komplexität, ...) abzuleiten, die auf den ersten Blick nicht in Beziehung zu stehen scheinen. Wie unsere Präsentation zeigt,

vzn
quelle

2

In einer Nussschale

Es scheint keinen guten Grund zu geben, das Halteproblem in Umgebungen zu vernachlässigen, die nicht das klassische der deterministischen Turingmaschinen sind, abgesehen von der Tatsache, dass das klassische Halteproblem einige wichtige mathematische Fragen beantwortet (wie das Entscheidungsproblem) ) , während es sich nur um Varianten handelt interessante (?) technische Probleme, die sich jedoch weniger auf die Fundamente auswirken.

$A$ $x$

Nach der Antwort von jmite kann dieses nichtdeterministische Anhalten definiert werden als das Vorhandensein von mindestens einer Anhaltensberechnung ( existentielles Anhalten ) oder alternativ als die Anforderung, dass alle möglichen Berechnungen angehalten werden müssen ( universelles Anhalten ). Diese beiden Definitionen entsprechen zwei unterschiedlichen Definitionen des nichtdeterministischen Halteproblems.

Ich zeige, dass bei Turing-Maschinen die beiden Definitionen zwei unterschiedlichen Arten der Bestimmung der Maschine durch Verzahnung entsprechen. Daraus schließe ich, dass beide Varianten des nicht deterministischen Halteproblems dem klassischen deterministischen Halteproblem äquivalent sind .

Ich zeige jedoch auch, dass jede dieser Definitionen von Anhalten in direktem Zusammenhang mit einer entsprechenden Definition der Sprache steht, die von einer Turing-Maschine erkannt wird, und diese Beziehung kann einfach unter der Bedingung ausgedrückt werden, dass konsistente Definitionen gewählt werden.

Angesichts der üblichen Definition der Sprache, die von einem nichtdeterministischen Automaten erkannt wird, ist die natürliche Definition des nichtdeterministischen Anhaltens existenzielles Anhalten, wie in der ursprünglichen Frage vorgeschlagen.

Der größte Teil dieser Analyse erstreckt sich natürlich auch auf andere Arten von Automaten, obwohl die Schwalbenschwanzkonstruktionen häufig nicht in weniger leistungsfähigen Familien als Turing-Maschinen verfügbar sind.

Einführung

Ich schreibe dies als Antwort, da es meine Frage nach weiteren Überlegungen teilweise beantwortet, wobei vorhandene Antworten berücksichtigt werden. Wenn ich meine Frage nach drei Antworten bearbeite, kann dies in diesem Fall zu Problemen führen, und ich möchte die Frage lieber so lassen, wie sie ursprünglich geschrieben wurde, um dies zu vermeiden.

Ich diskutiere zuerst einige meiner Meinungsverschiedenheiten mit den gegebenen Antworten. Es geht nicht darum, faire Versuche, meine Frage zu beantworten, herabzusetzen (ich danke Ihnen für alle Antworten), sondern darum, den Problemen auf den Grund zu gehen, indem Sie technische Punkte diskutieren oder diskutieren.

Ich denke, die ursprüngliche Frage braucht kaum Kontext oder Motivation. Das Problem des Anhaltens ist eine der Hauptfragen, die wir uns einerseits zu Automaten stellen, und Nichtdeterminismus ist andererseits ein sehr verbreitetes und nützliches Merkmal vieler Automaten. Darüber hinaus ist Nichtdeterminismus nicht nur ein gängiges theoretisches Mittel zur Vereinfachung von Beweisen, sondern ein wesentliches Merkmal einiger Automatenfamilien, wie beispielsweise des linearen gebundenen Automaten (LBA), zumindest zum Zeitpunkt dieses Schreibens.

Daher ist es selbstverständlich, sich zu fragen, ob das Halteproblem eine Bedeutung hat oder eine bevorzugte Bedeutung, welche und warum im Fall nicht deterministischer Automaten.

Ist das nicht-terministische Stopp-Problem gut gelöst?

Meine Frage fragt sich, warum das Stopp-Problem für nicht deterministische Automaten eine zweitklassige Behandlung zu erhalten scheint , die eine Ablehnung und eine Antwort von vzn erzeugt hat. Die Antwort von vzn , die eigentlich eher ein langer Kommentar ist, besteht darauf, dass " Nichtdeterminismus in CS ein sehr tiefgreifendes / allgegenwärtiges / übergreifendes Konzept zu sein scheint", woran ich nie gezweifelt habe. Es gibt auch einen Hinweis auf eine Forschung zum Anhalten für nichtdeterministische Maschinen, die nicht überraschend ist, aber meinen Standpunkt nicht wirklich anspricht. Mein Standpunkt ist, dass ich mich nicht daran erinnere, tatsächlich eine Definition des angestrebten Halteproblems gesehen zu haben an nicht deterministischen Maschinen, obwohl ich auf diesem Gebiet einiges an Literatur gelesen habe. Es wird in meinem Referenzlehrbuch (Hopcroft + Ullman 1979) nicht angesprochen, AFAIK. Es scheint für Menschen oft implizit, dass sie deterministische Automaten in Betracht ziehen, normalerweise Turing Maschinen, deren Referenzdefinition deterministisch ist.

Zum Beispiel in der Frage, warum das Halteproblem für LBA entscheidbar ist? Yuval Filmus vergaß in seiner Antwort, dass LBAs nicht deterministische Geräte sind - speicherte seine Antwort aber brillant mit einem 4-Wörter-Kommentar .

Als letztes Zeugnis der Tatsache, dass dieses Thema im Allgemeinen nicht gut angesprochen wird (trotz einiger spezialisierter Untersuchungen), möchte ich die Tatsache nennen, dass das Thema hier erörtert werden muss.

Die Antwort von jmite ist die einzige, die tatsächlich versucht zu erklären, warum es möglicherweise nicht gut angesprochen wird. Sein erstes Argument ist, dass es zwei mögliche Definitionen gibt, aber ich glaube, dass diese Situation eher zu mehr Analysen anregen sollte, um zu bestimmen, welche Definition am besten geeignet wäre. Das versuche ich weiter unten.

Er schlägt auch vor, dass, da ein nicht deterministisches TM immer in ein äquivalentes deterministisches TM umgewandelt werden kann, es nicht sinnvoll ist, sich über das Problem des Anhaltens im nicht deterministischen Fall Gedanken zu machen. Ich bin nicht ganz überzeugt, aber es kann von vielen als guter Grund angesehen werden. Das Argument gilt jedoch nicht für Linear Bounded Automata (LBA), da es immer noch ein offenes Problem ist, ob deterministische LBA zu nicht deterministischen LBA äquivalent sind. Und es gibt andere Automatenfamilien, bei denen die deterministische Unterfamilie schwächer ist als die gesamte nichtdeterministische Familie (z. B. PDA).

Ich stimme auch nicht mit dem letzten Punkt überein und behaupte, wir sollten uns nicht mit nicht deterministischem Anhalten befassen, weil Beweise mit deterministischen Maschinen einfacher sind. Raphael beanstandete dies in einem Kommentar : " Ich finde es normalerweise einfacher, sich auf schwierigere Probleme zu beschränken. " In der Tat dient die nichtdeterministische Version für viele Arten von Automaten hauptsächlich der Vereinfachung von Beweisen, beispielsweise der Reduktion auf diesen Automatentyp. Es könnte sogar als Vorteil angesehen werden, zusätzlich zwei Arten von Stopps zu haben, die verwendet werden können, wie von jmite selbst vorgeschlagen, da sie mehr Flexibilität bieten, um Probleme anzugehen.

Zur Definition des nicht deterministischen Halteproblems

_{Hinweis: Die Verwendung des Wortes "universal" im folgenden Text bezieht sich auf die universelle Quantifizierung , NICHT auf universelle Turing-Maschinen}

Die Antwort von jmite ist die detaillierteste.

Diese Antwort vermutet, dass nicht deterministische Automaten weniger Aufwand für das Stopp-Problem bedeuten, da sie auf zwei verschiedene Arten definiert werden können (die Terminologie ist meine):

$M$ $x$
$M$ $x$

Die einzige Definition, die ich für angemessen gehalten hatte, ist existenzielles Anhalten .

$x$

Beweis : Dies ist mit König's Lemma leicht zu beweisen , da die Anzahl der möglichen nicht deterministischen Auswahlen bei jedem Schritt für einen gegebenen Automaten begrenzt ist. Wenn es unendlich viele Stoppberechnungen gäbe, könnten wir jede Konfiguration mit jedem der zu ihr führenden Berechnungspfade kennzeichnen, wodurch ein Berechnungsgraph mit unendlich vielen Knoten, aber nur endlicher nicht deterministischer Verzweigung an jedem Knoten erstellt würde. Nach König's Lemma impliziert dies die Existenz eines unendlichen Rechenpfades, der einer ununterbrochenen Berechnung entspricht.

Der Fall von (nicht deterministischen) Turingmaschinen

Lassen Sie uns nun das Anhalten bei einer nicht deterministischen Turing-Maschine (NTM) untersuchen.

Um die beiden Definitionen zu analysieren, ist es in der Tat am einfachsten, deterministische Versionen nicht deterministischer Maschinen zu betrachten, die nach Hendrik Jan durch Verzahnung aller möglichen Berechnungen erreicht werden können.

Es gibt jedoch (mindestens) zwei Möglichkeiten, Berechnungen für die Bestimmung zu verzahnen, obwohl normalerweise nur eine in Betracht gezogen wird:

existentielle Schwalbenschwanzbestimmung, die alle Berechnungen parallel simuliert und endet, wenn eine der simulierten Berechnungen endet.
universelle Schwalbenschwanzbestimmung, die alle Berechnungen parallel simuliert und nur dann endet, wenn alle simulierten Berechnungen enden. Es ist jedoch vorstellbar, dass die abschließenden Berechnungen in irgendeiner Weise aufgezählt oder gezählt werden.

Satz 2 :

$M$ $x$ $M_\exists$ $x$
$M$ $x$ $M_\forall$ $x$

$M$ $x$ $M_\forall$ $x$

Satz 3 : Das Halteproblem für deterministisches TM und die existenziellen und universellen Halteprobleme für nichtdeterministisches TM sind gleichbedeutend mit Turing.

Beweis : Dies ergibt sich aus Satz 2 und aus der Tatsache, dass deterministische TMs eine Teilmenge von nicht deterministischen TMs sind, bei denen sowohl existenzielles als auch universelles Anhalten auf einfaches deterministisches Anhalten reduziert werden.

Unter dem Gesichtspunkt der Berechenbarkeit scheint es daher, und ich bin versucht, dies aus symbolischer Sicht zu sagen, unerheblich zu sein, welche Definition für das nicht deterministische Halteproblem existentiell oder universell gewählt wird.

Warum eine Definition von NTM-Stopp wählen und welche?

Hat ein Bestimmungsprozess, bei dem die vom ursprünglichen Automaten erkannte Sprache nicht erhalten bleibt, jedoch viel Sinn?

Das Wesen des Nichtdeterminismus bei der Spracherkennung besteht darin, dass er ein Orakel voraussetzt, das einen richtigen Rechenweg erraten soll, wenn es einen gibt, der zur Akzeptanz führt, eine grundlegend existenzielle Sichtweise .

$\epsilon$

Akzeptanz durch Anhalten kann daher als kanonische Form der Akzeptanz für nichtdeterministische Automaten angesehen werden.

In Anbetracht dieser kanonischen Sichtweise kann das Halteproblem auch gleichbedeutend mit dem Erkennungsproblem ausgedrückt werden :

$L$ $M$ $x$ $x\in L$

$M$ $x$ $x$ $M$

Im Falle des universellen Anhaltens geht diese enge Beziehung jedoch verloren. Eine ähnliche Aussage kann gemacht werden, jedoch für eine andere Sprache als die von der NTM erkannte (oder alternativ für eine andere, universelle Definition der von einer NTM erkannten Sprache).

Bei der Entwicklung einer Theorie ist es wichtig, konsistente Definitionen zu verwenden, um Strukturen und Beziehungen in ihrer einfachsten und übersichtlichsten Form hervorzuheben. Es ist ziemlich klar, dass im vorliegenden Fall die Übereinstimmung mit anderen Definitionen nahelegt, dass existenzielles Anhalten die natürliche Definition des Anhaltens für nicht deterministische Turing-Maschinen ist.

$x$ $x$

Der Fall anderer Automatenfamilien

Teile der obigen Analyse können nicht auf die meisten Familien nicht deterministischer Automaten ausgedehnt werden. Beispielsweise kann ein Pushdown-Atomaton (PDA) Sprachen definieren, die von einem deterministischen PDA nicht erkannt werden können. Das gleiche kann für LBAs zutreffen. Andere Teile können auf alle nicht deterministischen Familien ausgedehnt werden.

In Bezug auf die Definition des nichtdeterministischen Anhaltens erscheint es sinnvoll, eine Definition zu wählen, die mit der für nichtdeterministische Turing-Maschinen verwendeten Definition konsistent ist, daher die existenzielle Definition .

Die Definition des Halteproblems für diese Familien nichtdeterministischer Automaten folgt und entspricht der in der Frage vorgeschlagenen Definition.

babou
quelle

Definieren des Halteproblems für nicht deterministische Automaten

Antworten:

In einer Nussschale

Einführung

Ist das nicht-terministische Stopp-Problem gut gelöst?

Zur Definition des nicht deterministischen Halteproblems

Der Fall von (nicht deterministischen) Turingmaschinen

Warum eine Definition von NTM-Stopp wählen und welche?

Der Fall anderer Automatenfamilien