12.2 Zellular-Automaten

Zelluläre Automaten(1) sind Modelle, in denen die Eigenschaften der einzelnen Zellen in engem Zusammenhang mit dem Verhalten der benachbarten Zellen stehen. Im eindimensionalen Fall ist der Algorithmus am einfachsten zu formulieren. Das zeitliche Verhalten einiger "Zellen" wird in nacheinanderfolgenden Reihen dargestellt.



Im Bild wird zunächst gezeigt, dass der Wert einer Zelle aus den Eigenschaften der drei angrenzenden Zellen in der vorangegangenen Reihe berechnet wird. Die Farben der Felder entsprechen Zahlen: Weiß für 0, Rot für 1 und Grün für 2. Im unteren Teil des Bildes wird somit der Algorithmus dargestellt: Der Wert der neuen Zelle berechnet sich aus der Summe der drei Nachbarzellen. Welche Farbe der Summe zugeordnet wird, entscheidet eine mehrstellige "Codezahl":
6 5 4 3 2 1 0
1 2 0 1 1 2 0


Für dieses Beispiel wurde die Codezahl 12011203 verwendet (3 verschiedene Farben!).

Aufgrund der Regeln "entwickelt" sich eine komplizierte Struktur aus einer (oder mehreren) Ausgangszellen. Da jeder Zeitschritt einer neuen Reihe entspricht, kann aus dem erhaltenen Bild gleichsam die zeitliche Entwicklung einer "Anfangspopulation" untersucht werden...

Das Verhalten des eindimensionalen zellulären Automaten hängt somit wesentlich von der Codezahl und von der Ausgangsposition, also von der Anzahl der Zellen und von ihrer "Farbe" (also eigentlich von ihren "Eigenschaften") ab. In diesem Sinn können zelluläre Automaten biologische Systeme oder physikalische Modelle darstellen.

Das nächste Bild zeigt das Verhalten des Automaten mit der Codezahl 12011203 über mehrere Zeitschritte hinweg:

In der nächsten Abbildung wurde der eindimensionale Automat mit der Codezahl 022310005 "gerechnet", als Ausgangssituation wurde eine Zufallsfolge von Zahlen zwischen 0 und 4 (weiß, rot, grün, blau und gelb) verwendet. Interessanterweise brechen manche Strukturen ab, andere wiederholen sich unendlich oft:

Aufgabe: Untersuche die Automaten 042004105, 03314105, 0202243105, 011004005, 01312105 und 032113105!

Nur die Eigenschaften einer endlichen Kette (also einer Kette, die nach endlichen Schritten abbricht) können genau studiert werden. Im Allgemeinen kann das endgültige Verhalten des zellulären Automaten - etwa, ob eine Kette unregelmäßig bleibt oder sich wiederholt - nicht aus einer endlichen Anzahl von Schritten bestimmt werden... 

procedure tform1.putpix(xx,yy:integer; farbe:TColor);
begin
paintbox1.canvas.pen.color:=farbe;
paintbox1.canvas.brush.color:=farbe;
paintbox1.canvas.rectangle(xx-s,yy-s,xx+s,yy+s);
end;

