Zellularautomaten und Boolesche Netze - Modellierung komplexer Prozesse durch naturanaloge Verfahren - page 25

Ungeachtet der Einfachheit der Regeln des Game of Life ist es möglich, mit ihm sehr komple-
xe Dynamiken zu erzeugen. Tatsächlich handelt es sich beim Game of Life um eine sog. Uni-
versale Turing-Maschine, mit der man prinzipiell jedes beliebige System modellieren und
untersuchen kann, nämlich um ein System der Wolfram-Klasse 4. Nur in dieser Klasse treten
Systeme auf, die Universalen Turing Maschinen äquivalent sind. Von daher muss die Aussage,
dass Zellularautomaten Universalen Turing Maschinen logisch äquivalent sind, etwas präzisiert
werden, da nur ZA der Wolfram-Klasse 4 - und auch hier nicht unbedingt alle - diese Äquiva-
lenz aufweisen (Rasmussen et al. 1992).
Totalistische ZA-Regeln nützen also die Möglichkeiten aus, die sich durch kombinatorische
Zusammenfassungen der Zustände der Umgebungszellen und der Zentralzelle ergeben. Es sei
noch einmal betont, dass Moore- und von Neumann-Umgebungen zwar die Standardformen
von Umgebungen sind, dass jedoch nichts dagegen spricht, auch andere Umgebungsgrößen
einzuführen. Bei der ZA-Modellierung des Räuber-Beute Systems, das oben skizziert wurde,
arbeiteten wir zum Teil mit erweiterten Moore-Umgebungen, d. h., wir berücksichtigten auch
die Zustände der Zellen, die sich unmittelbar an die Umgebungszellen der Zentralzelle an-
schlossen. Dies war erforderlich, um den „Füchsen“ die Möglichkeit zu geben, über ihre Moo-
re-Umgebung hinaus zu prüfen, ob es in größerer Entfernung eventuell eine „Gans“ gibt. Die
entsprechende Regel lautet dann:
IF in der Moore-Umgebung eines Fuchses keine Gans ist und IF in der erweiterten Moore-
Umgebung eine Gans ist, THEN der Fuchs „bewegt“ sich um eine Zelle in Richtung der Gans,
falls eine entsprechende leere Zelle vorhanden ist.
Frage: Wie müsste man die „Bewegung“ einer Zelle korrekt in der ZA-Terminologie ausdrü-
cken, in der es nur Zustandsveränderungen von einzelnen Zellen gibt?
Wie man sich rasch überlegt, hat eine erweiterte Moore-Umgebung 8 + 12 + 4 = 24 Zellen;
eine n-fache Erweiterung von Moore-Umgebungen ergibt, was sich leicht durch vollständige
Induktion zeigen lässt, offenbar
(2n+1) 2 - 1 Zellen. 2 (2.1)
Diese Überlegungen gelten allerdings nur für zweidimensionale ZA. Wenn man aus z. B. Vi-
sualisierungsgründen dreidimensionale ZA entwickeln will, was wir für ein „Falken-Tauben-
System“ gemacht haben, also ein Räuber-Beute-System, das gewissermaßen in der Luft reali-
siert wird, dann hat eine einfache Moore-Umgebung im dreidimensionalen Raum bereits
26 Zellen und generell gilt für einfache Moore-Umgebungen in n-dimensionalen Räumen, dass
die Zahl ihrer Zellen
k = 3 n - 1 (2.2)

beträgt. Die folgenden zwei Bilder dienen zur Illustration eines dreidimensionalen ZA:

2

Eine mathematische Erinnerung: Beim Beweisverfahren der vollständigen Induktion beginnt man
damit, dass man die entsprechende Behauptung für den Fall n = 1 beweist. (der sog. Induktions-
anfang). Anschließend folgt der sog. Induktionsschritt, indem man von der Annahme, dass man die
Behauptung für ein beliebiges n bewiesen hat, zeigt, dass dann die Behauptung auch für n + 1 gilt. In
der obigen Formel ist die Variable n übrigens so zu verstehen, dass für die übliche Moore-Umgebung
gilt, dass n = 1; die Erweiterung ergibt dann n = 2 usf.