Was für ein Automat ist Googles Turing Doodle?

10

Zur Feier des Geburtstages von Alan Turing veröffentlichte Google ein Doodle mit einer Maschine. Was für eine Maschine ist das Gekritzel? Kann es eine Turing Complete-Sprache ausdrücken?

Es gibt offensichtliche Unterschiede zur klassischen Turingmaschine: ein endliches Band, Einschränkungen, wie der Zustand verbunden werden kann, ...

Die Doodle ist sein noch verfügbar hier Screenshot des Gekritzels

(Das Display oben rechts zeigt die erwartete Ausgabe.)

Das Band in der Mitte ist in Quadrate unterteilt, die ein Leerzeichen, eine Null oder eine Eins enthalten können. Der Kopf befindet sich über einem der Quadrate und dient zum Lesen und Schreiben.

Unter dem Band sehen Sie einen grünen Pfeil, auf den Sie klicken können, um die Maschine zu starten. Daneben befinden sich zwei Kreislinien, von denen einige miteinander verbunden sind. Ich werde sie "Staaten" nennen.

Nach dem Start der Maschine leuchtet der erste Status rechts neben der grünen Taste auf, dann der nächste rechts usw. Jeder Status enthält einen der folgenden Befehle:

  • leer = nichts tun (einfach zum nächsten Zustand übergehen)
  • 1 = Schreiben Sie an der aktuellen Position des Kopfes eine Eins auf das Band
  • 0 = Schreiben Sie an der aktuellen Position des Kopfes eine Null auf das Band
  • Pfeil nach links = Bewegen Sie den Kopf einen Schritt nach links
  • Pfeil nach rechts = Bewegen Sie den Kopf einen Schritt nach rechts
  • Bedingung: Wenn der Wert unter dem Kopf gleich dem auf dem Quadrat angezeigten Wert ist, gehen Sie zur zweiten Zustandszeile. Wenn nicht, fahren Sie mit dem nächsten Status rechts fort
  • linker Sprung: Rückkehr zu einem (festen) vorherigen Zustand, aber nur in der oberen Reihe [Ich habe diesen ursprünglich vergessen, danke @Marzio!]

Es gibt keine Möglichkeit, zwei Sprünge (übereinander) zu "überlappen". Die Maschine stoppt, wenn sie einen Zustand verlässt und rechts davon kein nächster Zustand ist.

(Nach dem Stoppen der Maschine wird der Inhalt des Bandes mit dem Inhalt der Anzeige verglichen, aber ich halte dies nicht für Teil der beabsichtigten Funktionalität der Maschine.)

bjelli
quelle
9
Eine Turingmaschine natürlich! en.wikipedia.org/wiki/Turing_machine Vielleicht waren Sie verwirrt, weil das Übergangssystem funky ist.
Huck Bennett
Es gibt auch einen "Links-Sprung-Operator" in der Steuermaschine, der es ermöglicht, zu einer vorherigen Position zurückzukehren, jedoch nur in der oberen Reihe. Außerdem gibt es keine Möglichkeit, zwei Sprünge (übereinander) zu "überlappen". Ohne den Sprungoperator entspricht die Maschine einem DFA (Aktionen in der Steuerungsmaschine werden von links nach rechts "ausgeführt"), aber auch mit dem begrenzten linken Sprungoperator scheint die Maschine nicht leistungsfähig genug zu sein, um einen LBA zu simulieren (aber ich habe es nicht getan) nicht zu viel darüber nachdenken). In jedem Fall kann es nicht vollständig sein, da das Band endlich ist.
Marzio De Biasi
1
@Marzio De Biasi: Sie haben Recht, dass dieses Puzzle Sprunganweisungen enthält, und ohne diese ist das Modell offensichtlich sehr schwach, da eine Maschine nur für eine konstante Zeit laufen kann. (Ich bin nicht sicher, was Sie unter "äquivalent zu einem DFA" verstehen.) Welche Einschränkung Sie den Sprunganweisungen auferlegen, kann die Antwort ändern. "Das Band ist endlich" ist wahrscheinlich eine falsche Annahme.
Tsuyoshi Ito
Google hält ihre Kritzeleien verfügbar (obwohl anscheinend nicht immer die interaktiven Versionen).
Raphael
@TsuyoshiIto: Ich meine (aber vielleicht irre ich mich), dass man bei einer Maschine ohne Schleifen einen DFA erstellen kann, der dies simuliert. Wenn Sie beliebige Sprünge in beide Richtungen zulassen und diese sich überlappen können, ist die Maschine auch mit nur zwei Zeilen sofort "fertig" (unter der Annahme eines unendlichen Bandes) (Zustände können horizontal "abgeflacht" werden). Ich weiß nicht, was passiert, wenn Sie linke Sprünge zulassen , die sich überlappen können (aber nur in der ersten Reihe) und eine beliebige Anzahl von Reihen (aber die Steuerung in den unteren Reihen kann nur nach oben oder unten erfolgen). Vielleicht ist es eine schöne Frage für cs.stackexchange.com
Marzio De Biasi

