Mrówka Langtona

Mrówka Langtona

Mrówka Langtona to prosty automat komórkowy stworzony przez Chrisa Langtona w 1986 roku, który może być rozpatrywany jako rozwinięcie maszyny Turinga w dwóch wymiarach. W każdym kroku na planszy wyróżniona jest jedna komórka, nazywana „mrówką”, która posiada określony kolor oraz kierunek ruchu.

Zasady ruchu mrówki

Mrówka porusza się zgodnie z następującymi zasadami:

• Na polu białym: obraca się w prawo o 90°, zmienia kolor pola na czarny i przechodzi do następnej komórki.
• Na polu czarnym: obraca się w lewo o 90°, zmienia kolor pola na biały i przechodzi do następnej komórki.

Plansza jest nieskończona i składa się z kwadratowych komórek w dwóch kolorach: czarnym i białym. Początkowo wszystkie komórki są białe.

Chao i wzory

Po kilku pierwszych krokach mrówka tworzy chaotyczny wzór na planszy. Jednak po około 10 tysiącach kroków zaczyna się formować charakterystyczny wzór, zwany „autostradą”. Zjawiskiem interesującym jest to, że po pewnym czasie chaotycznego poruszania się, mrówka wchodzi w cykl. Gdy symulacja rozpoczyna się na planszy z jednolitym kolorem, po około 10 tysiącach kroków mrówka przestaje poruszać się chaotycznie, tworząc regularny wzór w kształcie pasa, który co 104 kroki wydłuża się.

Modyfikacje i różnorodność

Wprowadzono modyfikacje, które zwiększają liczbę kolorów (stanów) komórek. Interesujące wyniki uzyskuje się również, gdy mrówka napotyka przeszkody lub gdy na planszy działa kilka mrówek równocześnie.

Przykłady

Przykładami mogą być symulacje z trzema mrówkami Langtona, które są reprezentowane przez różne kolory. Poniżej znajduje się animacja pierwszych 200 kroków automatu.