Nichtdeterministische Turing -Maschine

Im Theoretische Informatik, a Nichtdeterministische Turing -Maschine (Ntm) ist ein theoretisches Berechnungsmodell, dessen regierende Regeln in einigen Situationen mehr als eine mögliche Aktion angeben. Das heißt, der nächste Zustand eines NTM ist nicht vollständig durch seine Aktion und das aktuelle Symbol, das es sieht, im Gegensatz zu a deterministische Turing -Maschine.

NTMs werden manchmal in verwendet Gedankenexperimente Untersuchung der Fähigkeiten und Grenzen von Computern. Eines der wichtigsten offenen Probleme in der theoretischen Informatik ist der P gegen NP -Problem, was (unter anderem äquivalente Formulierungen) die Frage betrifft, wie schwierig es ist, nicht deterministische Berechnungen mit einem deterministischen Computer zu simulieren.

Hintergrund

Im Wesentlichen wird vorgestellt, dass eine Turing -Maschine ein einfacher Computer ist, der Symbole jeweils auf ein endloses Band liest und schreibt, indem sie strikt einer Reihe von Regeln folgen. Es bestimmt, welche Aktion es als nächstes entsprechend dem internen ausführen sollte Zustand und Welches Symbol sieht es derzeit. Ein Beispiel für eine der Regeln einer Turing -Maschine könnte also sein: "Wenn Sie in Status 2 sind und ein" A "sehen, ändern Sie es in" B ", bewegen Sie sich nach links und ändern Sie sich in Status 3."

Deterministische Turing -Maschine

In einem deterministische Turing -Maschine (DTM), die Vorschriften der Regeln, die höchstens eine Maßnahme für eine bestimmte Situation vorschreibt.

Eine deterministische Turing -Maschine hat a Übergangsfunktion Das gibt für einen bestimmten Zustand und ein bestimmtes Symbol unter dem Bandkopf drei Dinge an:

Das Symbol, das an das Band geschrieben werden soll (es kann das gleiche sein wie das Symbol derzeit in dieser Position oder nicht einmal schreiben, was zu einer praktischen Änderung führt).
die Richtung (links, rechts oder auch nicht), in der sich der Kopf bewegen sollte, und
der nachfolgende Zustand der endlichen Kontrolle.

Zum Beispiel kann ein X auf dem Band in Status 3 das DTM ein Y auf das Band schreiben, die Kopfposition nach rechts bewegen und in Status 5 umstellen.

Intuition

Vergleich der deterministischen und nichtdeterministischen Berechnung

Im Gegensatz zu einer deterministischen Turing -Maschine in a Nichtdeterministische Turing -Maschine (Ntm) Die Regeln können mehr als eine Aktion vorschreiben, die für eine bestimmte Situation ausgeführt werden soll. Beispielsweise kann ein X auf dem Band in Status 3 das NTM zulassen, um:

Schreiben Sie ein Y, bewegen Sie sich rechts und wechseln Sie zu Status 5

oder

Schreiben Sie ein X, bewegen Sie sich nach links und bleiben Sie in Zustand 3.

Lösung mehrerer Regeln

Woher weiß das NTM, welche dieser Aktionen es ergreifen sollte? Es gibt zwei Möglichkeiten, es zu betrachten. Man soll sagen, dass die Maschine die "glücklichste mögliche Vermutung" ist; Es wählt immer einen Übergang aus, der schließlich zu einem akzeptierenden Zustand führt, wenn es einen solchen Übergang gibt. Die andere ist sich vorzustellen, dass die Maschine "Geäst"In viele Kopien, von denen jeder einem der möglichen Übergänge folgt. Während ein DTM einen einzigen" Berechnungsweg "hat, der folgt, hat ein NTM einen" Berechnungsbaum ". Wenn mindestens ein Zweig des Baumes mit einem anhält" Akzeptieren Sie "Bedingung, die NTM akzeptiert die Eingabe.

Definition

Eine nichtdeterministische Turing-Maschine kann formell als Sechs-Tupel definiert werden ${\ displayStyle m = (q, \ sigma, \ iota, \ sqcup, a, \ delta)}$ , wo

${\ displayStyle q}$ ist eine endliche Reihe von Staaten
${\ displayStyle \ sigma}$ ist ein endlicher Satz von Symbolen (das Band Alphabet)
${\ displayStyle \ iota \ in q}$ ist der Anfangszustand
${\ displayStyle \ sqcup \ in \ sigma}$ ist das leere Symbol
${\ displayStyle a \ subseteq q}$ ist der Satz von Akzeptieren (endgültige) Zustände
${\ displaystyle \ delta \ subseteq \ links (q \ Backslash a \ times \ sigma \ rechts) \ Times \ links (q \ times \ sigma \ times \ {l, s, r \} \ rechts)}}}}$ ist eine Beziehung zu Zuständen und Symbolen, die als die genannt werden Übergangsbeziehung. ${\ displayStyle l}$ ist die Bewegung nach links, ${\ displayStyle S}$ ist keine Bewegung und ${\ displayStyle r}$ ist die Bewegung nach rechts.

