Jak to działa?
Gra w życie Johna Conwaya (1970)
Plansza to kratka komórek. Każda jest żywa albo martwa i ma 8 sąsiadów (także po skosie). W każdym pokoleniu wszystkie komórki naraz liczą żywych sąsiadów N i stosują jedną regułę:
Zapis B/S (ang. born / survive) wypisuje liczby sąsiadów, przy których komórka się rodzi i przy których przeżywa. Gra Conwaya to B3/S23; zmieniając cyfry, dostajesz inne światy: HighLife, Seeds, Day & Night, Maze.
Emergencja: więcej niż suma części
Nikt nie zaprogramował szybowca. Reguła mówi tylko o pojedynczej komórce i jej sąsiadach, a mimo to pojawiają się „obiekty”, które się poruszają, zderzają, rozmnażają i giną. Takie wyłanianie się złożonego zachowania z prostych zasad nazywamy emergencją. Podobnie z prostych oddziaływań powstają ławice ryb, korki na drogach czy wzory na muszlach.
Komputer zbudowany z szybowców
Działo Gospera wystrzeliwuje szybowiec co 30 pokoleń — to strumień bitów: szybowiec oznacza 1, luka oznacza 0. Gdy dwa strumienie się krzyżują, odpowiednio ustawione szybowce anihilują przy zderzeniu, więc działa i zderzenia działają jak bramki logiczne NIE, I oraz LUB. Z bramek i pamięci da się złożyć dowolny komputer, dlatego gra w życie jest Turing-zupełna: może obliczyć wszystko, co da się obliczyć. Konstrukcję naszkicowali Berlekamp, Conway i Guy w książce Winning Ways (1982), a w 2000 r. Paul Rendell zbudował w grze działającą maszynę Turinga.
Automaty komórkowe
Ogólnie automat komórkowy to siatka komórek, skończona liczba stanów i jedna lokalna reguła stosowana wszędzie jednocześnie. Pomysł pochodzi od Johna von Neumanna i Stanisława Ulama — matematyka ze Lwowa — z lat 40. XX wieku. Dziś automatami modeluje się pożary lasów, krystalizację, ruch uliczny i wzrost tkanek.
Automaty jednowymiarowe (Wolfram)
Komórki leżą w jednym rzędzie, a kolejne pokolenia rysujemy jedno pod drugim — obraz pokazuje upływ czasu. Nowy stan zależy od komórki i jej dwóch sąsiadów: to 2³ = 8 możliwych sąsiedztw, a każde może dać 0 lub 1, więc reguł jest 2⁸ = 256. Stephen Wolfram ponumerował je w 1983 r.: wyniki dla sąsiedztw 111, 110, …, 000 czytamy jak liczbę dwójkową.
Reguła 90 to po prostu sit+1 = si−1 ⊕ si+1 (alternatywa wykluczająca). Startując od jednej komórki, w wierszu t dostajemy dwumiany Newtona (t⁄k) mod 2 — trójkąt Pascala, w którym zostawiamy tylko liczby nieparzyste. Wychodzi trójkąt Sierpińskiego, fraktal. Więcej fraktali znajdziesz w eksperymencie Fraktal.
Reguła 30 z jednej komórki tworzy chaos tak nieprzewidywalny, że jej środkowa kolumna służyła jako generator liczb losowych. Reguła 110 jest Turing-zupełna — udowodnił to Matthew Cook (praca opublikowana w 2004 r.). Reguła 184 to model ruchu ulicznego: jedynki to samochody jadące w prawo, gdy pole przed nimi jest wolne; ich liczba się nie zmienia.
Mrówka Langtona (1986)
Chris Langton wymyślił „mrówkę” na kratce. Na pustym polu skręca o 90° w prawo, na zapełnionym — w lewo; zmienia stan pola i robi krok naprzód. Przez pierwsze ok. 10 000 kroków rysuje chaotyczną plamę, a potem nagle zaczyna budować autostradę: powtarza ten sam ciąg 104 kroków, który przesuwa ją o 2 pola po przekątnej — bez końca.
Nikt nie udowodnił, że autostrada pojawia się przy każdym początkowym układzie pól — to wciąż otwarty problem. Wiadomo tylko, że mrówka nigdy nie zostaje na zawsze w ograniczonym obszarze (twierdzenie Bunimowicza i Troubetzkoya).
Uproszczenia: plansze są skończone i sklejone brzegami w torus (384 × 384 komórki w grze w życie, 320 × 320 dla mrówki), a wiersz automatu 1D jest pierścieniem. Prawdziwe automaty żyją na nieskończonej płaszczyźnie — u nas szybowiec, który wyleci za krawędź, wraca z drugiej strony i może trafić w to, co zostawił za sobą. Liczby w opisach wzorów (np. 1103 pokolenia R-pentomina) dotyczą nieskończonej płaszczyzny.