Von Neumann Zellularer Automat - Von Neumann cellular automaton

Eine einfache Konfiguration in von Neumanns zellularem Automaten. Ein binäres Signal wird wiederholt durch die blaue Drahtschleife geleitet, wobei angeregte und ruhende normale Übertragungszustände verwendet werden . Eine konfluente Zelle dupliziert das Signal auf ein rotes Kabel, das aus speziellen Übertragungszuständen besteht . Das Signal geht über diesen Draht und baut am Ende eine neue Zelle auf. Dieses spezielle Signal (1011) kodiert für einen nach Osten gerichteten speziellen Übertragungszustand, wodurch die rote Leitung jedes Mal um eine Zelle verlängert wird. Während des Baus durchläuft die neue Zelle mehrere sensibilisierte Zustände, die von der binären Sequenz gesteuert werden.

Zelluläre Automaten von Neumann sind der ursprüngliche Ausdruck zellularer Automaten , deren Entwicklung durch Vorschläge seines engen Freundes und Mathematikerkollegen Stanislaw Ulam an John von Neumann angeregt wurde . Ihr ursprünglicher Zweck war es, Einblicke in die logischen Voraussetzungen für die maschinelle Selbstreplikation zu geben , und sie wurden in von Neumanns Universalkonstruktor verwendet .

Nobilis zellulärer Automat ist eine Variation des zellulären Automaten von von Neumann, erweitert um die Fähigkeit für konfluente Zellen, Signale zu kreuzen und Informationen zu speichern. Ersteres erfordert drei zusätzliche Zustände, daher hat Nobilis zellularer Automat 32 statt 29 Zustände. Huttons zellularer Automat ist eine weitere Variation, die es ermöglicht, eine Datenschleife, analog zu Langtons Schleifen , zu replizieren.

Definition

Aufbau

Im Allgemeinen bilden zellulare Automaten (CA) eine Anordnung von endlichen Automaten (FSA), die in Positionsbeziehungen zueinander sitzen, wobei jeder FSA Informationen mit den anderen FSAs austauscht, zu denen er positionsmäßig benachbart ist. In von Neumanns zellularem Automaten sind die endlichen Zustandsautomaten (oder Zellen ) in einem zweidimensionalen kartesischen Gitter angeordnet und verbinden sich mit den umgebenden vier Zellen. Da von Neumanns zellulärer Automat das erste Beispiel für diese Anordnung war, wird es als von Neumann-Nachbarschaft bezeichnet .

Der Satz von FSAs definiert einen Zellenraum von unendlicher Größe. Alle FSAs sind in Bezug auf die Zustandsübergangsfunktion oder den Regelsatz identisch.

Die Nachbarschaft (eine Gruppierungsfunktion) ist Teil der Zustandsübergangsfunktion und definiert für jede Zelle die Menge anderer Zellen, von denen der Zustand dieser Zelle abhängt.

Alle Zellen vollziehen ihre Übergänge synchron im Gleichschritt mit einem universellen "Takt" wie in einer synchronen digitalen Schaltung.

Zustände