Der Unterschied mit einem Standard (deterministisch) Turing Maschine ist, dass die Übergangsbeziehung für deterministische Turing -Maschinen eher eine Funktion als nur eine Beziehung ist.

Konfigurationen und die ergibt Beziehung zu Konfigurationen, die die möglichen Aktionen der Turing -Maschine beschreiben, die mögliche Inhalte des Bandes haben ergibt Die Beziehung ist nicht mehr einwert. (Wenn die Maschine deterministisch ist, sind die möglichen Berechnungen alle Präfixe eines einzelnen, möglicherweise unendlichen Pfades.)

Die Eingabe für ein NTM ist auf die gleiche Weise bereitgestellt wie für eine deterministische Turing -Maschine: Die Maschine wird in der Konfiguration gestartet .

Ein NTM akzeptiert eine Eingangszeichenfolge, wenn und nur wenn mindestens ein Von den möglichen Rechenpfaden, die von dieser Saite beginnen, bringt die Maschine in einen Akzeptanzstatus. Wenn wir die vielen Verzweigungswege eines NTM auf einer deterministischen Maschine simulieren, können wir die gesamte Simulation so schnell stoppen irgendein Branch erreicht einen akzeptierenden Zustand.

Alternative Definitionen

Als mathematische Konstruktion, die hauptsächlich in Beweisen verwendet wird, gibt es eine Vielzahl von geringfügigen Variationen der Definition eines NTM, aber diese Variationen akzeptieren alle äquivalente Sprachen.

Die Kopfbewegung in der Ausgabe der Übergangsbeziehung wird häufig numerisch codiert, anstatt Buchstaben zu verwenden, um das Verschieben des Kopfes nach links (-1), stationär (0) und rechts (+1) zu beenden; eine Übergangsfunktionsausgabe von geben ${\ displaystyle \ links (q \ times \ sigma \ times \ {-1,0,+1 \} \ rechts)}$ . Es ist üblich, die stationäre (0) Ausgabe wegzulassen,^[1] und fügen Sie stattdessen den transitiven Verschluss aller gewünschten stationären Übergänge ein.

Einige Autoren fügen einen expliziten hinzu ablehnen Zustand,^[2] Dies führt dazu, dass der NTM anhält, ohne zu akzeptieren. Diese Definition behält immer noch die Asymmetrie, die irgendein Nichtdeterministischer Zweig kann akzeptieren, aber jeder Der Zweig muss abgelehnt werden, damit die Zeichenfolge abgelehnt werden soll.

Computeräquivalenz mit DTMs

Jedes Rechenproblem, das von einem DTM gelöst werden kann, kann auch von einem NTM gelöst und umgekehrt. Es wird jedoch angenommen, dass im Allgemeinen die Zeitkomplexität kann nicht gleich sein.

DTM als Sonderfall von NTM

NTMs umfassen DTMS als Sonderfälle, sodass jede Berechnung, die von einem DTM durchgeführt werden kann, auch durch das äquivalente NTM durchgeführt werden kann.

DTM -Simulation von NTM

Es scheint, dass NTMs leistungsfähiger sind als DTMs, da sie Bäume möglicher Berechnungen ermöglichen, die sich aus derselben anfänglichen Konfiguration ergeben, und eine Zeichenfolge akzeptiert, wenn jemand im Baum sie akzeptiert. Es ist jedoch möglich, NTMs mit DTMS zu simulieren, und dies kann in mehr als einer Weise erfolgen.

Multiplizität der Konfigurationszustände

Ein Ansatz besteht darin, einen DTM zu verwenden, von dem die Konfigurationen mehrere Konfigurationen des NTM darstellen, und der Operation des DTM besteht darin, jeweils jeder von ihnen zu besuchen, bei jedem Besuch einen einzelnen Schritt auszuführen und neue Konfigurationen auszuführen, wenn die Übergangsbeziehung mehrere Kontinuationen definiert .

Multiplizität von Bändern

Eine andere Konstruktion simuliert NTMs mit 3-Tape-DTMs, von denen das erste Band immer die ursprüngliche Eingangszeichenfolge enthält. Das zweite wird verwendet, um eine bestimmte Berechnung des NTM zu simulieren, und der dritte codiert einen Pfad im Berechnungsbaum des NTM.^[3] Die 3-Tape-DTMs lassen sich leicht mit einem normalen Einzelgepäck-DTM simulieren.

Zeitkomplexität und P gegen NP

In der zweiten Konstruktion führt das konstruierte DTM e effektiv a durch Breite-First-Suche des Berechnungsbaums des NTM besuchen Sie alle möglichen Berechnungen des NTM in der Reihenfolge der Erhöhung der Länge, bis er einen akzeptiert. Daher ist die Länge einer Annahme der Berechnung des DTM im Allgemeinen exponentiell in der Länge der kürzesten Akzeptanz der Berechnung des NTM. Es wird angenommen, dass dies eine allgemeine Eigenschaft von Simulationen von NTMs durch DTMS ist. Das P = NP -ProblemDie berühmteste ungelöste Frage in der Informatik betrifft einen Fall dieses Problems: Ob jedes Problem, das durch ein NTM in der Polynomzeit löslich ist oder nicht, ist in der Polynomzeit notwendigerweise auch lösbar.

