Mrówka Langtona

Mrówka Langtona po 11 000 kroków. Czerwony piksel pokazuje lokalizację mrówki.

Mrówka Langtona to dwuwymiarowa, uniwersalna maszyna Turinga z bardzo prostym zestawem reguł, ale złożonym zachowaniem emergentnym . Został wynaleziony przez Chrisa Langtona w 1986 roku i działa na kwadratowej siatce czarnych i białych komórek. Uniwersalność . Pomysł został uogólniony na kilka różnych sposobów, takich jak turmity , które dodają więcej kolorów i więcej stanów.

Zasady

Animacja pierwszych 200 kroków mrówki Langtona

Kwadraty na płaszczyźnie mają różne kolory, czarne lub białe. Arbitralnie identyfikujemy jeden kwadrat jako „mrówkę”. Mrówka może podróżować w każdym z czterech głównych kierunków na każdym kroku. „Mrówka” porusza się zgodnie z poniższymi zasadami:

  • Na białym kwadracie obróć o 90° zgodnie z ruchem wskazówek zegara, odwróć kolor kwadratu i przesuń się o jedną jednostkę do przodu
  • Na czarnym kwadracie obróć o 90° w kierunku przeciwnym do ruchu wskazówek zegara, odwróć kolor kwadratu i przesuń się o jedną jednostkę do przodu

Mrówkę Langtona można również opisać jako automat komórkowy , w którym siatka ma kolor czarny lub biały, a kwadrat „mrówki” ma jeden z ośmiu różnych kolorów przypisanych do zakodowania kombinacji stanu czarno-białego i aktualnego kierunku ruchu mrówki .

Tryby zachowania

Te proste zasady prowadzą do złożonych zachowań. Podczas startu na całkowicie białej siatce widoczne są trzy różne tryby zachowania.

  1. Prostota. Podczas pierwszych kilkuset ruchów tworzy bardzo proste wzory, często symetryczne.
  2. Chaos. Po kilkuset ruchach pojawia się duży, nieregularny wzór czarno-białych kwadratów. Mrówka śledzi pseudolosową ścieżkę do około 10 000 kroków.
  3. Pojawiające się zamówienie. W końcu mrówka zaczyna budować powtarzający się wzór „autostrady” składający się ze 104 kroków, który powtarza się w nieskończoność.

Wszystkie przetestowane skończone konfiguracje początkowe ostatecznie zbiegają się do tego samego powtarzalnego wzorca, co sugeruje, że „autostrada” jest atraktorem mrówki Langtona, ale nikt nie był w stanie udowodnić, że jest to prawdą dla wszystkich takich konfiguracji początkowych. Wiadomo tylko, że trajektoria mrówki jest zawsze nieograniczona niezależnie od początkowej konfiguracji – jest to znane jako Cohena-Konga .

Uniwersalność obliczeniowa

W 2000 roku Gajardo i in. pokazał konstrukcję, która oblicza dowolny obwód logiczny na podstawie trajektorii pojedynczego wystąpienia mrówki Langtona. Dodatkowo możliwe byłoby symulowanie dowolnej maszyny Turinga przy użyciu trajektorii mrówki do obliczeń. Oznacza to, że mrówka jest zdolna do uniwersalnych obliczeń.

Rozszerzenie do wielu kolorów

Greg Turk i Jim Propp rozważali proste rozszerzenie mrówki Langtona, w którym zamiast tylko dwóch kolorów zastosowano więcej kolorów. Kolory są modyfikowane w sposób cykliczny. Stosowany jest prosty schemat nazewnictwa: dla każdego z kolejnych kolorów litera „L” lub „R” służy do wskazania, czy należy skręcić w lewo, czy w prawo. Mrówka Langtona ma w tym schemacie nazewnictwa nazwę „RL”.

Niektóre z tych rozszerzonych mrówek Langtona wytwarzają wzory, które w kółko stają się symetryczne . Jednym z najprostszych przykładów jest mrówka „RLLR”. Wystarczającym warunkiem, aby tak się stało, jest to, aby nazwa mrówki, widziana jako lista cykliczna, składała się z następujących po sobie par identycznych liter „LL” lub „RR”. (określenie „lista cykliczna” wskazuje, że ostatnia litera może łączyć się z pierwszą) Dowód dotyczy płytek Truchet .

  • Kilka przykładowych wzorów w wielokolorowym rozszerzeniu mrówek Langtona:
  • RLR: Grows chaotically. It is not known whether this ant ever produces a highway.

    RLR: Rośnie chaotycznie. Nie wiadomo, czy ta mrówka kiedykolwiek zbuduje autostradę.

  • LLRR: Grows symmetrically.

    LLRR: Rośnie symetrycznie.

  • LRRRRRLLR: Fills space in a square around itself.

    LRRRRRLLR: Wypełnia przestrzeń w kwadracie wokół siebie.

  • LLRRRLRLRLLR: Creates a convoluted highway.

    LLRRRLRLRLLR: Tworzy zawiłą autostradę.

  • RRLLLRLLLRRR: Creates a filled triangle shape that grows and moves.

    RRLLLRLLLRRR: Tworzy wypełniony kształt trójkąta, który rośnie i porusza się.

  • L2NNL1L2L1: Hexagonal grid, grows circularly.

    L 2 NNL 1 L 2 L 1 : Sześciokątna siatka, rośnie kołowo.

  • L1L2NUL2L1R2: Hexagonal grid, spiral growth.

    L 1 L 2 NUL 2 L 1 R 2 : Sześciokątna siatka, spiralny wzrost.

  • R1R2NUR2R1L2: Animation.

    R 1 R 2 NUR 2 R 1 L 2 : Animacja.