Jeder FSA des von Neumann-Zellraums kann jeden der 29 Zustände des Regelsatzes akzeptieren. Der Regelsatz ist in fünf orthogonale Teilmengen gruppiert. Jeder Zustand beinhaltet die Farbe der Zelle im zellularen Automatenprogramm Golly in (rot, grün, blau). Sie sind

  1. ein Grundzustand U   (48, 48, 48)
  2. die Übergangs- oder sensibilisierten Zustände (in 8 Unterzuständen)
    1. S (neu sensibilisiert)  (255, 0, 0)
    2. S 0 – (sensibilisiert, einen Zyklus lang keine Eingabe erhalten)  (255, 125, 0)
    3. S 00 – (sensibilisiert, zwei Zyklen lang keine Eingabe erhalten)  (255, 175, 50)
    4. S 000 – (sensibilisiert, nach drei Zyklen keinen Input erhalten)  (251, 255, 0)
    5. S 01 – (sensibilisiert, nachdem für einen Zyklus keine Eingabe und dann für einen Zyklus eine Eingabe erhalten wurde)  (255, 200, 75)
    6. S 1 – (sensibilisiert, nachdem sie einen Zyklus lang einen Input erhalten haben)  (255, 150, 25)
    7. S 10 – (sensibilisiert, nachdem für einen Zyklus eine Eingabe erhalten wurde und dann für einen Zyklus keine Eingabe)  (255, 255, 100)
    8. S 11 – (sensibilisiert, nach zwei Zyklen Input erhalten)  (255, 250, 125)
  3. die konfluenten Zustände (in 4 Erregungszuständen)
    1. C 00 – Ruhe (und wird im nächsten Zyklus auch Ruhe sein)  (0, 255, 128)
    2. C 01 – als nächstes aufgeregt (jetzt ruht, wird aber im nächsten Zyklus aufgeregt)  (33, 215, 215)
    3. C 10 – aufgeregt (wird aber im nächsten Zyklus ruhig sein)  (255, 255, 128)
    4. C 11 – aufgeregt als nächstes erregt (derzeit erregt und wird im nächsten Zyklus erregt)  (255, 128, 64)
  4. die gewöhnlichen Transmissionszustände (in 4 Richtungen, angeregt oder ruhend, also 8 Zustände)
    1. Nach Norden gerichtet (aufgeregt und ruhig)   (36, 200, 36)   (106, 106, 255)
    2. Südgerichtet (aufgeregt und ruhig)   (106, 255, 106)   (139, 139, 255)
    3. Nach Westen gerichtet (aufgeregt und ruhig)   (73, 255, 73)   (122, 122, 255)
    4. Richtung Osten (aufgeregt und ruhig)   (27, 176, 27)   (89, 89, 255)
  5. die speziellen Transmissionszustände (in 4 Richtungen, angeregt oder ruhend, also 8 Zustände)
    1. Nach Norden gerichtet (aufgeregt und ruhig)   (191, 73, 255)   (255, 56, 56)
    2. Südgerichtet (aufgeregt und ruhig)   (203, 106, 255)   (255, 89, 89)
    3. Nach Westen gerichtet (aufgeregt und ruhig)   (197, 89, 255)   (255, 73, 73)
    4. Richtung Osten (aufgeregt und ruhig)   (185, 56, 255)   (235, 36, 36)

"Erregte" Zustände führen Daten mit einer Rate von einem Bit pro Zustandsübergangsschritt.

Beachten Sie, dass konfluente Zustände die Eigenschaft einer Verzögerung von einem Zyklus haben und somit effektiv zwei Datenbits gleichzeitig halten.

Regeln für den Übertragungsstatus

Der Bitfluss zwischen den Zellen wird durch die Richtungseigenschaft angezeigt. Es gelten folgende Regeln:

  • Übertragungszustände wenden den ODER-Operator auf Eingaben an, was bedeutet, dass eine Zelle in einem Übertragungszustand (normal oder speziell) zum Zeitpunkt t+1 erregt wird, wenn einer der darauf zeigenden Eingaben zum Zeitpunkt t . erregt wird
  • Daten gelangen von Zelle A in einem gewöhnlichen Übertragungszustand zu einer benachbarten Zelle B in einem gewöhnlichen Übertragungszustand gemäß der Richtungseigenschaft von A (es sei denn, B wird auch auf A gerichtet , in welchem ​​Fall die Daten verschwinden).
  • Daten werden von Zelle A in einem speziellen Übertragungszustand zu einer benachbarten Zelle B in einem speziellen Übertragungszustand nach den gleichen Regeln wie für gewöhnliche Übertragungszustände übertragen.
  • Die beiden Untergruppen von Übertragungszuständen, gewöhnlich und speziell, sind sich gegenseitig antagonistisch:
    • Gegeben sei eine Zelle A zur Zeit t im angeregten gewöhnlichen Transmissionszustand
    • zeigt auf eine Zelle B in einem speziellen Übertragungszustand
    • zum Zeitpunkt t+1 wird Zelle B der Grundzustand. Die spezielle Übertragungszelle wurde "zerstört".
    • eine ähnliche Sequenz wird im Fall einer Zelle im speziellen Übertragungszustand auftreten, die auf eine Zelle im normalen Übertragungszustand "zeigt".

