Langton’s Ant: Jak Dwie Zasady Budują Autostradę

Dwa zasady, bez pamięci

Christopher Langton wprowadził to w 1986 roku jako eksperyment myśliwski w dziedzinie sztucznej życiodajności. Ustawienie: nieskończona siatka komórek, każda biała lub czarna, i pojedynczy mrowisko stojące na jednej z komórek, skierowane jednym z czterech kierunków. W każdym kroku stosuje dokładnie dwie zasady, w kolejności: na komórce białej obróć się o 90° w prawo; na komórce czarnej obróć się o 90° w lewo. Następnie odwróć kolor komórki, na której się znajduje, i przesuną się o jeden krok do przodu.

jeśli cell[x][y] == WHITE: dir = turnRight(dir) else: dir = turnLeft(dir) cell[x][y] = flip(cell[x][y]) (x, y) = stepForward(x, y, dir)

if cell[x][y] == WHITE: dir = turnRight(dir)
else:                   dir = turnLeft(dir)
cell[x][y] = flip(cell[x][y])
(x, y) = stepForward(x, y, dir)

Trzy fazy: porządek, chaos, autostrada

Rozpoczynając od pustego siatki, trajektoria muchołówka dzieli się na trzy wyraźnie różne stany. W ciągu pierwszych około 500 kroków buduje małe, prawie symetryczne wzory, niemal krystaliczne. Następnie, w ciągu kolejnych kilku tysięcy kroków, wydaje się, że bezwładnie przemieszcza się w nieprzewidywalny sposób – odwiedzana przestrzeń staje się szorstka i pozbawiona jakiejkolwiek struktury na jakimkolwiek poziomie. Następnie, bez ostrzeżenia, około kroku 9978 dla standardowej warunkowej siatki, zamyka się cykl trwania 104 kroki, który przenosi go o dwie komórki po przekątnej w każdym cyklu i powtarza to w nieskończoność, przynajmniej do tej pory obliczone.

Hipodysa – wciąż nierozwiązana

Pytanie oczywiste — czy każda konfiguracja początkowa ostatecznie buduje autostradę? — nazywa się hipodysą, a do 2026 roku pozostaje nierozwiązana. Wyczerpujące poszukiwania komputerowe obejmujące miliardy konfiguracji początkowych nigdy nie znalazły przykładu zaprzeczającego temu, ale nie istnieje dowód ogólny. Co wiadomo o przypadku pustej siatki: ślad autostrady o 26 komórkach powtarza się co 104 kroki, przesuwając mrówkę dokładnie o (2, −2), a jej kierunek jest ustalony w momencie, gdy pierwsze skręcenie mrówki łamie czwórkową symetrię siatki. Zmiana pojedynczej komórki w konfiguracji początkowej może spowodować, że autostrada pojawi się w zupełnie innym ułożeniu lub zostanie opóźniona o setki tysięcy kroków — forma wrażliwości na warunki początkowe, choć sama układanka jest w pełni deterministyczna i nie jest chaotyczna w sensie systemów dynamicznych.

Turmaty: uogólnianie zachowania mrowców

Rudy Rucker ukuł termin Turmet (Turing + termit) dla ogólnej rodziny: k możliwych kolorów komórek zamiast dwóch, s możliwych stanów wewnętrznych mrówców zamiast jednego oraz tabeli przejścia mapującej (stan, kolor) na (nowy stan, nowy kolor, ruch). Oryginalny Turmet Langtona jest najprostszy – k=2, s=1 — zapisany zwięźle jako ciąg reguł RL (skręć w prawo na kolorze 0, skręć w lewo na kolorze 1). Rozszerz ten ciąg: RLLR tworzy powolną, prawie fraktalną granicę; LLRR generuje szybkie, nieregularne wzrosty bez widocznej autostrady; dłuższe ciągi takie jak LRRRRRLLR produkują struktury okresowe przypominające bilardowe kule z okresami w tysiącach. Turmaty z dwoma lub więcej stanami wewnętrznymi są udowodnione jako Turing Complete – mogą obliczać wszystko, pod warunkiem odpowiedniego początkowego taśmy — co umieszcza te maszyny na granicy uniwersalności obliczeniowej; prosty, jednowarów mrówcowy nie jest znany z tego, że jest to w przypadku jego ostatecznej okresowości, co wykluczyłoby nieograniczone obliczanie, jeśli załoga autostrady się sprawdzi.

Frequently asked questions

Wypróbuj na żywo

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