Wang-Kacheln (Dominosteine) wurden 1961 von Hao Wang aus mathematischen Gründen erfunden. Sie wurden jedoch häufig in Spielen zur Erstellung von Kachelgrafiken verwendet. Dank ihnen sehen die Ergebnisse nicht repetitiv aus, sowohl in 2D-Texturen als auch in 3D-Modellen mit Kacheln.
Es scheint, dass Van-Kacheln auch Turing-Maschinen ausführen können, und deshalb sind sie Turing-vollständig, was bedeutet, dass sie jedes Programm ausführen können.
Dies ist eine erstaunliche und unverständliche Aussage, daher werde ich in diesem Beitrag dieses Problem ein wenig untersuchen.
Kurz über Van Tiles
Van-Kacheln sind rechteckige Kacheln, bei denen jede der Flächen nur anderen spezifischen Flächen entsprechen kann. Für jede bestimmte Fläche gibt es jedoch mehrere mögliche Kacheln, die dieser Fläche entsprechen können. Mit übereinstimmenden Flächen meine ich, dass sie sich nahtlos verbinden, ohne dass visuelle Artefakte oder Anzeichen einer Naht zwischen den Fliesen entstehen.
Diese Eigenschaft ist nützlich für Grafiken, da Sie damit nahtlose Kachelgrafiken erstellen können. Die Konfiguration der Position der Kacheln kann jedoch vollständig nach dem Zufallsprinzip erfolgen, sofern alle Flächen miteinander kompatibel sind. Das Ergebnis sind Kachelgrafiken, die sich keineswegs wiederholen, da visuelle Muster weniger auffallen als herkömmliche Kachelgrafiken.
Grafische Beispiele, detailliertere Informationen und Links zu Shadertoy finden Sie hier:
Wang Tiling .
Hier ist ein Beispiel, das ich erstellt habe. Meine Grafiken sind "Kunstprogrammierer", aber ich hoffe, die Idee ist klar. Die Zeichnung besteht aus 16 Kacheln und für jede Fläche gibt es zwei verschiedene Arten von Flächen.
Kurz über Turingmaschinen
Turing-Maschinen wurden 1936 von Alan Turing als generalisierter Computer erfunden, für den nachgewiesen wurde, dass er jeden Algorithmus ausführen kann.
Die Turing-Maschine besteht aus mehreren Hauptkomponenten: Speicherbändern, Lese- / Schreibköpfen und Zustandsautomaten.
Das Speicherband hat eine unendliche Länge, dh es hat eine unendliche Speicherkapazität, und am Anfang wird es nur mit Nullen initialisiert.
Der Lese- / Schreibkopf beginnt an einer bestimmten Position des Bandes und kann Werte lesen / schreiben sowie sich entlang des Bandes nach links und rechts bewegen.
Die Zustandsmaschine steuert den Lese- / Schreibkopf.
Die Zustandsmaschine weiß, in welchem Zustand sie sich befindet, und hat Regeln, was in jedem Zustand zu tun ist, wenn sie einen Wert vom Band liest.
Wenn beispielsweise in Zustand A 0 vom Band gelesen wird, kann die Regel lauten, 1 an die aktuelle Position des Bandes zu schreiben, den Lese- / Schreibkopf nach rechts zu bewegen oder in Zustand B überzugehen. Zustand B kann eine völlig andere Logik haben und entweder den Übergang durchführen zurück zu Zustand A oder in Zustand B bleiben oder in einen völlig anderen Zustand wechseln.
Unter Verwendung einer derart einfachen Logik des Übergangs zwischen Zuständen kann ein beliebiger Computeralgorithmus ausgeführt werden.
Die Turing-Maschine kann auch einen "Halt-Status" haben, was bedeutet, dass das Programm die Ausführung abgeschlossen hat und die Antwort berechnet wurde.
Auf der Suche nach einigen Programmen. kann leicht gesehen werden. dass sie im Laufe der Zeit enden oder sich in einer Endlosschleife befinden und niemals aufhören werden. Einige Programme befinden sich zwischen ihnen, sie sind komplex und es ist nicht so einfach festzustellen, ob sie jemals aufhören werden. Turing hat bewiesen, dass es keine allgemeine Lösung gibt, um festzustellen, ob die Turing-Maschine anhält (es ist ein Computerprogramm), und dies wird als
Stopp-Problem bezeichnet . Im Allgemeinen ist der einzige Weg, um herauszufinden, ob ein Programm stoppt, zu warten. Das heißt, im Allgemeinen lauten die Antworten auf diese Frage entweder "Ja" oder "Noch nicht". Bei vielen spezifischen Programmen können Sie jedoch feststellen, dass sie nach dem Start mit der Zeit enden werden.
Wang Fliesenberechnungen
Es stellt sich heraus, dass Wang-Kacheln eine Turing-Maschine simulieren können, das heißt, sie sind Turing-vollständig, was bedeutet, dass sie jeden Computeralgorithmus ausführen können.
Um dies zu realisieren, benötigen wir eine Spalte mit Van-Kacheln, die den Zustand der Turing-Maschine zu einem bestimmten Zeitpunkt anzeigt, beginnend zum Zeitpunkt 0 in der äußersten linken Spalte. Wir werden Kacheln in die rechte Spalte mit allen Regeln der Flächen einfügen und dann rechts davon eine Spalte erstellen usw., bis das Programm beendet wird (oder wir werden dies für immer tun, wenn es nicht endet). Wenn Sie den richtigen Kachelsatz auswählen, reicht es aus, beim Anordnen der Kacheln zu prüfen, ob die Regeln der Flächen eingehalten werden, um die Turing-Maschine fertigzustellen.
Schauen wir uns ein einfaches Beispiel an, das die folgenden Regeln für die Zustandsautomatenlogik enthält:
- Wenn sich die Maschine im Zustand A befindet, schreiben wir beim Lesen von 0 1, bewegen den Lese- / Schreibkopf nach unten und gehen in den Zustand B.
- Befindet sich die Maschine im Zustand A, stoppt das Programm beim Lesen von 1 (wechselt in den Endzustand).
- Wenn sich die Maschine im Zustand B befindet, schreiben wir beim Lesen von 0 1, bewegen den Schreib- / Lesekopf nach oben und gehen in den Zustand A.
- Wenn sich die Maschine im Zustand B befindet, stoppt das Programm beim Lesen von 1 (geht in den Endzustand über).
Bandlaufwerk
Zunächst benötigen wir einen dauerhaften Speicher für das Band. Dazu benötigen wir die folgenden zwei Kacheln:
Um ihre Arbeit zu testen, können wir ein Segment des Bandes mit einigen Werten vorbereiten (eine Spalte mit Van-Kacheln erstellen) und sicherstellen, dass die einzigen geeigneten Van-Kacheln, die sich neben der ersten Spalte befinden, Kacheln sind, die die Werte 0 und 1 zeitlich vorwärts übertragen, ohne sie zu ändern sie.
In der folgenden Abbildung wird das Band mit dem Wert 0101 in der Spalte ganz links (Zeitpunkt 0) initialisiert. Wenn wir nur Kacheln mit kompatiblen Flächen haben, sehen wir, dass die Werte im Speicher für immer gespeichert sind. Wir haben ein Speicherlaufwerk implementiert!
Wir werden beginnen, unser Beispiel mit einem auf 0 initialisierten Speicher zu demonstrieren, und die obige Abbildung zeigt einfach die Persistenz des Speichers.
Schreib- / Lesekopf-Zustandsmaschine
Der Schreib- / Lesekopf einer Turingmaschine wird als Teil der Gesichtsinformation dargestellt. Wenn sich der Lese- / Schreibkopf in dem Gesicht befindet, das 0 oder 1 speichert, speichert er somit auch den Zustand der Zustandsmaschine.
In unserem Beispiel werden zwei Zustände verwendet (ohne den Endzustand): A und B. Wenn 1 gelesen wird, endet das Programm in einem der Zustände (A oder B).
Dazu benötigen wir folgende Kacheln:
Da wir nun die Regeln für den Übergang in den Endzustand haben (Regeln 2 und 4), müssen wir verstehen, wie die Regeln implementiert werden, die das Umschalten von einem Zustand in einen anderen steuern (Regeln 1 und 3).
Schreib- / Lesekopf bewegen
Regel 1 besagt, dass wir, wenn wir uns in Zustand A befinden und 0 lesen, 1 schreiben müssen, den Lese- / Schreibkopf nach unten bewegen und in Zustand B gehen müssen.
Wir brauchen diese Kachel, um 0 in Zustand A zu lesen, 1 als Ausgabe zu schreiben und der Kachel unten zu befehlen, in Zustand B überzugehen.
Die Kachel unter der aktuellen Kachel kann den Wert 0 oder 1 haben. Ohne einen bestimmten Wert zu kennen, müssen wir ihn speichern, aber den Schreib- / Lesekopf akzeptieren und im Status B sein. Dazu benötigen wir zwei Kacheln - eine für 0 auf dem Band in dieser Position, die andere für 1 auf dem Band.
Regel 3 besagt, dass wir, wenn wir uns in Zustand B befinden und 0 lesen, 1 schreiben müssen, den Schreib- / Lesekopf nach oben bewegen und in Zustand A gehen müssen.
Dazu benötigen wir eine Konstruktion, die der Konstruktion für Regel 1 ähnelt, aber wir bewegen uns nicht nach unten, sondern nach oben. Die folgenden drei Kacheln ergeben das gewünschte Ergebnis:
Anfängliche Spaltenkacheln
Wir werden die Grenzen des Simulationsbereichs so wahrnehmen, als hätten sie eine x-Seite.
Dies bedeutet, dass wir zum Erstellen der anfänglichen Spalte (Turing-Maschine zum Zeitpunkt 0) zwei spezielle Kacheln benötigen. Eine Kachel wird benötigt, um den Wert 0 auf dem Band zu speichern, das das Band initialisiert, und eine andere Kachel, um die Position des Lese- / Schreibkopfs in Zustand A zu speichern, der unser Anfangszustand ist.
Diese beiden Kacheln sind:
Fertigset Fliesen
Hier ist der komplette Satz von 12 Kacheln, die wir verwenden werden:
Volle Simulation
Hier ist das Originaldesign unserer Turing-Maschine zum Zeitpunkt 0. Beachten Sie, dass dies einer der möglichen Anfangszustände ist, aber dies ist der von uns gewählte Zustand. Wir lassen keine Chance, zu entscheiden, wo der Lese- / Schreibkopf beginnt, und auch seine Anwesenheit. Wenn wir nur die Regeln der Gesichter befolgen, können wir 4 oder 0 Schreib- / Leseköpfe oder eine beliebige Zahl zwischen ihnen erhalten.
Um die zweite Spalte zu erstellen, beginnen wir von oben nach unten und wählen eine Kachel aus, die den Einschränkungen der Fläche entspricht, die sie berührt. In diesem ersten Schritt liest der Kopf 0, schreibt 1, bewegt sich nach unten und geht in den Zustand B.
Hier ist der zweite Schritt, in dem der Kopf 0 liest, 1 schreibt, nach oben geht und in den Zustand A übergeht.
Hier ist der letzte Schritt, in dem der Kopf 1 liest und in den Endzustand übergeht, um anzuzeigen, dass das Programm abgeschlossen ist.
Das Programm wurde beendet und ergab einen Ausgabewert von 0110 oder 6. Diese Ausgabewerte sind nicht besonders signifikant, aber andere Programme können eine signifikante Ausgabe erzeugen. Zum Beispiel können wir eine Turing-Maschine zwingen, zwei Zahlen hinzuzufügen, und die Ausgabe ist die Summe dieser beiden Zahlen.
Wichtiges Detail
Hier müssen wir ein wichtiges Detail erwähnen, das wir oben nicht berücksichtigt haben und das in den meisten Erklärungen von Turing-Maschinen auf Van-Fliesen nicht erwähnt wird.
Wenn Sie das zweite Plättchen für Zeit 2 platzieren, besteht die einzige Einschränkung für die Seiten darin, dass das Plättchen x oben und 1 links haben muss. In der Tat wird die Situation dadurch mehrdeutig, da nicht klar ist, welches der beiden unten gezeigten Kacheln ausgewählt werden soll.
Wie wählen wir dann die richtige aus?
Die Antwort ist, dass wir nur eine Annahme treffen und eine davon auswählen. Wenn in diesem Fall das falsche Plättchen ausgewählt ist, suchen wir nach einem Plättchen mit dem X oben und dem B0 links, wenn wir zum nächsten Plättchen übergehen. Ein solches Plättchen gibt es nicht, daher können wir das Plättchen nicht legen. In diesem Fall müssen wir zur letzten Kachel zurückkehren und eine der anderen Optionen ausprobieren.
Das heißt, wenn Turing-Maschinen mit Wang-Kacheln simuliert werden, gibt es leider buchstäblich einen Versuch und Irrtum-Prozess, aber zumindest ist er überschaubar. Es erschwert die Berechnungen im Pixel-Shader (oder in anderen Geräten mit hoher Parallelität) ein wenig, aber die Kosten sind nicht viel höher.
Schlussfolgerung und Links
Einige der folgenden Links behandeln Wang-Kacheln und Turing-Maschinen, aber die Diskussionen scheinen sich nicht strikt an Turing-Maschinen zu halten. Beispielsweise können Sie feststellen, dass in einigen Beispielen Daten "zurück in die Zeit" zurückkehren dürfen. Wenn das Programm beendet wird, erfolgt die Antwort auf Band zum Zeitpunkt 0 der Turing-Maschine, obwohl diese Daten zum Zeitpunkt 0 nicht vorhanden waren. Dies zeigt, dass Wang-Kacheln die Berechnungen selbst durchführen können und nicht nur Turing-Maschinen simulieren, aber ich weiß nicht genau, wie diese Technik heißen wird.
Wenn Sie außerdem wissen möchten, was beim Rechnen mit Wang-Kacheln nützlich ist, kann ich mir Fälle von deren praktischer Anwendung nicht vorstellen. Wissenschaftler scheinen jedoch entdeckt zu haben, dass DNA in etwa wie Van-Kacheln wirken kann, da Verbindungen nur zwischen kompatiblen Gesichtern hergestellt werden. Dank dessen werden nun DNA-basierte Berechnungen erforscht, die auf dem Prozess des Rechnens mit Wang-Kacheln basieren. Ziemlich interessantes Thema!
Hier ist die Implementierung der Berechnung von Primzahlen mit Wang-Kacheln in Shadertoy im WebGL-Pixel-Shader:
Shadertoy: WangTiles: PrimeGeneratorHier sind einige weitere großartige Videos über Turing-Autos und das Problem des Anhaltens:
Erklärte Turing-Maschinen - ComputerphileTuring & The Halting Problem - ComputerphileUnd hier noch ein paar Links:
Rechnen mit KachelnWikipedia: Van FliesenWang Fliesen und TuringmaschinenWang Fliesen - 1Hier sind einige wissenschaftliche Artikel:
Rechnen mit KachelnBerechenbarkeit von Fliesen