Sześciokątna siatka pozwala na maksymalnie sześć różnych obrotów, oznaczonych tutaj jako N (bez zmian), R 1 (60° zgodnie z ruchem wskazówek zegara), R 2 (120° zgodnie z ruchem wskazówek zegara), U (180°), L 2 (120° przeciwnie do ruchu wskazówek zegara). zgodnie z ruchem wskazówek zegara), L 1 (60° przeciwnie do ruchu wskazówek zegara).

Rozszerzenie na wiele stanów

Główny artykuł: Turmit

Dalszym rozszerzeniem mrówek Langtona jest rozważenie wielu stanów maszyny Turinga - tak jakby sama mrówka miała kolor, który może się zmieniać. Te mrówki nazywane są turmitami , co jest skrótem od „ termitów maszyny Turinga ”. Typowe zachowania obejmują tworzenie autostrad, chaotyczny wzrost i spiralny wzrost.

  • Kilka przykładowych turmitów:
  • Spiral growth.

    Wzrost spiralny.

  • Semi-chaotic growth.

    Wzrost pół chaotyczny.

  • Production of a highway after a period of chaotic growth.

    Produkcja autostrady po okresie chaotycznego wzrostu.

  • Chaotic growth with a distinctive texture.

    Chaotyczny wzrost o charakterystycznej teksturze.

  • Growth with a distinctive texture inside an expanding frame.

    Wzrost o charakterystycznej fakturze wewnątrz rozszerzającej się ramy.

  • Constructing a Fibonacci spiral.

    Konstruowanie spirali Fibonacciego .

  • Constructing a growing diamond

    Konstruowanie rosnącego diamentu

Rozszerzenie na wiele mrówek

Kolonia (jako oscylator absolutny) buduje trójkąt

Wiele mrówek Langtona może współistnieć na płaszczyźnie 2D, a ich interakcje dają początek złożonym automatom wyższego rzędu, które wspólnie budują różnorodne zorganizowane struktury.

Istnieją różne sposoby modelowania ich interakcji, a wyniki symulacji mogą silnie zależeć od dokonanych wyborów.

Można wybrać, aby wszystkie mrówki siedzące na tym samym kwadracie jednocześnie dokonały tej samej zmiany na taśmie. Jest film na YouTube pokazujący symulację takich wielokrotnych interakcji mrówek. Istnieje również rodzina kolonii, która jest oscylatorem absolutnym o okresie liniowym 4(8n+3).

Wiele turmitów może współistnieć na płaszczyźnie 2D, o ile istnieje reguła określająca, co się stanie, gdy się spotkają. Ed Pegg Jr. rozważał mrówki, które mogą na przykład skręcać zarówno w lewo, jak iw prawo, dzieląc się na dwie części i unicestwiając się nawzajem, gdy się spotkają.

Zobacz też

  1. ^ Langton, Chris G. (1986). „Badanie sztucznego życia za pomocą automatów komórkowych” (PDF) . Physica D: Zjawiska nieliniowe . 22 (1–3): 120–149. Bibcode : 1986PhyD...22..120L . doi : 10.1016/0167-2789(86)90237-X . hdl : 2027.42/26022 .
  2. ^ a b c   Gajardo, A .; Moreira, A.; Goles, E. (15 marca 2002). „Złożoność mrówki Langtona” (PDF) . Dyskretna matematyka stosowana . 117 (1–3): 41–50. arXiv : nlin/0306022 . doi : 10.1016/S0166-218X(00)00334-6 . S2CID 1107883 .
  3. ^ Pratchett Terry (1999). Nauka Świata Dysku .
  4. ^   Bunimowicz, Leonid A.; Troubetzkoy, Serge E. (1992). „Właściwości powtarzalności sieciowych gazowych automatów komórkowych Lorentza”. Dziennik fizyki statystycznej . 67 (1–2): 289–302. Bibcode : 1992JSP....67..289B . doi : 10.1007/BF01049035 . S2CID 121346477 .
  5. ^ Stewart, I. (1994). „The Ultimate w anty-cząsteczkach” (PDF) . nauka jestem . 271 (1): 104–107. Bibcode : 1994SciAm.271a.104S . doi : 10.1038/scientificamerican0794-104 . Zarchiwizowane od oryginału (PDF) w dniu 3 marca 2016 r . Źródło 6 maja 2013 r .
  6. Bibliografia   _ Propp, J.; Sutherland S.; Troubetzkoy, S. (1995). „Dalsze podróże z moją mrówką”. Kolumna rozrywki matematycznej, inteligencja matematyczna . 17 : 48–56. arXiv : matematyka/9501233 . doi : 10.1007/BF03024370 . S2CID 123800756 .
  7. Bibliografia _ „Turmit” . Z MathWorld — zasób internetowy firmy Wolfram, stworzony przez Erica W. Weissteina . Źródło 15 października 2009 . {{ cite journal }} : Cite journal wymaga |journal= ( pomoc ) .
  8. Bibliografia _ Fatès, N. (2012). „Solidność modeli wieloagentowych: przykład współpracy między Turmites z aktualizacją synchroniczną i asynchroniczną” (PDF) . Systemy złożone . 21 (3): 165–182. doi : 10.25088/ComplexSystems.21.3.165 .
  9. Bibliografia _ „Zagadki matematyczne” . Źródło 15 października 2009 . .

Linki zewnętrzne

Pobrano z „ https://en.wikipedia.org/w/index.php?title=Langton%27s_ant&oldid=1115853185 ”