procedure TForm1.Rechnen1Click(Sender: TObject);
var x,y:integer;
i,j:integer;
summe:integer;
lauf,index:integer;
bits,anfang:string;
l,la:integer;
wieweit:integer;
begin
s:=StrToInt(editgro.text);
form1.caption:='Zellular-Automaten - läuft!!!';
index:=StrToInt(editindex.text);
bits:=bitmuster.text;
l:=length(bits);
anfang:=editanfang.text;
la:=length(anfang);
with paintbox1 do begin
left:=0;
top:=0;
width:=Screen.Width-15;
height:=Screen.Height-40;
x:=s+140;
y:=height div 2 - (height div 2) mod (2*s+1)+length(anfang)*(2*s+1)
div 2;
end;
wieweit:=StrtoInt(editweite.text);
if wieweit=0 then wieweit:=paintbox1.width;
with paintbox1.canvas do begin
pen.color:=clBlack;
brush.color:=clWhite;
rectangle(0,0,width,height);
if s<>0 then begin
for lauf:=0 to la-1 do begin
putpix(x,y-(2*s+1)*lauf,farben[StrToInt(copy(anfang,lauf+1,1))]);
end;
end else begin
for lauf:=0 to la-1 do begin
pixels[x,y-lauf]:=farben[strtoint(copy(anfang,lauf+1,1))];
end;
end;
i:=x;
repeat
j:=0;
repeat
summe:=0;
for lauf:=1 to index do begin
if pixels[i,j]=clRed then summe:=summe+1;
if pixels[i,j]=clGreen then summe:=summe+2;
if pixels[i,j]=clBlue then summe:=summe+3;
if pixels[i,j]=clYellow then summe:=summe+4;
j:=j+(2*s+1);
end;
if s<>0 then j:=j-(2*s+1)*((index div 2)+1)
else j:=j-{(index div 2+1)}2;
if s<>0 then begin
case summe of
0:putpix(i+(2*s+1),j,farben[StrtoInt(copy(bits,l,1))]);
1:putpix(i+(2*s+1),j,farben[StrtoInt(copy(bits,l-1,1))]);
2:putpix(i+(2*s+1),j,farben[StrtoInt(copy(bits,l-2,1))]);
3:putpix(i+(2*s+1),j,farben[StrtoInt(copy(bits,l-3,1))]);
4:putpix(i+(2*s+1),j,farben[StrtoInt(copy(bits,l-4,1))]);
5:putpix(i+(2*s+1),j,farben[StrtoInt(copy(bits,l-5,1))]);
6:putpix(i+(2*s+1),j,farben[StrtoInt(copy(bits,l-6,1))]);
7:putpix(i+(2*s+1),j,farben[StrtoInt(copy(bits,l-7,1))]);
8:putpix(i+(2*s+1),j,farben[StrtoInt(copy(bits,l-8,1))]);
9:putpix(i+(2*s+1),j,farben[StrtoInt(copy(bits,l-9,1))]);
10:putpix(i+(2*s+1),j,farben[StrtoInt(copy(bits,l-10,1))]);
11:putpix(i+(2*s+1),j,farben[StrtoInt(copy(bits,l-11,1))]);
12:putpix(i+(2*s+1),j,farben[StrtoInt(copy(bits,l-12,1))]);
13:putpix(i+(2*s+1),j,farben[StrtoInt(copy(bits,l-13,1))]);
14:putpix(i+(2*s+1),j,farben[StrtoInt(copy(bits,l-14,1))]);
15:putpix(i+(2*s+1),j,farben[StrtoInt(copy(bits,l-15,1))]);
end;
end else begin
case summe of
0:pixels[i+1,j]:=farben[StrtoInt(copy(bits,l,1))];
1:pixels[i+1,j]:=farben[StrtoInt(copy(bits,l-1,1))];
2:pixels[i+1,j]:=farben[StrtoInt(copy(bits,l-2,1))];
3:pixels[i+1,j]:=farben[StrtoInt(copy(bits,l-3,1))];
4:pixels[i+1,j]:=farben[StrtoInt(copy(bits,l-4,1))];
5:pixels[i+1,j]:=farben[StrtoInt(copy(bits,l-5,1))];
6:pixels[i+1,j]:=farben[StrtoInt(copy(bits,l-6,1))];
7:pixels[i+1,j]:=farben[StrtoInt(copy(bits,l-7,1))];
8:pixels[i+1,j]:=farben[StrtoInt(copy(bits,l-8,1))];
9:pixels[i+1,j]:=farben[StrtoInt(copy(bits,l-9,1))];
10:pixels[i+1,j]:=farben[StrtoInt(copy(bits,l-10,1))];
11:pixels[i+1,j]:=farben[StrtoInt(copy(bits,l-11,1))];
12:pixels[i+1,j]:=farben[StrtoInt(copy(bits,l-12,1))];
13:pixels[i+1,j]:=farben[StrtoInt(copy(bits,l-13,1))];
14:pixels[i+1,j]:=farben[StrtoInt(copy(bits,l-14,1))];
15:pixels[i+1,j]:=farben[StrtoInt(copy(bits,l-15,1))];
end;
end;
until j>height;
i:=i+(2*s+1);
until i>wieweit;
end;
form1.caption:=
'Zellular-Automaten: 0 = weiß, 1 = rot, 2 = grün, 3 = blau, 4 =
gelb';
end;

12.3 Weitere "Automaten"

Der wohl bekannteste zelluläre Automat ist das berühmte "Spiel des Lebens" (Game of Life), das der Mathematiker John Horton Conway von der Universität Cambridge in den sechziger Jahren erfunden hat. Dabei ist jede Zelle in einem von zwei Zuständen, nämlich lebendig oder tot. Die Regeln sind sehr einfach: Eine tote Zelle erwacht nach dem Ticken der Uhr ("Zeitschritt") zu neuem Leben, wenn sie davor genau drei lebendige Nachbarn besessen hat. Eine lebendige Zelle dagegen stirbt mit dem nächsten Ticken, wenn sie von weniger als zwei oder mehr als drei Nachbarn umgeben ist. Diese zwei simplen Regeln verleihen dem Automaten ein erstaunlich reichhaltiges Verhaltensrepertoire, das allein von der Anfangskonfiguration aus toten und lebendigen Zellen abhängt.

Die Mischmasch-Maschine ist eigentlich kein zellulärer Automat, sondern das Rezept zur Konstruktion einer ganzen Klasse davon. Eine spezielle Maschine erhält man, indem man für vorgegebene Parameter bestimmte Werte einsetzt. Um mehr Zustände bildhaft beschreiben zu können, haben Gerhard und Schuster Conways Metapher leicht abgewandelt: Eine Zelle im Zustand 0 nennen sie "gesund" und eine im höchstmöglichen Zustand n "krank"; die Zustände dazwischen drücken den Grad der "Infektion" aus - je näher die Zustandsnummer an n liegt, desto stärker ist die Zelle infiziert. Die Mischmasch-Maschine wendet auf jede Zelle eine von drei Regeln an, je nachdem, ob die Zelle gesund, infiziert oder krank ist.

