Was ist die einfachste unumstrittene Universal-Turing-Maschine mit zwei Zuständen?

31

Ich möchte eine einfache Turing-Maschine nach den Regeln eines Kartenspiels kodieren. Ich würde es gerne zu einer universellen Turingmaschine machen, um die Turing-Vollständigkeit zu beweisen.

Bisher habe ich einen Spielstatus erstellt, der Alex Smiths Turing-Maschine mit 2 Status und 3 Symbolen codiert . Allerdings scheint es (zugegebenermaßen basierend auf Wikipedia) Kontroversen darüber zu geben, ob die (2, 3) -Maschine tatsächlich universell ist.

Um genau zu sein, möchte ich, dass mein Beweis eine "unumstrittene" UTM enthält. Meine Fragen sind also:

  1. Wird die (2,3) Maschine allgemein als universell, nichtuniversell oder kontrovers angesehen? Ich weiß nicht, wo es seriöse Orte gibt, um die Antwort darauf zu finden.

  2. Wenn die (2,3) -Maschine nicht allgemein als universell anerkannt ist, welches ist das kleinste N, so dass eine (2, N) -Maschine unumstritten als universell anerkannt ist?

Bearbeitet, um hinzuzufügen: Es wäre auch nützlich, die Anforderungen für das Endlosband für die genannten Maschinen zu kennen, wenn Sie sie kennen. Es scheint, dass die (2,3) -Maschine einen nicht-periodischen Anfangszustand des Bandes benötigt, der nach den Regeln eines Kartenspiels etwas schwierig zu simulieren sein wird.