Antworten:

10

Vorausgesetzt, dass:

  • wir können eine beliebig große Anzahl von Zeilen hinzufügen ("Statuszeilen")
  • Die Zeilen können beliebig lang sein
  • Das Band ist unendlich

M4

atdoodle

... selbst wenn das Doodle des AT möglicherweise nicht vollständig ist (aufgrund des nicht überlappenden Nur-Links-Sprungoperators, der nur in der ersten Reihe verfügbar ist), ist es leistungsstark genug, um die feine Linie der (Un-) Entscheidbarkeit zu überschreiten: - D.

BEARBEITEN: TURING DOODLE TURING VOLLSTÄNDIG

(Ich lasse die vorherige Antwort oben, weil ich nicht sicher bin, ob dieser Teil korrekt ist :-)

Ich denke, dass das Turing Doodle auch mit einem einzigen nicht überlappenden Sprung nach links komplett ist! . Die (einfache) Idee besteht darin, das Band selbst zu verwenden, um den aktuellen Status zu speichern, und mehrere Zellen zu verwenden, um ein größeres Alphabet darzustellen.

Zum Beispiel kann ein 2 Zustände 8 Symbole TM unter Verwendung der folgenden Banddarstellung simuliert werden:

    HEAD POSITION
    v
...[s][b2 b1 b0] [_][b2 b1 b0] [_][b2 b1 b0] ....
   ^^^^^^^^^^^^^
    "macro cell"

Das Turing-Doodle kann:

  1. s
  2. b2,b1,b0
  3. Schreiben Sie das nächste Symbol, bewegen Sie den Kopf in die "Makrozelle" links oder rechts und speichern Sie den nächsten Status darauf. In der folgenden Abbildung werden diese Operationen (die mit den Aktionen "Verschieben nach links / rechts und Schreiben" für eine Sequenz von Zellen ausgeführt werden können) als "MW" bezeichnet.
  4. Übertragen Sie die Steuerung schließlich in die obere Reihe, damit die Steuerung mit einem einzigen Sprung nach links zu Schritt 1 zurückkehrt.

Das vollständige Bild finden Sie hier .

TdoodleTC

TMDM

Marzio De Biasi
quelle
nein! Du warst schneller als ich! Ich habe gerade geschrieben, wie man ein beliebiges TM im Zustandsraum anstelle von Band erstellt. Ihr Ansatz ist jedoch besser, da nur ein Sprung verwendet wird. Gut gemacht! Warten Sie, wie erhält Ihr Gerät Eingaben?
Artem Kaznatcheev
@ marzio-de-biasi Gute Arbeit!
Pepper_chico
1
@ArtemKaznatcheev: Es empfängt Eingaben auf dem Band. Natürlich müssen Sie es entsprechend den ursprünglichen Alphabetsymbolen des zu emulierenden TM codieren und Leerzeichen für die Zustandsdarstellung lassen.
Marzio De Biasi
Die Marke des Junior alen turing. Ich habe es genossen, dies zu lesen
iDroid
nicht vollständig überzeugt TM Vollständigkeit. Denken Sie nicht, dass Sie den Fall behandelt haben, in dem das TM in neue leere Quadrate schreibt, die zuvor nicht auf dem Eingabeband definiert wurden. Dies ist für die TM-Vollständigkeit erforderlich, andernfalls ist es nur eine endliche Berechnung.
VZN
5

