Ant Langtona: Dwie Reguły, Jeden Ant i Pojawiająca Się Autostrada

Dwa zasady, mrówka i nieskończony szachownicowy grid

Mrówka Langtona, wprowadzona przez komputerowego naukowca Chrisa Langtona w 1986 roku, jest jedną z najprostszych systemów w informatyce, która pokazuje, że może wygenerować naprawdę skomplikowane i nieprzewidywalne zachowanie. Układ: nieskończona szachownica kwadratowych komórek, każda z której może być czarna lub biała; pojedyncza „mrówka” siedząca na jednej komórce i obracająca się w jedną z czterech kierunków. W każdym kroku mrówka follows dokładnie dwa zasady, oparte tylko na barwie komórki, na której aktualnie stoi:

na białej komórce: obróć się o 90 stopni w prawo, zamień komórkę na czarną, przesuń się o jedno pole na czarnej komórce: obróć się o 90 stopni w lewo, zamień komórkę na białą, przesuń się o jedno pole demo live · mrówka rzeźbi ścieżkę po szachownicy czarnej i białej● LIVE Formalnie to dwuwymiarowy maszyn Turing: mrówka jest głową do czytania i zapisywania, a szachownica jest nieskończoną tapecią rozszerzoną na dwa wymiary, a te dwa zasady stanowią jej całe programowanie. Nic nie ukrywamy i nic nie jest losowe — przyszłość mrówki jest całkowicie wyznaczona przez jej pozycję początkową, orientację oraz powyższe dwa zasady.

on a WHITE cell: turn 90° clockwise, flip the cell to BLACK, move forward one cell
on a BLACK cell: turn 90° counter-clockwise, flip the cell to WHITE, move forward one cell

Trzy fazy: chaos, chaos, a następnie autostrada

Zaczynając od siatki całkowicie białej, ścieżka anty przebiega przez trzy widocznie różne fazy. W ciągu około pierwszych 500 kroków anta rysuje małe, proste, często symetryczne wzory, powtarzając się w pobliżu miejsca startowego. Od około kroku 500 do około 10 000, wzór wygląda prawdziwie chaotycznie — gęste, nieporząkane rysunki bez jasnej struktury, typu ścieżki, która wydaje się mogłaby kontynuować się w nieskończoność bez nigdy osiągnięcia równowagi.

Następnie, bez ostrzegawczej sygnału, około kroku 10 000 (liczba ta może się nieco różnić w zależności od orientacji początkowej), anta ucieka z chaotycznego chaosu i zaczyna budować „autostradę” — przekątną pasma 104 kroków powtarzającego się nieskończenie, przenosząc antę wprost do nieskończoności w jednolitej ogólniej kierunku, jednocześnie śladując tym samym małym powtarzalnym wzorcowy kształt. Nikt nie udowodnił matematycznie, dlaczego autostrada musi zawsze pojawiać się z każdej konfiguracji początkowej na pustej siatce — to fakt empiryczny, obserwowany w każdym przeprowadzonym symulacji, ale ogólny problem czy anta zawsze buduje autostradę z dowolnej skończonej początkowej konfiguracji czarnych i białych kwadracików nadal pozostaje otwartym zagadnieniem w matematyce automata komórkowych.

Dlaczego tak proste zasady mogą Cię zdziwić

Ant Langtona należy do tej samej rodziny idei co elementary cellular automata Wolframa i Gra Życia konwaiowskiego: minimalne lokalne zasady, stosowane deterministycznie i powtarzane, mogą wygenerować zachowania znacznie bardziej skomplikowane niż sugerują sama te zasady — temat często nazywany emergencją. Jest to również ulubiona ilustracja dlaczego symulowanie krok po kroku jest często jedynym sposobem na zrozumienie, co zrobi proste i deterministyczne system: nie ma skróconej formuły, która powiedzie, gdzie będzie ant na milionie kroku bez rzeczywistej wykonania wszystkich miliona kroków, a właściwość ta jest blisko związana z pojęciem niezredukowalności obliczeniowej.

Warianty rozszerzają ideę dodając więcej niż dwie kolory i więcej niż dwa zasady obracania — niektóre z nich generują jeszcze bardziej skomplikowane struktury, w tym niektóre zdolne do tego samego rodzaju uniwersalnej obliczeniowej komputacji znalezionej w Grze Życia konwaiowskiej.

Często zadawane pytania

Wypróbuj na żywo

Wszystko powyżej działa bezpośrednio w Twojej przeglądarce — otwórz Langton's Ant i zmieniaj parametry podczas działania. Nic nie jest instalowane ani przesyłane na serwer, cały model działa w jednej karcie.