Willkommen! Anmelden Ein neues Profil erzeugen

Erweiterte Suche

Langtons Ameise

geschrieben von Neo 
In diesem Forum können zur Zeit keine Beiträge verfasst werden. Bitte versuche es später noch einmal.
Neo
Langtons Ameise
30. October 2005 19:22
Hallo,

Ich habe nur mal zwei kleine Fragen zu Langtons Ameise.
(http://de.wikipedia.org/wiki/Ameise_%28Turingmaschine%29)
Handelt es sich bei Langtons Ameise um ein chaotisches System?
Und ist die Straße, die den Endzustand darstellt ein Attraktor?
(temporärer Gleichgewichtszustand im Phasenraum wie zum Beispiel ein Anfangs- oder Endzustand eines dynamischen Systems)





1-mal bearbeitet. Zuletzt am 30.10.05 19:53.
Peter
Re: Langtons Ameise
31. October 2005 09:23
Gute Frage.

Keine Ahnung, ob man Chaostheoriebegriffe auf solche "computational problems" anwenden kann. Damit der Begriff des Attraktors sinnvoll ist, müsste man zunächst die Freiheitsgrade erhöhen. Z.B. könnte die Ameise auf einem nichtweißen Blatt starten. Wenn sich die Straße tatsächlich bei mehreren Anfangskonfigurationen bildet, ist sie schon so eine Art Attraktor, oder?
Neo
Re: Langtons Ameise
31. October 2005 15:24
@Peter
Bislang ist so viel ich weiß noch kein Anfangszustand gefunden worden, bei dem die Ameise keine Straße baut. (Allerdings kann man normalerweise nicht wiederlegen, dass sie irgendwann keine Straße baut, weil es bei bestimmten Anfangsbedingungen einfach sehr lange dauern könnte und man nicht vorhersagen kann, ob sie diese Straße bauen wird oder nicht. Eine Möglichkeit wäre ein anderer Zyklus, der sich immer regelmäßig wiederholt.)
Peter
Re: Langtons Ameise
31. October 2005 16:44
@Neo
Witzig. Die Straße scheint tatsächlich eine Art Attraktor zu sein. (Hier ist noch ein Link dazu: http://www.wissenschaft-online.de/abo/spektrum/archiv/550).
Auch interessant:
Die Frage, ob eine bestimmte Regelkette eine Straße hervorbringt oder nicht, entspricht dem Turingschen Halteproblem - eine allgemeine Lösung ist also prinzipiell unmöglich.

@Ameise
Baust Du schon Autobahnen oder bist Du noch in Deiner chaotischen Phase?
Neo
Re: Langtons Ameise
31. October 2005 21:11
Hi,

Ich bin mir jetzt doch wieder ziemlich sicher, dass es sich um ein chaotisches System hadelt.

@Peter:
Jop, das mit dem Turingschen Halteproblem habe ich ja im vorherigen Post erwähnt:
>>Allerdings kann man normalerweise nicht wiederlegen, dass sie irgendwann keine Straße baut, weil es bei bestimmten Anfangsbedingungen einfach sehr lange dauern könnte und man nicht vorhersagen kann, ob sie diese Straße bauen wird oder nicht. Eine Möglichkeit wäre ein anderer Zyklus, der sich immer regelmäßig wiederholt.<<
Ich habe mir aber gedacht, dass das etwas zu tief in die Theoretische Informatik geht um es hier explizit zu erwähnen.

Ich habe Langtons Ameise nachprogrammieren, wehalb ich auch eine eigene Definition geschrieben hatte.
Aber wie gesagt wollte ich ggf. das mit dem Attraktor
noch hinzufügen.
Ich poste einfach mal meine Definition (ohne Turingmaschinenkram)
für die, die das Programm noch nicht kennen:

Chris Langtons Ameise ist ein einfaches Beispiel für ein komplexes System,
dass sowohl chaotisches Verhalten als auch komplexe geordnete Strukturen
hervorbringen kann, obwohl alle Verhaltensregeln feststehen und streng deterministisch sind:

Eine Ameise sitzt auf einem (unendlich-)großen weißen, quadratisch kariertem Feld
und blickt in Richtung eines Nachbarfeldes.

Wenn das Feld, auf dem sie sitzt, weiß ist, dann färbt sie es schwarz,
dreht sich um 90 Grad nach rechts und geht auf das Feld, dass vor ihr liegt.

Wenn das Feld, auf dem sie sitzt, schwarz ist, dann färbt sie es weiß,
dreht sich um 90 Grad nach links und geht auf das Feld, dass vor ihr liegt.


Man kann nun das Verhalten der Ameise unterteilen:

In der ersten Phase, während der ersten hundert Schritte entstehen einfache,
symmetrisch erscheinende Formen.

In der zweiten Phase, ungefähr bis zum 10.000 Schritt, sind die Muster chaotisch
und undurchsichtig.

In der Dritten Phase bildet die Ameise dann in einem unendlichen Zyklus
von 104 Schritten eine regelmäßige, diagonale Straße.

Der Witz an der Sache ist, dass man sagen kann,
dass man alle Regeln des Ameise Universums kennt,
aber trotzdem keine Vorhersagen machen kann,
ohne dass man es ausprobiert hat. In einer leicht
abgewandelten Umwelt könnte die Ameise außerdem ein völlig anderes
Verhalten aufweisen und am Schluss vielleicht eine regelmäßige
Straße mit einem anderen Zyklus bauen (deterministisches chaos).
Von den Regeln lässt sich also nicht auf die von uns
erkennbaren Verhaltensweisen schließen.
Wir erkennen diese Verhaltensmuster als Regeln, die
auf den Grundregeln aufbauen.
Weil diese Regeln sich erst aus "der Bewegung heraus"
und sich nicht unmittelbar aus unseren Regeln ergeben,
nennt man sie "emergent", sie sind also hervortretende
Regeln auf einer höheren Ebene.
Ähnlich verhält es sich mit der Atomphysik und dem Leben,
bzw mit Physik Biologie und .

Überträgt man diesen Sachverhalt auf eine Weltformel
("Theory of Everything"), hilft uns die
Ameise zu erkennen, dass die
Wahrscheinlichkeit eine solche Formel für unsere Zwecke
zu verwenden, geschweige denn sie zu verstehen
verschwindend gering ist, selbst wenn wir sie (er)finden
könnten.

Ist eine Art Zusammenfassung von der Definition in Wikipedia und
"Die Gelehrten der Scheibenwelt" von Terry Pratchett.



3-mal bearbeitet. Zuletzt am 01.11.05 07:18.
Re: Langtons Ameise
02. November 2005 00:29
@Peter :
Nee ich bin noch in der chaotischen Phase :) .

@Neo : in welcher Sprache programmierst du ? Ich würd gern ein paar
Fraktale programmieren , bzw hab auch schon Programme geschrieben die
erfolgreich compiliert wurden(in C und Pascal) , aber der Bildschirm
bleibt immer schwarz :( . Mit dem Grafikmodus das funzt irgendwie nicht .
Hast vielleicht ´n Tipp für mich ??
Neo
Re: Langtons Ameise
02. November 2005 17:26
@Ameise:
>>in welcher Sprache programmierst du ?<<
Momentan programmiere ich mit Delphi, also mit objekt pascal.
(Aber nur weil ich dazu gezwungen werde, C und Java gefallen mir besser.)

>> Ich würd gern ein paar Fraktale programmieren , bzw hab auch schon Programme geschrieben die erfolgreich compiliert wurden(in C und Pascal) , aber der Bildschirm
bleibt immer schwarz sad smiley . Mit dem Grafikmodus das funzt irgendwie nicht .<<
Schrecklich, das erinnert mich doch gleich an meine Informatikstunden ;(
Da machen wir auch nix mit Grafik (langweilig und nicht anschaulich).

>>Hast vielleicht ´n Tipp für mich ??<<
Also ich würde dir raten es mal mit Borlands C++ oder Delphi zu probieren,
weil du da sogar gleich am Anfang etwas zu sehen bekommst (ein bisschen nach dem Motto WYSIWYG).

Die Alternative ist sich mit der GDI (Graphics Device Interface) von Windows auseinanderzusetzen. OpenGL ist die plattformunabhängige Variante.
DirektX wird anscheinend bald veraltet sein (Wikipedia zufolge inkompatibel zur nächsten Generation für Vista).
Das ist allerdings etwas komplizierter, also nur wenn du viel Zeit hast :)




4-mal bearbeitet. Zuletzt am 18.11.05 17:55.