Die Maschine wird mit einem „Klebeband“ (dem Analogon von Papier) geliefert, das durch sie läuft und in Abschnitte (als „Quadrate“ bezeichnet) unterteilt ist, die jeweils ein „Symbol“ tragen können. Zu jedem Zeitpunkt gibt es nur ein Quadrat, beispielsweise das r-te, das das Symbol S (r) trägt, das sich „in der Maschine“ befindet. Wir können dieses Quadrat das "gescannte Quadrat" nennen. Das Symbol auf dem gescannten Quadrat kann als "gescanntes Symbol" bezeichnet werden. Das „gescannte Symbol“ ist das einzige, von dem die Maschine sozusagen „direkt bewusst“ ist. Durch Ändern der m-Konfiguration kann sich das Gerät jedoch effektiv an einige der Symbole erinnern, die es zuvor „gesehen“ (gescannt) hat. Das mögliche Verhalten der Maschine zu jedem Zeitpunkt wird durch die m-Konfiguration qn und das gescannte Symbol S (r) bestimmt. Dieses Paar qn, S (r) wird als "Konfiguration" bezeichnet: Somit bestimmt die Konfiguration das mögliche Verhalten der Maschine. In einigen Konfigurationen, in denen das gescannte Quadrat leer ist (dh kein Symbol trägt), schreibt das Gerät ein neues Symbol auf das gescannte Quadrat: In anderen Konfigurationen wird das gescannte Symbol gelöscht. Das Gerät kann auch das gescannte Quadrat ändern, jedoch nur, indem es um eine Stelle nach rechts oder links verschoben wird. Zusätzlich zu diesen Operationen kann die m-Konfiguration geändert werden. Einige der aufgeschriebenen Symbole {232} bilden die Folge von Zahlen, die die Dezimalstelle der reellen Zahl ist, die berechnet wird. Die anderen sind nur grobe Notizen, um „das Gedächtnis zu unterstützen“. Es sind nur diese groben Notizen, die gelöscht werden können. trägt kein Symbol) Das Gerät schreibt ein neues Symbol auf das gescannte Quadrat: In anderen Konfigurationen wird das gescannte Symbol gelöscht. Das Gerät kann auch das gescannte Quadrat ändern, jedoch nur, indem es um eine Stelle nach rechts oder links verschoben wird. Zusätzlich zu diesen Operationen kann die m-Konfiguration geändert werden. Einige der aufgeschriebenen Symbole {232} bilden die Folge von Zahlen, die die Dezimalstelle der reellen Zahl ist, die berechnet wird. Die anderen sind nur grobe Notizen, um „das Gedächtnis zu unterstützen“. Es sind nur diese groben Notizen, die gelöscht werden können. trägt kein Symbol) Das Gerät schreibt ein neues Symbol auf das gescannte Quadrat: In anderen Konfigurationen wird das gescannte Symbol gelöscht. Das Gerät kann auch das gescannte Quadrat ändern, jedoch nur, indem es um eine Stelle nach rechts oder links verschoben wird. Zusätzlich zu diesen Operationen kann die m-Konfiguration geändert werden. Einige der aufgeschriebenen Symbole {232} bilden die Folge von Zahlen, die die Dezimalstelle der reellen Zahl ist, die berechnet wird. Die anderen sind nur grobe Notizen, um „das Gedächtnis zu unterstützen“. Es sind nur diese groben Notizen, die gelöscht werden können. Einige der aufgeschriebenen Symbole {232} bilden die Folge von Zahlen, die die Dezimalstelle der reellen Zahl ist, die berechnet wird. Die anderen sind nur grobe Notizen, um „das Gedächtnis zu unterstützen“. Es sind nur diese groben Notizen, die gelöscht werden können. Einige der aufgeschriebenen Symbole {232} bilden die Folge von Zahlen, die die Dezimalstelle der reellen Zahl ist, die berechnet wird. Die anderen sind nur grobe Notizen, um „das Gedächtnis zu unterstützen“. Es sind nur diese groben Notizen, die gelöscht werden können.

