O mrówce Langtona | Autostrada, reguły i turmity

Reguły

Mrówka chodzi po nieskończonej siatce pól. Każde pole jest białe lub czarne, a mrówka jest zwrócona na północ, wschód, południe albo zachód. Kolor pod jej nogami decyduje o całym następnym ruchu. Na białym polu skręca o 90° w prawo (zgodnie z ruchem wskazówek zegara), maluje pole na czarno i przesuwa się o jedną komórkę. Na czarnym polu skręca o 90° w lewo (przeciwnie do ruchu wskazówek zegara), maluje pole na biało i przesuwa się o jedną komórkę. Nie ma tu losowości. Uruchom ten sam start dwa razy, a dostaniesz ten sam obraz.

Trzy fazy

Uruchom mrówkę na pustej białej siatce, a jej zachowanie podzieli się na trzy znane etapy. 1. Prostota i symetria, od kroku 1 do mniej więcej kroku 500. Ślad jest mały i często symetryczny. 2. Chaos, mniej więcej od kroku 500 do kroku 10 000. Mrówka grzęźnie we własnej ścieżce. Obraz wygląda jak szum, choć każdy krok jest z góry ustalony. 3. Autostrada, po około 10 000 krokach. Mrówka wpada w cykl 104 kroków. Każdy cykl dodaje powtarzający się ukośny blok i przesuwa mrówkę o dwie komórki w bok i dwie do przodu. Gdy cykl raz ruszy na wolnej siatce, trwa w nieskończoność, a mrówka buduje z chaosu prostą autostradę.

Dlaczego to ważne

Mrówka to jedna z najczytelniejszych demonstracji emergencji: skomplikowana, trudna do przewidzenia struktura z garstki lokalnych reguł. Jest też zupełna w sensie Turinga. Przy odpowiednim wzorze startowym ten sam rodzaj reguły może wykonać każde obliczenie, które wykona komputer ogólnego przeznaczenia. Nie potrzebujesz tej maszynerii, by cieszyć się obrazem. Autostrada już jest niespodzianką.

Kolory, kolonie, sześciokąty i turmity

Pomysł rozwinięto w kilku kierunkach. Reguły wielokolorowe zastępują czerń i biel listą skrętów zapisaną jako ciąg liter L i R. RL to klasyczna mrówka. RLR, LLRR i LRRRRRLLR dają każdemu kolorowi własny skręt. Mrówka zapisuje następny kolor z listy, a niektóre z tych reguł zamiast jednej autostrady wyrastają w symetryczne figury geometryczne. Kilka mrówek dzieli jedną siatkę. Gdy ich ślady się spotykają, mogą przeciąć autostradę albo utkać wzór, którego żadna nie zbudowałaby sama. Siatka sześciokątna daje mrówce sześć kierunków. Skręt w prawo lub w lewo ma wtedy 60° zamiast 90°. Turmit ma stan wewnętrzny, niewielką pamięć. Skręt i zapisywany kolor zależą zarówno od komórki, jak i od tego stanu, więc sama reguła zmienia się w trakcie marszu. Spirala, Splot i Dryf w aplikacji to turmity o dwóch stanach i dwóch kolorach.

Odkryj ją w PictorX

Otwórz Mrówkę Langtona, aby uruchomić klasyczną mrówkę, przeskoczyć do fazy chaosu albo zacząć od autostrady. Wpisz regułę skrętów, dodaj mrówki, przełącz siatkę na sześciokąty lub wybierz turmita. Przeciągaj, by przesuwać, przewijaj, by powiększać, maluj komórki i dokładaj mrówki. Zapisz PNG lub otwórz płótno w edytorze PictorX. Połącz ją z Hipotezą Collatza lub Laboratorium reakcji-dyfuzji, aby zobaczyć więcej prostych reguł z zaskakującymi obrazami.

Często zadawane pytania

Kto wymyślił mrówkę Langtona?

Chris Langton w 1986 roku. To dwuwymiarowa maszyna Turinga: jedna mrówka, nieskończona siatka i skręt zależny wyłącznie od koloru bieżącej komórki.

Czy każdy wzór startowy buduje autostradę?

Pusta siatka tak, po około 10 000 krokach, a cykl 104 kroków trwa dalej, gdy mrówka jest już na autostradzie. Inne wzory startowe i inne reguły mogą budować autostrady, pozostawać ograniczone albo rosnąć w innym kształcie. Ulubiony preset „Autostrada” w aplikacji ustawia klasyczną mrówkę tuż po rozpoczęciu cyklu.

Co oznacza ciąg reguły?

Każdy znak to skręt dla jednego koloru. R oznacza skręt w prawo, L w lewo. Po skręcie mrówka zmienia kolor komórki na następny i idzie do przodu. RL to czerń i biel. Dłuższy ciąg to mrówka wielokolorowa.

Czym turmit różni się od mrówki?

Klasyczna mrówka nie ma pamięci poza siatką. Turmit ma dodatkowo stan wewnętrzny. Kolor komórki i ten stan wspólnie wybierają zapisywany kolor, skręt i następny stan.