Konfluente staatliche Regeln

Die folgenden spezifischen Regeln gelten für konfluente Staaten:

  • Konfluente Zustände übertragen keine Daten untereinander.
  • Konfluente Zustände nehmen Eingaben von einem oder mehreren gewöhnlichen Übertragungszuständen entgegen und liefern eine Ausgabe an gewöhnliche und spezielle Übertragungszustände, die nicht auf den konfluenten Zustand gerichtet sind.
  • Daten werden nicht gegen die Eigenschaft Richtung des Übertragungszustands übertragen.
  • Daten, die von einem konfluenten Zustand gehalten werden, gehen verloren, wenn dieser Zustand keinen benachbarten Übertragungszustand hat, der auch nicht auf den konfluenten Zustand zeigt.
  • Somit werden Zellen mit konfluentem Zustand als "Brücken" von Übertragungsleitungen von Zellen mit gewöhnlichem zu speziellem Übertragungszustand verwendet.
  • Der konfluente Zustand wendet den UND-Operator auf Eingaben an und "speichert" eine erregte Eingabe nur, wenn alle potentiellen Eingaben gleichzeitig erregt werden.
  • Konfluente Zellen verzögern Signale um eine Generation mehr als OTS-Zellen; Dies ist aufgrund von Paritätsbeschränkungen erforderlich .

Bauvorschriften

Die neun Zelltypen, die in von Neumanns CA konstruiert werden können. Hier laufen binäre Signale über neun gewöhnliche Übertragungsleitungen und bauen eine neue Zelle auf, wenn sie am Ende auf einen Grundzustand treffen. Zum Beispiel wird in der fünften Zeile die Binärzeichenfolge 1011 angezeigt und konstruiert den ostgerichteten Sonderübertragungszustand – dies ist der gleiche Prozess wie im Automaten oben auf dieser Seite. Beachten Sie, dass es, anders als beispielsweise in Wireworld , keine Interaktion zwischen benachbarten Drähten gibt , was ein kompaktes Packen von Komponenten ermöglicht.

Anfänglich ist ein Großteil des Zellraums, des Universums des zellulären Automaten, "leer", bestehend aus Zellen im Grundzustand U . Wenn eine Eingangserregung von einem benachbarten gewöhnlichen oder speziellen Transmissionszustand gegeben wird, wird die Zelle im Grundzustand "sensibilisiert", durchläuft eine Reihe von Zuständen, bevor sie schließlich in einem ruhenden Transmissions- oder konfluenten Zustand "ruht".

Die Wahl, welchen Zielzustand die Zelle erreichen wird, wird durch die Folge der Eingangssignale bestimmt. Daher kann man sich die Übergangs-/sensibilisierten Zustände als Knoten eines Bifurkationsbaums vorstellen, der vom Grundzustand zu jedem der ruhenden Transmissions- und konfluenten Zustände führt.