Ich behaupte, dass diese Operationen alle umfassen, die bei der Berechnung einer Zahl verwendet werden. Die Verteidigung dieser Behauptung wird einfacher, wenn die Theorie der Maschinen dem Leser vertraut ist. Im nächsten Abschnitt fahre ich daher mit der Entwicklung der Theorie fort und gehe davon aus, dass verstanden wird, was unter "Maschine", "Band", "gescannt" usw. zu verstehen ist.

Dies ist ein Auszug aus dem Original-Turing-Papier "Über berechenbare Zahlen mit einer Anwendung auf das Entscheidungsproblem".

Ein moderner guter Begleiter zu dem von mir empfohlenen Papier ist The Annotated Turing von Charles Petzold.

Wie Sie vielleicht sehen, hat Google nur versucht, einer Maschine zu ähneln, die der Beschreibung des Turing sehr ähnlich ist.

BEARBEITEN: Angenommen, das vollständige TM-Alphabet von Google wird am Ende des Spiels angezeigt, nachdem Sie auf das Häschensymbol geklickt haben und aufgrund der Tatsache, dass es eine unendliche Sequenz erzeugt, mehr Zeilen und Spalten erhalten haben (wir können also davon ausgehen, dass wir beliebige hinzufügen können ), hat linke Sprünge (und überlappt auch linke Sprünge) in jeder Reihe , hat bedingte und bedingungslose Sprünge zwischen benachbarten Reihen, ich denke, es ist Turing vollständig .

pepper_chico
quelle
aber haben sie akut eine turingmaschine implementiert? Dieser hat ein endliches Band, das ist also ein leicht erkennbarer Unterschied. Ist es ein Unterschied, der einen Unterschied macht? Haben sie tatsächlich eine schwächere Maschine implementiert?
Bjelli
2
@bjelli Nun, ich kann das nicht versichern, denn da ich es nicht entworfen habe, kenne ich nicht alle Regeln über ihre Maschine. Wenn Sie jedoch das Finale des Spiels erreichen, können Sie auf das Bunny-Symbol klicken, das Sie zu einem längeren Band führt. Überprüfen Sie die Analyse hier: sbf5.com/~cduan/technical/turing . Daher gibt es möglicherweise keine Einschränkung für die Anzahl der Zeilen, die das Gerät erhalten kann, was Sie zu einem Band beliebiger Größe führen würde.
Pepper_chico
PLZ skizzieren einen Beweis, dass seine Turing abgeschlossen ist
vzn
4

In den Rätseln sind Sprünge auf beiden Linien erlaubt, sie können sich jedoch nicht überlappen. Beim letzten Kaninchensequenz-Doodle am Ende des Spiels erlauben sie Sprünge in jeder Zeile und sie können in Klammern verschachtelt werden, so dass [()] erlaubt ist, aber ([)] scheint nicht erlaubt zu sein.

Ich werde die folgenden Annahmen verwenden:

  1. 01ϵ
  2. Die Maschine kann eine beliebige feste Anzahl von Zeilen verwenden
  3. Linkssprünge sind in jeder Zeile zulässig (ich verwende einen Linkssprung pro Zeile).
  4. ϵ01

Mit diesen Annahmen ist die Google Doodle-Maschine vollständig .

01ϵ01n

3(n1)+15n+1

Google Doodle Machine

ϵ01ϵ0101

Das GDM simuliert das TM wie folgt:

  1. 1
  2. j
  3. ϵ01
  4. ϵ
  5. 01
  6. 01

Wählen Sie Ihr bevorzugtes Universal-TM aus und implementieren Sie es wie oben beschrieben, um ein universelles GDM zu erhalten.

Artem Kaznatcheev
quelle