Wie ist die Regel 110 Turing vollständig?

Ich habe die Wikipedia-Seite für Regel 110 in Zellularautomaten gelesen und weiß mehr oder weniger, wie sie funktionieren (eine Reihe von Regeln entscheidet, wo die nächste 1 oder 0 gezeichnet wird).

Ich habe gerade gelesen, dass Turing vollständig ist, aber ich kann nicht einmal nachvollziehen, wie Sie in "Regel 110" "programmieren" würden.

Universalität ist ein etwas informeller Begriff. In etwa bedeutet dies, dass für jede berechenbare Funktion ein "Programm" $f$$P$ im Modell vorhanden ist, so dass das "Ausführen" von auf einer beliebigen Eingabe x immer "anhält" und die richtige Antwort "ausgibt". (Beachten Sie, dass Turing-Maschinen hier nicht auftauchen: Sie sind nur ein Beispiel für ein universelles Rechenmodell.)$P$$x$

Die zitierten Wörter sind diejenigen, die definiert werden müssen. Für Turingmaschinen:

• Ein Programm wird als eine Liste von Zuständen, ein Bandalphabet, ein Anfangszustand, Endzustände und Übergänge angegeben.
• Wenn Sie eine Turing-Maschine an einem Eingang x betreiben, wird das Band mit einer Kodierung von initialisiert$T$ $x$und die Maschine T auf diesem Band gemäß den üblichen Regelnausführen.$x$$T$
• Eine Turingmaschine hält an, wenn sie einen Endzustand erreicht. (Hier gibt es einige Varianten.)
• Was die Turing-Maschine ausgibt (wenn sie anhält), ist der Inhalt des Bandes.

Regel 110 als Rechenmodell muss in gleicher Weise formal definiert werden. Eine Definition ist sinnvoll, wenn man das Rechenmodell im folgenden Sinne rechnerisch simulieren kann: Es gibt eine berechenbare Funktion so dass für jedes Programm P und jede Eingabe x (beide als natürliche Zahlen kodiert) S ( P , x ) stoppt, wenn P stoppt auf x , und wenn S ( p , x ) stoppt, ist seine Ausgabe identisch mit der Ausgabe von P auf x .$S$$P$$x$$S(P,x)$$P$$x$$S(p,x)$$P$$x$

Wenn Sie neugierig auf die spezielle Konfiguration von Regel 110 als Computersystem sind, empfehlen wir Ihnen einen Blick auf Matthew Cooks Artikel, der die Universalität von Regel 110 (oder besser gesagt eines Computersystems, das auf Regel 110 basiert ) belegt.

Was andere Regeln wie Artikel 30 und Artikel 90 betrifft, wissen wir nicht, dass sie nicht universell sind. Es mag überzeugende Computersysteme geben, die universell einsetzbar sind, aber wir kennen einfach keine.

Aus Matthews Beweis:

Der hier verfolgte Ansatz besteht nicht darin, einen neuen zellularen Automaten zu entwerfen, sondern den einfachsten, der auf natürliche Weise ein komplexes Verhalten aufweist, und zu prüfen, ob wir in diesem komplexen Verhalten einen Weg finden können, es zu tun, was wir wollen. Wir werden uns nicht direkt mit der oben angegebenen Nachschlagetabelle befassen, sondern das Verhalten betrachten, das die Aktion des Automaten im Laufe der Zeit auf natürliche Weise zeigt.

Der Autor beginnt damit zu beweisen, dass ein "Tag-System", das bei jedem Schritt 2 Symbole entfernt, universell ist, indem er ein 2-Zustands-Turing-Maschinenprogramm kompiliert. Danach beweist er, dass ein Segelflugzeugsystem tatsächlich ein Tag-System implementieren kann. Es ist ein schrittweiser Prozess. Dann studiert er die Raumzeit des CA-110, um die Segelflugzeuge zu finden und sie korrekt dem Segelflugzeugsystem zuzuordnen.

Nun zu Ihrer Frage: Wie würden Sie in "Regel 110" "programmieren"?

1. Suchen Sie nach der einfachsten 2-Zustands-Turing-Maschine und finden Sie die Bänder der Grundoperationen OR, AND, XOR, NOT .

2. Übersetzen Sie diese in das Tag-System.

3. Kompilieren Sie die Implementierung des Tag-Systems in die Glider-Implementierung.

4. Passen Sie es richtig an die CA-110-Segelflugzeuge an und Sie haben die grundlegenden Operationen in einem zellularen Automaten.

Die Schritte 1 bis 4 werden nur einmal ausgeführt. Von dort aus wird berechnet$1+1=2$ Verwendung von Logikgattern zu Summenzahlen reduziert.

Eine Notiz beiseite. Segelflugzeuge sind sehr spezielle Strukturen. Die Operationen werden als Partikel angesehen, die sich bewegen und kollidieren (die Segelflugzeuge) und je nachdem, wie diese Segelflugzeuge starten oder kollidieren, eine unterschiedliche Ausgabe erzeugen.