Mrówka Langtona

Mrówka Langtona to prosty automat komórkowy wymyślony przez Chrisa Langtona. Może być traktowany również jako rozszerzona do dwóch wymiarów bardzo prosta maszyna Turinga.

W każdym kroku wyróżniona jest jedna komórka nazywana "mrówką", która oprócz koloru ma określony także kierunek, w którym się porusza. Mrówka zachowuje się według następujących zasad:

1. jeśli znajduje się na polu białym to obraca się w lewo (o kąt prosty), zmienia kolor pola na czarny i przechodzi na następną komórkę;
2. jeśli znajduje się na polu czarnym to obraca się w prawo (o kąt prosty), zmienia kolor pola na biały i przechodzi na następną komórkę;
3. porusza się na nieskończonej planszy podzielonej na kwadratowe komórki (pola) w dwóch możliwych kolorach: czarnym i białym.

Zadziwiającą własnością tego automatu jest cykl, który pojawia się po pewnym czasie chaotycznego błądzenia. Jednakże, gdy symulacja rozpoczyna się na planszy posiadającej wszystkie pola o tym samym kolorze, wówczas po ok. 10 tysiącach kroków mrówka przestaje poruszać się chaotycznie, tworząc na planszy regularny wzór w kształcie grubego na kilka kratek pasa. Co 104 kroki czasowe pas ten zwiększa swoją długość. Podobnie jak w maszynach Turinga, mimo bardzo prostych zasad zachowanie mrówki przez długi czas od rozpoczęcia symulacji może być bardzo trudne do przewidzenia.

Powstały modyfikacje podstawowych reguł zwiększające liczbę możliwych kolorów (stanów) komórki.

Przykład: 3 mrówki w różnych kolorach

Plik:Langant.gif

Animacja pierwszych 100 kroków

Zobacz też:

• Gra w życie,
• Busy Beaver,
• Turmity.

Linki zewnętrzne

• aplet z wielokolorowymi stanami komórki i programowalnymi mrówkami
• aplikacja w ASM32 z możliwością przybliżania, dodawania przeszkód, zapis&odczyt, odwracanie kolorów, praca krokowa
• Mrówka Langtona (ang.) w encyklopedii MathWorld