PL 
EnglishDomyślny
Українська🐜 Mrówka Langtona — automat komórkowy budujący autostrady
Obserwuj mrówkę Langtona
O mrówce Langtona
Mrówka Langtona to dwuwymiarowy automat komórkowy opracowany przez Christophera Langtona w 1986 roku. „Mrówka” porusza się po nieskończonej siatce czarnych i białych komórek, kierując się dwiema deterministycznymi regułami: na białej komórce skręca o 90° w prawo, zmienia kolor komórki na czarny i przesuwa się o jeden krok naprzód; na czarnej komórce skręca o 90° w lewo, zmienia kolor komórki na biały i idzie dalej. Mimo tych niezwykle prostych reguł mrówka wykazuje złożone zachowanie emergentne — około 10 000 kroków pozornie chaotycznego, pseudolosowego błądzenia — zanim spontanicznie ustabilizuje się w okresowym, ukośnym wzorze „autostrady”, który powtarza się w nieskończoność co 104 kroki. System jest obliczeniowo uniwersalny (Turinga-zupełny): przy dodatkowych stanach kolorów warianty mrówki Langtona mogą symulować dowolne obliczenia.
Symulacja pozwala zmieniać prędkość, włączać wiele mrówek o odrębnych ciągach reguł kolorów (zwanych „turmitami”) oraz obserwować, jak interakcje między mrówkami prowadzą do nieoczekiwanych zachowań zbiorowych. Możesz też dostosować ciąg reguł (np. „LR”, „RLL”, „LRRRRRLLR”), aby uzyskać zupełnie inne struktury emergentne.
Najczęściej zadawane pytania
Dlaczego wzór „autostrady” pojawia się po około 10 000 krokach?
Pojawienie się autostrady około 10 000. kroku jest jednym z najlepiej zbadanych przykładów emergencji w prostych systemach, jednak nie istnieje pełny matematyczny dowód wyjaśniający, dlaczego dzieje się to akurat przy tej liczbie kroków dla pustej siatki startowej. Zjawisko zostało zweryfikowane obliczeniowo dla każdej standardowej konfiguracji początkowej — autostrada jest atraktorem o okresie 104. Udowodnienie, że autostrada zawsze się pojawia dla wszystkich warunków początkowych, pozostaje otwartą hipotezą matematyczną.
Czy mrówka Langtona jest Turinga-zupełna?
Oryginalna, dwukolorowa mrówka Langtona sama w sobie nie została udowodniona jako Turinga-zupełna, ale wielokolorowe warianty zwane turmitami już tak: reguła turmita RL (dwa kolory, dwa stany) została pokazana przez Gajardo, Moreirę i Golesa w 2002 roku jako symulująca automat komórkowy Reguła 110, który jest Turinga-zupełny. Oznacza to, że przy odpowiedniej konfiguracji początkowej turmit może obliczyć dowolną funkcję, jaką potrafi obliczyć współczesny komputer, o ile dysponuje wystarczającą ilością czasu i pamięci.
Czym jest „autostrada” i jak wygląda?
Autostrada to okresowy, ukośny wzór pasków, który mrówka tworzy po zakończeniu chaotycznej fazy przejściowej. Powtarza się dokładnie co 104 kroki, przesuwając się po przekątnej o 2 komórki w każdym okresie. Wizualnie wzór przypomina powtarzający się układ jodełki. Gdy autostrada się już ukształtuje, mrówka nigdy nie wraca do chaotycznego zachowania — autostrada rośnie w nieskończoność, aż mrówka dotrze do krawędzi skończonej siatki.
Co się dzieje, gdy na tej samej siatce umieścimy dwie mrówki?
Dwie mrówki oddziałujące na tej samej siatce mogą dawać ogromną różnorodność wyników w zależności od pozycji startowych i orientacji: w niektórych konfiguracjach obie mrówki tworzą autostrady w różnych kierunkach, w innych dochodzi do złożonej wzajemnej interferencji, która uniemożliwia powstanie którejkolwiek autostrady, a jeszcze inne dają stabilne wzory cykliczne. Systemy z wieloma mrówkami są znacznie trudniejsze do analizy teoretycznej i często bada się je obliczeniowo.
Czym są turmity i jak uogólniają mrówkę Langtona?
Turmit to dwuwymiarowa maszyna Turinga na siatce: oprócz koloru komórki posiada stan wewnętrzny (podobny do stanu głowicy maszyny Turinga), a reguły określają: (nowy kolor komórki, kierunek skrętu, nowy stan wewnętrzny). Oryginalna mrówka Langtona jest najprostszym turmitem, z 1 stanem wewnętrznym i 2 kolorami komórek. Przestrzeń turmitów o 2 stanach i 2 kolorach zawiera 2592 odrębne reguły; garstka z nich tworzy autostrady, część daje wzory chaotyczne, a kilka jest uniwersalnych obliczeniowo.
Czy mrówkę Langtona można badać na innych topologiach siatki?
Tak. Warianty badano na siatkach trójkątnych i sześćokątnych, na torusach (skończonych siatkach z periodycznymi warunkami brzegowymi), a nawet na grafach Cayleya grup. Na torusie mrówka musi w końcu ponownie odwiedzić jakiś stan i wejść w cykl, więc autostrada lub inny okresowy atraktor jest gwarantowany; na nieskończonej siatce zbieżność do autostrady pozostaje hipotezą.
Jaki jest związek między mrówką Langtona a Regułą 110?
Reguła 110 to jednowymiarowy elementarny automat komórkowy, którego Turinga-zupełność udowodnił Matthew Cook w 2004 roku. Związek z mrówką Langtona przebiega przez turmity: wykazano, że reguła turmita odpowiadająca „RL” zawiera w swoim zachowaniu symulacje Reguły 110. Ma to istotne znaczenie, ponieważ osadza Turinga-zupełność systemów turmitów w niezależnie udowodnionym systemie Turinga-zupełnym, zamiast opierać się na bezpośredniej konstrukcji.
Czy mrówka Langtona zawsze tworzy autostradę na pustej siatce?
Dla nieskończonej, pustej (całkowicie białej) siatki początkowej we wszystkich znanych symulacjach obserwowano konsekwentne pojawianie się autostrady około 10 000. kroku. Jednak hipoteza, że dzieje się tak zawsze — niezależnie od rozmiaru siatki czy precyzji symulacji — nigdy nie została formalnie udowodniona. Dla niepustych konfiguracji początkowych mrówka może nigdy nie ustabilizować się w autostradzie; zależy to bardzo wrażliwie od początkowego wzoru czarnych komórek.
Jaki jest związek mrówki Langtona z badaniem emergencji?
Mrówka Langtona jest klasycznym przykładem emergencji: złożone zachowanie globalne (autostrada) wyłania się z lokalnych reguł, w których nie ma żadnego jawnego zakodowania tego wzoru. Jest badana w teorii złożoności, badaniach nad sztucznym życiem oraz filozofii nauki jako dowód na to, że złożony porządek może samoorganizować się z trywialnie prostych reguł. Christopher Langton wykorzystał ją jako motywujący przykład przy zakładaniu programu sztucznego życia Santa Fe Institute.