AlexC
quelle
3
Übrigens kann ich nicht sagen, ob Fragen zu Turingmaschinen besser hier oder auf MathOverflow gepostet würden. Ich versuche es hier zuerst, weil cs ein "turing-machines" -Tag hat und MO nicht. Ich bin kein Simul-Crossposting im Sinne der Richtlinie, aber ich freue mich, dass diese Frage migriert wird, wenn dies ein besserer Ort dafür wäre.
AlexC
12
Ich denke, das ist ein vernünftiger Ort für diese Frage.
Suresh Venkat
4
"Universal" zum Titel hinzugefügt. (Die einfachste 2-Zustands-Turing-Maschine stoppt in beiden
Zuständen, wenn
1
ps suchte vor Jahren nach einer Umfrage zum Thema Universalität in zellularen Automaten ohne Erfolg. es scheint nicht viel in die Literatur integriert worden zu sein. Das Konzept ist in der "Folklore" an dieser Stelle weit verbreitet, aber nicht in formalen Defns / Beweisen / Theorien begründet. wolfram hat viel auf dem gebiet gemacht, aber wie viele bemerkt haben, ist sein stil eher experimentell.
vzn
2
Heh. Der Kollege bringt das Papier ( arxiv.org/abs/1904.09828 ) auf Slack und schnüffelt mich, ich google "2,18 Universal Turn Machine", und hier sind wir. Herzliche Glückwünsche!
Cyan

Antworten:

12

Seit der in den vorherigen Antworten zitierten Arbeit sind einige neue Ergebnisse zu verzeichnen. Diese Umfrage beschreibt den Stand der Technik (siehe Abbildung 1). Die Größe der kleinsten bekannten Universal-Turingmaschine hängt von den Details des Modells ab. Hier sind zwei Ergebnisse, die für diese Diskussion relevant sind:

  • Es gibt eine Standard-Universalmaschine mit 18 Symbolen und zwei Zuständen (Rogozhin 1996. TCS, 168 (2): 215–240). Hier haben wir die übliche Vorstellung eines leeren Symbols in einer oder beiden Richtungen eines einzelnen Bandes.
  • Es gibt eine schwach universelle Maschine mit 2 Zuständen und 4 Symbolen (Neary, Woods 2009. FCT. Springer LNCS 5699: 262-273). Hier haben wir ein einzelnes Band, das die endliche Eingabe enthält, und ein konstantes (unabhängig von der Eingabe) Wort das unendlich rechts wiederholt wird , und ein anderes konstantes Wort l, das unendlich links wiederholt wird. Dies verbessert die von David Eppstein erwähnte schwach universelle Maschine.rl

Es hört sich so an, als ob (2,18) für Sie am nützlichsten ist.

Es ist bekannt, dass alle kleinsten universellen Turing-Maschinen in polynomieller Zeit laufen. Dies impliziert, dass ihr Vorhersageproblem (wenn eine Maschine , die Eingabe w und die Zeit t unär sind, akzeptiert M w innerhalb der Zeit t ?) P-vollständig ist. Wenn Sie versuchen, ein (1-Spieler-) Spiel zu erstellen, kann dies nützlich sein, um beispielsweise zu zeigen, dass es NP-schwer ist, eine anfängliche Konfiguration (Kartenhand) zu finden, die innerhalb von t Zügen zu einem Gewinn führt. Für diese Komplexitätsprobleme kümmern wir uns nur um einen begrenzten Teil des Bandes, was die (extrem kleinen) schwach universellen Maschinen sehr nützlich macht.MwtMwt

Neary, Woods SOFSEM 2012, Kleinste bekannte Universal-Turingmaschine

Die Abbildung zeigt die kleinsten bekannten Universalmaschinen für eine Vielzahl von Turingmaschinen-Modellen (entnommen aus Neary, Woods SOFSEM 2012). Die Referenzen finden Sie hier .

Niall Murphy
quelle
13

Dies ist keine echte Antwort auf Ihre Frage (ich weiß nicht viel über die (2,3) Maschinendebatte); aber ich schlage Ihnen die Zeitung " Kleine Turingmaschinen und allgemeiner reger Biberwettbewerb " vor. Ich habe es vor einiger Zeit schnell gelesen und es hat eine schöne Grafik mit den Grenzen zwischen den 4 Arten von kleinen TMs:

  • entscheidbar
  • offenes Collatz-ähnliches Problem
  • Simulation3x+1
  • Universal-

Bild aus dem Papier

(Vielleicht wurden einige Ergebnisse verbessert).

Der Begriff TM, der in dem Papier verwendet wird, ist die Standarddefinition von TM, die in Papieren auf kleinen Universal-Turing-Maschinen verwendet wird:

... Sie haben ein einzigartiges eindimensionales Band, das in beide Richtungen unendlich ist, und einen einzigartigen Schreib- / Lesekopf. Es gibt ein leeres Symbol, das mit 0 bezeichnet ist. Anfangs wird ein endliches Wort, die Eingabe, auf das Band geschrieben, andere Zellen enthalten das leere Symbol, der Kopf liest das Symbol ganz links der Eingabe und der Zustand ist der Anfangszustand. Bei jedem Schritt wird das Symbol entsprechend dem aktuellen Maschinenzustand und dem vom Kopf gelesenen Symbol geändert, der Kopf bewegt sich nach links oder rechts (und kann nicht die gleiche Zelle lesen), und der Zustand wird geändert. Die Berechnung wird gestoppt, wenn ein besonderer Haltezustand erreicht ist. ...

Marzio De Biasi
quelle
1
Der Link führt zu Alex Smiths Artikel, nicht zu dem Artikel, den Sie bestimmt haben.
Jeffs
Sehr nützlicher Link. Vielen Dank. Es sieht so aus, als würde ich mich am besten für eine (2, 18) Maschine entscheiden.
AlexC
Wenn man diese Zeitung liest, heißt es, dass Turingmaschinen mit 2 Zuständen und 3 Symbolen ein entscheidendes Problem beim Anhalten haben, so dass die Turingmaschine mit Wolfram 2 Zuständen und 3 Symbolen nicht universell sein kann.
Craig Feinstein
1
@CraigFeinstein: Der Wolfram (2,3) TM unterscheidet sich geringfügig von den üblichen TMs: Er hat keinen Haltestatus und erfordert eine unbegrenzte Unterstützung für nicht wiederholte Bänder. Es kann nicht einmal als schwach universell angesehen werden (ein schwach universelles TM erfordert ein unendlich wiederholtes Muster in beide Richtungen)
Marzio De Biasi
11

Es ist auch möglich, Universalität mit 7 Zuständen und 2 Symbolen zu erreichen, obwohl viele der gleichen Einwände zutreffen (ungleichmäßige Anfangsbedingungen auf dem Endlosband und ungewöhnliche Beendigungsbedingungen). Siehe http://11011110.livejournal.com/104656.html und http://www.complex-systems.com/abstracts/v15_i01_a01.html

Diese basieren auf der Simulation des von Matthew Cook universell nachgewiesenen Zellularautomaten nach Regel 110, und Cook fand auch eine 5-Symbol-Simulation nach Regel 110 mit zwei Zuständen, wenn Sie mit der Einschränkung verbunden sind, dass es nur zwei Zustände gibt.

David Eppstein
quelle
Die Beschränkung auf zwei Zustände wird viel einfacher zu simulieren sein als TMs mit mehr Zuständen. Momentan denke ich, dass es für mich einfacher sein wird, ein 18-Farben-TM mit zwei Zuständen als eines mit drei Zuständen und sogar einer kleinen Anzahl von Farben herzustellen.
AlexC
Die (2, 5) ist interessant und kann für mich ein nützlicher Zwischenschritt sein. Aber es sieht so aus, als müsste ich zu (2, 18) aufsteigen, um eine zu finden, die es mir ermöglicht, mit nur endlich vielen nichtschwarzen Zellen auf dem ursprünglichen Band zu beginnen. Vielen Dank!
AlexC
5

S0s<SC0c<C2LRC+4SC

Zu jeder Zeit kann nur die aktuelle Zelle oder die beiden an einem Übergang beteiligten Zellen eine verbesserte Farbe haben: Alle anderen Zellen haben ihre wahre Farbe. Wir möchten, dass sich unsere Maschine wie folgt verhält: Überprüfen Sie, welcher echte Übergang ausgeführt werden soll, verschieben Sie die "True State" -Informationen von der Zelle, die wir verlassen möchten, in die Zielzelle (dies beinhaltet viel Hin und Her), und bereinigen Sie die Zelle, die wir verlassen haben, wiederholen.

(c,s)LR(cNeu,sNeu,emittieren)L

cLc(c,0,L,erhalten)R

cc(c,s,emittieren)(c,0,L,erhalten)cc
ss0L

Hier sind die Übergänge, um das umzusetzen. Bewegen Sie sich in fast allen Fällen in die vom aktuellen Status festgelegte Richtung und drehen Sie den Status um

  1. c(c,0,dichr,erhalten)dichr

  2. (c,s)(cNeu,sNeu,emittieren)

  3. (c,s,emittieren)(c,s-1,emittieren)s>0

  4. (c,0,emittieren)c

  5. (c,s,dichr,erhalten)(c,s+1,dichr,erhalten)dichr

  6. (c,s,dichr,erhalten)(c,s)dichr

C+3SC

Bruno Le Floch
quelle
0

es sei denn, Sie definieren "nicht kontrovers" auf irgendeine technische Weise, es gibt keine genaue Antwort. Hier ist eine weitere kleine Maschine, die auf Regel 110 basiert und sich in gewissem Sinne als universell erwiesen hat. Meines Wissens erfordert sie jedoch unendlich viele periodische Eingabebandformulierungen (und auch die Extraktion am Ende, wenn die Maschine anhält). Ich habe das in der Literatur beschriebene "periodische vs. nichtperiodische" Bandproblem nicht gesehen, obwohl es beispielsweise auf Mailinglisten für Mathematik [Foundations of Mathematics Mailingliste] diskutiert wurde.

vzn
quelle
-3

Alex Smiths Turing-Universalitätsbeweis für Wolframs vermutete Turing-Maschine mit 2 Zuständen und 3 Symbolen ist definitiv nicht umstritten. Der gegebene Universalitätsnachweis (nicht die Maschine) erfordert ein unendliches Muster auf dem Turing-Band, und die Frage war, ob man solche Konfigurationen zulassen sollte (Sie können sich das normalerweise "leere" Band auch als ein unendliches sich wiederholendes Muster von leeren Symbolen vorstellen). Die Schlussfolgerung war, dass die Universalberechnung von der Turing-Maschine ausgeführt wird, solange die Konfiguration auf dem Maschinenband feststeht (dh, sie ändert sich nach dem Start Ihrer Berechnung nicht und bleibt für jede Berechnung gleich). Beachten Sie, dass dies für Wolframs elementare Zellularautomat-Regel 110, die Wolfram und Cook als universell erwiesen haben, NICHT umstritten ist. Der Universalitätsnachweis der Regel 110 erfordert auch ein unendliches Muster in der Anfangskonfiguration, das auf beiden Seiten unterschiedlich ist, und ist daher für die Turing-Maschine mit 2 Zuständen und 3 Symbolen von gleicher Natur. Eine andere Sorge war, dass eine solche Lockerung der (leeren) Anfangsbedingung möglicherweise einige akzeptierte nicht-Turing-Universalautomaten universal machen würde, wie z respektiert die Chomsky-Hierarchie. Es ist also definitiv nicht umstritten, ob die Turing-Maschine mit 2 Zuständen und 3 Symbolen universell ist, aber für den Universalitätsnachweis war eine Variation erforderlich, die normalerweise als die Cotents eines normalen Turing-Maschinenbands angesehen wird. Dies bedeutet übrigens nicht direkt, dass der 2-Zustand,

user2230103
quelle
Beim Versuch, dieses lange Argument zu analysieren, komme ich zu dem Schluss, dass Smiths (2,3) -TM eindeutig nur in einem schwachen Sinne universell ist. Einige der anderen Antworten haben dies jedoch bereits ausführlich erörtert, wobei auf Artikel mit Klassifikationen verwiesen wurde, die versuchen, diese Erzählung mathematisch präzise zu machen. Beachten Sie auch, dass nicht bei allen TM-Modellen zunächst ein unendliches leeres Band vorausgesetzt wird.
András Salamon
Ihr Kommentar zeigt nur, dass Sie den Bereich ignorieren. Ich habe keine schwierigen Konzepte für jemanden verwendet, der mit den Grundlagen von Turing-Maschinen vertraut ist (z. B. Erstkonfiguration, leeres Symbol usw.). Der einzige Unterschied, der bereits für andere Automatenarten akzeptiert wurde, besteht darin, dass die Smith-Wolfram-Turing-Maschine nicht von einem leeren Band ausgeht Angesichts der Art von Clowns, die heute die Welt unter dem Dach der Demokratie regieren, ist diese Erkenntnis wichtiger als alles andere.
user2230103