Begrenzter Nichtdeterminismus

Ein NTM hat die Eigenschaft des begrenzten Nichtdeterminismus. Das heißt, wenn ein NTM immer an einem bestimmten Eingangsband angehalten wird T Dann hält es in einer begrenzten Anzahl von Schritten an und kann daher nur eine begrenzte Anzahl möglicher Konfigurationen haben.

Vergleich mit Quantencomputern

Die vermutete Form des Problembereichs Lösbar durch Quantencomputer in Polynomzeit (BQP). Beachten Sie, dass die Abbildung vorschlägt

{\ displaystyle {\ mathsf {p}} \ neq {\ mathsf {np}}}

und

{\ displayStyle {\ mathsf {np}} \ neq {\ mathsf {pspace}}}

. Wenn dies nicht der Fall ist, sollte die Figur anders aussehen.

Da Quantencomputer verwenden Quantenbits, was sein kann Überlagerungen von Staaten und nicht konventionellen Bits gibt es manchmal ein Missverständnis, das Quantencomputer sind NTMs.^[4] Es wird jedoch angenommen, dass Experten (aber nicht nachgewiesen wurden), dass die Leistung von Quantencomputern tatsächlich mit der von NTMS unvergleichlich ist; Das heißt, es gibt wahrscheinlich Probleme, dass ein NTM effizient lösen könnte, dass ein Quantencomputer nicht kann und umgekehrt.^[5] Insbesondere ist es wahrscheinlich, dass es wahrscheinlich ist NP-Complete Probleme sind durch NTMS lösbar, jedoch nicht durch Quantencomputer in Polynomzeit.

Während ein Quantencomputer intuitiv in einem Überlagerungszustand sein kann, der allen möglichen Berechnungszweigen entspricht, die gleichzeitig ausgeführt wurden (ähnlich wie ein NTM), kollabiert die endgültige Messung den Quantencomputer in einen zufällig ausgewählten Zweig. Dieser Zweig repräsentiert dann im Allgemeinen nicht die gesuchte Lösung, im Gegensatz zum NTM, der die richtige Lösung zwischen den exponentiell vielen Zweigen auswählen darf.

Siehe auch

Probabilistische Turing -Maschine

Verweise

^ Garey, Michael R.; David S. Johnson (1979). Computer und Unverdaulichkeit: Ein Leitfaden zur Theorie der NP-Vervollständigung. W. H. Freeman. ISBN 0-7167-1045-5.
^ Erickson, Jeff. "Nichtdeterministische Turing -Maschinen" (PDF). U. Illinois Urbana-Champaign. Abgerufen 2019-04-07.
^ Lewis, Harry R.; Papadimitriou, Christos (1981). "Abschnitt 4.6: Nichtdeterministische Turing -Maschinen". Elemente der Berechnungstheorie (1. Aufl.). Englewood Cliffs, New Jersey: Prentice-Hall. S. 204–211. ISBN 978-0132624787.
^ Die Orion Quantum Computer Anti-Hype-FAQ, Scott Aaronson.
^ Tušarová, Tereza (2004). "Quantenkomplexitätsklassen". Arxiv:CS/0409051..

Martin, John C. (1997). "Abschnitt 9.6: Nichtdeterministische Turing -Maschinen". Einführung in die Sprachen und die Theorie der Berechnung (2. Aufl.). McGraw-Hill. S. 277–281. ISBN 978-0073191461.
Papadimitriou, Christos (1993). "Abschnitt 2.7: Nichtdeterministische Maschinen". Rechenkomplexität (1. Aufl.). Addison-Wesley. S. 45–50. ISBN 978-0201530827.

Externe Links

[GJ-1] Garey, Michael R.; David S. Johnson (1979). Computer und Unverdaulichkeit: Ein Leitfaden zur Theorie der NP-Vervollständigung. W. H. Freeman. ISBN 0-7167-1045-5.

[jeffe-2] Erickson, Jeff. "Nichtdeterministische Turing -Maschinen" (PDF). U. Illinois Urbana-Champaign. Abgerufen 2019-04-07.

[3] Lewis, Harry R.; Papadimitriou, Christos (1981). "Abschnitt 4.6: Nichtdeterministische Turing -Maschinen". Elemente der Berechnungstheorie (1. Aufl.). Englewood Cliffs, New Jersey: Prentice-Hall. S. 204–211. ISBN 978-0132624787.

[4] Die Orion Quantum Computer Anti-Hype-FAQ, Scott Aaronson.

[5] Tušarová, Tereza (2004). "Quantenkomplexitätsklassen". Arxiv:CS/0409051..

[1]

[2]

[3]

[4]

[5]