Wireworld
Wireworld ist ein Zellulärer Automat, der erstmals von Brian Silverman 1987 in seinem Programm Phantom Fish Tank verwendet wurde und später durch einen Artikel in der Kolumne Computer Recreations des Scientific American weitere Verbreitung fand. Wireworld eignet sich besonders für die Simulation elektronischer Logikelemente wie Gatter oder Flipflops. Trotz der Einfachheit seiner Regeln (s.u.) ist Wireworld Turing-vollständig, d. h. man kann damit sogar vollständige Computer erstellen (s. auch Weblink).
Regeln
Eine Wireworld-Zelle kann vier unterschiedliche Zustände einnehmen (die jeweils angegebene Farbe wird in den animierten Grafiken auf dieser Seite verwendet):
- schwarz steht für leer
- gelb steht für „elektrischer Leiter“
- blau steht für „Elektronenkopf“
- rot steht für „Elektronenende“
Die Zeit verläuft in diskreten Schritten, den sogenannten Generationen. Dabei bleibt eine leere Zelle grundsätzlich leer. Die übrigen Zellen verhalten sich beim Übergang von einer Generation zur nächsten wie folgt:
- Aus einem Elektronenkopf wird ein Elektronenende.
- Aus einem Elektronenende wird ein Leiter.
- Aus einem Leiter wird ein Elektronenkopf, wenn genau ein oder zwei der benachbarten Zellen Elektronenköpfe sind. Als benachbart gelten dabei die sogenannten Moore-Nachbarn, das sind alle Zellen, die den Leiter umgeben, auch die nur diagonal angrenzenden.
Anwendungen
Wendet man diese Regeln auf folgende Anordnung von Zellen an, so bewegt sich das Elektron bei jedem Generationswechsel um eine Position nach rechts (= Leiter, # Elektronenende, @ Elektronenkopf):
Generation n ====#@======== Generation n + 1 =====#@======= Generation n + 2 ======#@======
Durch geeignete Ausbildung von Leiterverzweigungen und -kreuzungen können logische Schaltelemente vom einfachen Gatter bis zum komplexen Rechenwerk realisiert werden.
Das Bild links zeigt die Implementierung zweier Taktgeber (linke Bildhälfte) und eines XOR-Gatters (rechts). Die Taktgeneratoren sind als ringförmige Leiterbahnen ausgeführt, in denen jeweils zwei Elektronen in unterschiedlichen Abständen kreisen. An den Verzweigungen am rechten Rand der Ringe werden Kopien dieser Elektronen in die zu den Eingängen des XOR-Gatters führenden Leiterbahnen emittiert. Die Taktgeber sind derart aufeinander abgestimmt, dass entweder jeweils ein einzelnes Elektron von oben oder unten in das XOR-Gatter eintritt (es wird durchgelassen), oder zwei Elektronen gleichzeitig am Gatter eintreffen − sie „vernichten“ sich gegenseitig und am Gatter-Ausgang tritt kein Elektron aus. Damit ist eine XOR-Verknüpfung der an den Gatter-Eingängen eintretenden Elektronen realisiert.
Signale
In Wireworld gibt es verschiedene Codierungen zur Übertragung von Daten. Allen gemein ist, dass ein Gesamtsignal in Blöcke gleicher Länge aufgeteilt wird. Eine Codierung mit der Blocklänge n nennt man "n-Micron"- oder auch "n-Tick"-Codierung.
In den sogenannten Real-Codierungen wird eine logische 0 durch einen leeren Block und eine 1 durch einen Block mit einem Elektron am Anfang repräsentiert. Die minimale Blocklänge beträgt dabei 3, da zwischen zwei Elektronen immer mindestens ein Feld Abstand sein muss. In den Complex-Codierungen wird eine 1 wie gehabt durch ein Elektron am Anfang des Blockes, eine 0 jedoch nicht durch kein, sondern durch ein um eine Generation verzögertes Elektron repräsentiert. Hier beträgt die minimale Blocklänge 4. Üblicherweise nutzt man
- 6-Micron-Real
- 4-Micron-Real
- 4-Micron-Complex
- 3-Micron-Real
Die Codierungen mit geringerer Blockgröße sind dabei schneller, benötigen aber unter Umständen aufwendigere Schaltungen.
Siehe auch
- Conways Spiel des Lebens
- Es existiert eine Wireworld-Implementierung von Langtons Ameise; sie ist in den Golly-Beispielpatterns enthalten.