LinAuto.doc Lineare Automaten (c) 01/91 Reinhard Huppert +----------------------------------------------------------------------+ ! ! ! Eine Hommage an die Königin der Wissenschaften, die ! ! ! ! M A T H E M A T I K ! ! ! +----------------------------------------------------------------------+ 1. Was sind Lineare Automaten ? 2. Wie funktioniert das Programm ? 3. Wer hat's geschrieben, wo gibt's Infos und die Source ? +----------------------------------------------------------------------+ 1. Was sind Lineare Automaten ? Wir betrachten ein (endloses) Band, auf dem lauter Nullen und Einsen in zufälliger Reihenfolge aufgereiht sind: ...001001011001001100001001100100001100110011000010011001100101000110... Dies sei die Generation Nummer 1. Nun picken wir uns eine Stelle x her- aus und betrachten sie und ihre Nachbarn (hier z.B. je 5 Nachbarn rechts und links): ...001001011001001100001001100100001100110011000010011001100101000110... -----+----- Diese 11 Stellen heißen die Umgebung von x. In dieser Umgebung zählen wir jetzt alle Einsen (in unserem Beispiel sind es 4). In einer solchen Umgebung können jetzt 0 oder 1 oder 2 oder... oder 11 Einsen sein, also 12 verschiedene Zustände. Abhängig von diesen Zuständen bestimmen wir, ob die Stelle x in der nächsten Generation eine Null oder eine Eins sein soll. Anschließend gehen wir eine Stelle weiter, betrachten hier die Umgebung und setzen wieder, abhängig vom Zustand der Umgebung, den Wert der Stelle in der nächsten Generation. So bauen wir die gesamte nächste Generation auf, und dann wieder die nächste...ad infinitum. Wir betrachten also die zeitliche Entwicklung des endlosen Bandes. Hier- bei ergeben sich eigenartige Muster und Strukturen. +----------------------------------------------------------------------+ 2. Wie funktioniert das Programm ? Unser Band ist 320 Stellen lang. Der rechte Rand geht wieder in den linken über (ein Kreis). In der ersten Bildschirmzeile steht die erste Generation: ein Null ist gelb dargestellt, eine Eins blau. Diese Anfangs-Generation ist zufällig gewählt und bei jedem Programmdurchlauf eine andere. Die zweite Generation steht in der zweiten Zeile etc. Das Programm betrachtet eine Umgebung von je 5 Nachbarn. Das entstehende Bild (ca. 16 sek) zeigt also 256 Generationen des endlosen Bandes. Hierbei zeigen sich eigenartige Muster, wo man eigentlich vielleicht nur wirres blau-gelbes Chaos erwarten würde. Das Programm hat 2 Menüs: im ersten Menü (Project) wird der Rechenvorgang/ Bildaufbau gestartet mit "RUN". Die Punkte "INFO" und "SAVE PICTURE" werden in einer späteren Version realisiert. Im 2. Menü (Options) legt man die Bedingungen für den Linearen Automaten fest: es sind einige schöne Standart- werte vorgegeben: - Houses sieht aus wie Wolkenkratzer am bergigen Waldrand - Shuttles verschiedene schöne Muster, einige kleine Teile bleiben in sich stabil, wandern aber (life) - Triangles Dreicke - Chaos nun ja, wie der Name schon sagt - Terminator der hört immer auf In der Windowzeile sind die Parameter angegeben: Env = Umgebung (von links nach rechts) und Val = Zustandstabelle (wenn in der Umgebung der Stelle x 5 Einsen sind, dann kriegt die Stelle x in der nächsten Gene- ration den Wert, der an der 5-ten Stelle in der Val-Tabelle steht). - Random hier wird die Umgebung und die Zustandstabelle zu- fällig gesetzt - Symetric Random hier wird die Umgebung auch zufällig, aber rechts und links gleich gesetzt; die Zustandstabelle ganz zufällig - Your Turn hier kann man in ner späteren Version die Umgebung und die Zustandstabelle selber definieren Wie gesagt, hier werden nur die Parameter festgelegt, nach denen der lineare Automat laufen soll. Laufen selbst tut er nur mit dem RUN aus dem ersten Menü. +----------------------------------------------------------------------+ 3. Wer hat's geschrieben, wo gibt's Infos und die Source ? Das Programm wird noch um Einiges erweitert: SavePicture soll möglich werden (Load Picture ist unnötig), sodann die eigene Definition der Umgebung und des Zustände. Ebenso soll man die Generation 1 selber setzen bzw. zufällig erzeugen und dann modifizieren könen. Jetzt hört der Prozess nach 256 Generationen auf, der Bildschirm ist ja voll. Später soll ein Scrollen möglich sein, so daß der Prozeß endlos laufen kann (Abbruch durch MausKlick). Geschrieben hat's ein USER der M-Box (0621 / 801685), ein treuer Vasall der o.g. Königin: Reinhard Huppert Sommergasse 3 6940 Weinheim Wenn Ihr Infos oder die C-Source haben wollt, könnt Ihr mir schreiben.