Im folgenden Baum wird nach jedem Schritt die Reihenfolge der Eingaben als Binärstring dargestellt:

  • eine Zelle im Grundzustand U geht bei einer Eingabe im nächsten Zyklus in den S- Zustand (neu sensibilisiert) über (1)
  • eine Zelle im S- Zustand, wenn keine Eingabe erfolgt, geht in den S 0- Zustand über (10)
    • eine Zelle im Zustand S 0 geht ohne Eingabe in den Zustand S 00 über (100)
      • eine Zelle im S 00- Zustand, wenn keine Eingabe erfolgt, geht in den S 000- Zustand über (1000)
        • eine Zelle im S 000- Zustand wird ohne Eingabe in den ostgerichteten normalen Übertragungszustand (10000) übergehen.
        • eine Zelle im S 000- Zustand geht bei einer Eingabe in den nach Norden gerichteten gewöhnlichen Übertragungszustand über (10001)
      • eine Zelle im Zustand S 00 wird bei einer Eingabe in den nach Westen gerichteten gewöhnlichen Übertragungszustand (1001) übergehen.
    • eine Zelle im Zustand S 0 geht bei einer Eingabe in den Zustand S 01 über (101)
      • eine Zelle im Zustand S 01 wird ohne Eingabe in den nach Süden gerichteten gewöhnlichen Übertragungszustand (1010) übergehen.
      • eine Zelle im Zustand S 01 wird bei einer Eingabe in den ostgerichteten Sonderübertragungszustand (1011) übergehen.
  • eine Zelle im S- Zustand geht bei einer Eingabe in den S 1- Zustand über (11)
    • eine Zelle im Zustand S 1 geht ohne Eingabe in den Zustand S 10 über (110)
      • eine Zelle im Zustand S 10 wird ohne Eingabe in den nach Norden gerichteten Sonderübertragungszustand (1100) übergehen.
      • eine Zelle im Zustand S 10 wird bei einer Eingabe in den nach Westen gerichteten Sonderübertragungszustand übergehen (1101)
    • eine Zelle im Zustand S 1 geht bei einer Eingabe in den Zustand S 11 über (111)
      • eine Zelle , in dem S 11 - Zustand, keine Eingabe gegeben wird in den Süden gerichtete spezieller Übertragungszustand (1110) Übergang
      • eine Zelle im Zustand S 11 geht bei einer Eingabe in den ruhenden konfluenten Zustand über C 00 (1111)

Beachten Sie, dass:

  • ein Eingabezyklus mehr (vier nach der anfänglichen Sensibilisierung) ist erforderlich, um den ost- oder nordgerichteten gewöhnlichen Übertragungszustand aufzubauen, als jeder der anderen Zustände (die drei Eingabezyklen nach der anfänglichen Sensibilisierung erfordern),
  • der "Standard"-Ruhezustand, der zum Aufbau führt, ist der nach Osten gerichtete normale Übertragungszustand, der eine anfängliche Sensibilisierungseingabe und dann vier Zyklen ohne Eingabe erfordert.

Zerstörungsregeln

Ungefähr 4000 Datenbits in einem zusammengerollten "Band", das ein komplexes Muster konstruiert. Dies verwendet eine 32-Zustands-Variante von zellulären Automaten von Neumann, die als Hutton32 bekannt ist.
  • Eine Eingabe in eine konfluente Zustandszelle von einer Spezialübertragungszustandszelle führt dazu, dass die konfluente Zustandszelle zurück in den Grundzustand reduziert wird.
  • In ähnlicher Weise führt eine Eingabe in eine Zelle mit gewöhnlichem Übertragungszustand von einer Zelle mit speziellem Übertragungszustand dazu, dass die Zelle mit gewöhnlichem Übertragungszustand zurück auf den Grundzustand reduziert wird.
  • Umgekehrt führt eine Eingabe in eine spezielle Übertragungszustandszelle von einer gewöhnlichen Übertragungszustandszelle dazu, dass die spezielle Übertragungszustandszelle zurück auf den Grundzustand reduziert wird.

Siehe auch

Verweise

  • Von Neumann, J. und AW Burks (1966). Theorie selbstreproduzierender Automaten. Urbana, University of Illinois Press. [1]

Externe Links

  • Golly - unterstützt von Neumanns CA zusammen mit dem Game of Life und anderen Regelwerken.