← Laboratorium Matematyka · automaty komórkowe

Eksperyment · Życie

Gra w życieprosty kod, złożony świat

Kratka, dwa stany i jedna reguła liczenia sąsiadów. Z tego rodzą się oscylatory, statki kosmiczne, działa — a nawet komputery. Rysuj komórki, stawiaj słynne wzory, zmieniaj reguły i patrz, jak z prostoty wyłania się złożoność.

Pokolenie0
Populacja0
RegułaB3/S23

Rysuj: przeciągnij · Przesuwaj: prawy przycisk, Shift lub dwa palce · Zoom: kółko lub szczypnięcie

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łę:

st+1 = 1, gdy st = 0 i N = 3 — narodziny (B3) 1, gdy st = 1 i N ∈ {2, 3} — przetrwanie (S23) 0 w pozostałych przypadkach — samotność lub tłok

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ą.

sit+1 = bit nr (4·si−1 + 2·si + si+1) liczby reguły,   np. 30 = 000111102

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.

φt+1 = φt + 90° (pole puste)  lub  φt − 90° (pole zapełnione)

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.

Czy wiesz, że…?

  • John Conway (1937–2020) wymyślił grę w życie w 1970 r., a świat poznał ją dzięki rubryce „Mathematical Games” Martina Gardnera w październikowym numerze Scientific American z 1970 r.
  • Conway wyznaczył 50 dolarów nagrody za wzór, który rośnie bez końca. Jeszcze w 1970 r. zgarnął ją zespół Billa Gospera z MIT — działem, które masz w bibliotece wzorów.
  • Ponieważ gra w życie jest Turing-zupełna, można w niej zbudować… grę w życie. Metapiksel OTCA (Brice Due, 2006) to blok 2048 × 2048 komórek udający jedną komórkę; z takich bloków składa się „gra w grze”, która działa 35 328 razy wolniej.

Wyzwania

  1. Zbuduj oscylator o okresie 2Wyczyść planszę (C) i narysuj własnoręcznie wzór, który co 2 pokolenia wraca do tego samego kształtu. Reguła B3/S23.nie zaliczone
  2. Wystrzel szybowiec z działa GosperaPostaw działo z biblioteki i uruchom symulację, aż wyleci pierwszy szybowiec.nie zaliczone
  3. Matuzalem: z najwyżej 10 komórek przez 1000 pokoleńZacznij od 1–10 żywych komórek (B3/S23). Po 1000 pokoleniach wzór ma wciąż żyć i się zmieniać — sam blok się nie liczy.nie zaliczone
  4. Doczekaj się autostrady mrówkiW trybie 3 przetrwaj chaos, aż mrówka zacznie budować prostą, powtarzalną „autostradę”.nie zaliczone