Von Neumann’s Zellularautomaten

Da die von von Neumann angedachten Systeme bisher alle nur in der  Fantasie existierten, beschäftigte ihn die Frage, inwieweit ein selbstreproduzierendes System praktisch umgesetzt werden könnte. Im Gespräch mit einem Freund, dem polnischen Mathematiker Stanislaw Ulam, entwickelte er das Konzept der Zellularautomaten, angelehnt an das Wachstum von Kristallen. Ein Zellularautomat kann als schachbrettartige Anordnung von Zellen verstanden werden, wobei jede Zelle wiederum einen endlichen Zustandsautomaten repräsentiert und somit auf einem Satz einfacher Zustände und Zustandsübergänge basiert. Der Zustand einer Zelle ist dabei abhängig von den Zuständen der umliegenden Zellen 4 und ändert sich nach einem vordefinierten Zeitintervall. In diesem Fall findet eine Aktualisierung des Zellzustandes, basierend auf den Zuständen der Nachbarzellen, statt.

Von Neumann wählte ein unendliches Schachbrett an Zellen als Grundlage seines Zellularautomaten [1]. Auf diesem malte er ein Monster auf, das aus einem großen Rechteck mit einem langen Schwanz bestand und insgesamt bis zu 200 000 Zellen umfasste, wie unten abgebildet.

Neumann_CA

Schematische Darstellung des von Neumannschen selbstreproduzierenden Zellularautomaten [3].
Jede Zelle, die von dem Monster bedeckt war, stellte einen eigenen endlichen Zustandsautomaten dar und befand sich in einem von insgesamt 29 möglichen Zuständen. Die Kombination der einzelnen Zustände repräsentierte das Verhalten und die Existenz der Kreatur. Von Neumann gab die Regeln der Zellen vor, die wiederum jedoch abhängig von der Position der Zelle in der gesamten Kreatur war. Der Schwanz hatte die Funktion eines Konstruktionsarms und war nach einiger Zeit sogar in der Lage, das Vorderteil der Kreatur (das große Rechteck) zu reproduzieren. Anschließend verdoppelte sich der Konstruktionsarm selbst, schnitt das Duplikat ab und hatte eine vollständige Kopie der ursprünglichen Kreatur erzeugt. Die Vermutung lag nahe, dass das so entstandene künstliche System einen evolutionären Prozess durchlaufen konnte. Besonders interessant war hierbei die Frage, wie sich ein gleichartiges System verhalten würde, wenn es nicht nur innerhalb eines PC-Chips, sondern in der Realität “leben” würde.

Von Neumann’s Arbeiten wurden in den darauffolgenden Jahren von zahlreichen Wissenschaftlern erweitert, darunter z.B. Arthur W. Burks, Edgar F. Codd, und Stephen Wolfram. Dazu später mehr.

References
[1] Von Neumann, J. ; Burks, Arthur W. (Hrsg.): Theory of Self-Reproducing Automata. Champaign, IL, USA : University of Illinois Press, 1966

[2] Smith, A. R.: Simple Computation-Universal Cellular Spaces. Journal of the ACM 18 (1971), Nr. 3, S. 339–353.

[3] Levy, S.: Künstliches Leben aus dem Computer. 1st. München, Droemer Knaur, 1992