Der Zustand einer gesunden Zelle nach dem nächsten Zeitschritt hängt von der Anzahl A infizierter Zellen und der Anzahl B kranker Zellen in iherer Nachbarschaft sowie von zwei Parametern k1 und k2 ab. Die entsprechende Formel lautet [A/k1]+[B/k2]. Dabei bedeuten die eckigen Klammern, dass vom Ergebnis der Division jeweils die Nachkommazahlen abzuschneiden sind.

Der Zustand von bereits infizierten Zellen verschlechtert sich im Laufe der Zeit meist noch. Zur Zeit t+1 it er gleich der Summe zweier Zahlen, nämlich des Infektionsgrades in der Nachbarschaft der Zelle zur Zeit t und einer unveränderlichen Größe g, die bestimmt, wie schnell die Infektion sich unter den Zellen ausbreitet. Um den Infektionsgrad zu erhalten, muss man die Summe S der Zustandszahlen der Zelle selbst und aller Zellen in ihrer Nachbarschaft durch die Anzahl A der infizierten Zellen teilen. Eine zur Zeit t infizierte Zelle geht also zur Zeit t +1 in den Zustand über, der durch die Formel [S/A] + g gegeben wird. Eine infizierte Zelle kann allerdings nicht kränker als n werden - ergibt die letzte Formel eine größere Zahl, wird statt dessen einfach n genommen.

Eine zur Zeit t schon kranke Zelle (also eine im Zustand n) wird auf wundersame Weise zur Zeit t + 1 wieder gesund, geht also in den Zustand 0 über.

Schließlich muss noch festgelegt werden, wie die "Nachbarschaft" einer Zelle aussieht. Traditionellerweise gibt es bei zellulären Automaten zwei Arten von Nachbarschaften: Die Von-Neumann-Nachbarschaft, die aus vier Zellen besteht, die mit der Zelle eine Kante gemeinsam haben. Bei der Moore-Nachbarschaft kommen außerdem die vier Zellen dazu, deren Ecke an die jeweilige Zelle grenzt.

12.4 Fraktale

Fraktale Geometrie wird durch Algorithmen beschrieben, die beispielsweise in einer Art "Rückkopplung" definiert sind. In einem relativ einfachen Beispiel verwenden wir lineare Strukturen, die innerhalb eines Computer-Programmes rekursiv aufgerufen werden.

Beispiel: Die Koch-Kurve

Ausgangspunkt der Koch-Kurve ist eine gerade Linie, die in drei gleiche Strecken geteilt wird. Über dem mittleren Teilstück wird ein gleichseitiges Dreieck errichtet.

Auf jedes gerade Teilstück der entstandenen Kurve lässt sich das Verfahren wiederholen - es entsteht eine immer stärker "gezackte" Kurve.

Wir können ein lineares Fraktal, wie es die Koch-Kurve darstellt, durch Rekursionen erreichen: Dabei ruft eine Prozedur sich selber mit geänderten Parametern auf: Beachte dies in der Prozedur "kochkurve": 



unit U_koch;
...
type
TForm1 = class(TForm)
MainMenu1: TMainMenu;
...
Kochkurve1: TMenuItem;
Lschen1: TMenuItem;
procedure fd(strecke:real);
procedure rt(alpha:real);
procedure kochkurve(strecke:real; ebene:byte);
procedure Kochkurve1Click(Sender: TObject);
procedure FormCreate(Sender: TObject);
procedure Lschen1Click(Sender: TObject);
...
end;
var
Form1: TForm1;
x,y,a,xneu,yneu,alpha,strecke:real;
ebene:byte;
implementation
...
procedure TForm1.fd(strecke:real);
begin
xneu:=x+strecke*cos(a);
yneu:=y-strecke*sin(a);
Image1.Canvas.LineTo(round(xneu),round(yneu));
x:=xneu;
y:=yneu;
end;
procedure TForm1.rt(alpha:real);
begin
a:=a+alpha*pi/180;
end;
procedure TForm1.Drucken1Click(Sender: TObject);
begin
if PrintDialog1.execute then Print;
end;
procedure TForm1.kochkurve(strecke:real;    ebene:byte);
begin
if ebene <> 0 then begin
kochkurve(strecke/3,ebene-1);
rt(60);
kochkurve(strecke/3,ebene-1);
rt(-120);
kochkurve(strecke/3,ebene-1);
rt(60);
kochkurve(strecke/3,ebene-1);
end else fd(strecke);
end;
procedure Tform1.Kochkurve1Click(Sender: 
Tobject);
var e:byte;
begin
x:=0;
y:=Image1.height/2;
Image1.Canvas.MoveTo(round(x),round(y));
a:=0;
e:=StrToInt(Inputbox('Kochkurve','Zahl der  
Rekursionstiefe:','5'));
kochkurve(image1.width,e);
Image1.Canvas.TextOut(10,image1.height-30,
'Rekursionstiefe '+IntToStr(e));
end;

1. Literatur: Stephen Wolfram, "Software für Mathematik und Naturwissenschaften", Spektrum der Wissenschaft 11/1984