O automatach komórkowych | Gra w życie, Reguła 30, Reguła 110 i więcej

Cztery podstawowe części

Każdy automat komórkowy składa się z tych samych czterech części. Siatka to przestrzeń, w której żyją komórki. Może to być jednowymiarowa linia, dwuwymiarowa płaszczyzna jak szachownica, a nawet trójwymiarowa przestrzeń. Stany określają, czym może być komórka. W najprostszym przypadku komórka jest binarna: czarna albo biała, 1 albo 0. Sąsiedztwo to zbiór komórek, które bezpośrednio wpływają na daną komórkę. Na siatce kwadratowej jest to zwykle sąsiedztwo Moore'a, czyli wszystkie osiem otaczających komórek, albo sąsiedztwo von Neumanna, czyli tylko północ, wschód, południe i zachód. Reguły to mózg automatu: logika, która wyznacza każdej komórce jej nowy stan. Na przykład: jeśli żyję, ale mam mniej niż dwóch żywych sąsiadów, umieram z samotności. Każda komórka stosuje te same reguły w tej samej chwili.

1. Gra w życie Conwaya

Reguły: B3/S23. Żywa komórka przeżywa, gdy ma 2 lub 3 żywych sąsiadów. Martwa komórka ożywa, gdy ma ich dokładnie 3. Każda inna komórka jest martwa w następnym pokoleniu. John Conway zaprojektował ją w 1970 roku, a sławę przyniosła jej rubryka Martina Gardnera w Scientific American. Powstają w niej szybowce, oscylatory i statki kosmiczne. Bill Gosper znalazł w tym samym roku pierwsze działo szybowców: wzór, który co 30 pokoleń wystrzeliwuje nowy szybowiec, bez końca. Gra w życie potrafi wykonywać obliczenia, bo szybowce mogą przenosić sygnały i zderzać się jak bramki logiczne. Przede wszystkim pokazuje, jak złożone zachowanie wyrasta z prostych reguł.

Działo Gospera w Grze w życie wystrzeliwujące ukośny strumień szybowców — Działo Gospera po 330 pokoleniach. Wyrenderowano w PictorX.

2. Reguła 30

Typ: jednowymiarowy elementarny automat komórkowy. Następny stan każdej komórki zależy od niej samej i jej dwóch sąsiadów, a każde pokolenie jest rysowane jako nowy wiersz pod poprzednim. Stephen Wolfram przedstawił Regułę 30 w 1983 roku. Zacznij od jednej czarnej komórki, a wyrośnie z niej chaotyczny trójkąt. Wynik wygląda na losowy mimo deterministycznej reguły, tak losowy, że jego środkowa kolumna była używana jako generator liczb pseudolosowych. Takie same trójkąty pojawiają się w pigmencie muszli ślimaka morskiego Conus textile.

Trójkąt Reguły 30 wyrosły z jednej czarnej komórki, chaotyczny po prawej i prążkowany po lewej — Reguła 30 z jednej czarnej komórki, 224 pokolenia. Wyrenderowano w PictorX.

3. Reguła 110

Typ: jednowymiarowy elementarny automat komórkowy, tak jak Reguła 30, ale z inną tabelą ośmiu odpowiedzi. Udowodniono, że Reguła 110 jest obliczeniowo uniwersalna: Matthew Cook pokazał, że przy odpowiednim pierwszym wierszu może ona emulować każde obliczenie, które wykona komputer ogólnego przeznaczenia. Występują w niej ruchome struktury, które przemieszczają się po powtarzającym się tle i oddziałują na siebie, gdy się spotkają. To właśnie te zderzenia dowód wykorzystuje jako logikę. Reguła 110 pokazuje, jak bardzo proste reguły mogą emulować dowolne obliczenia.

Reguła 110 wyrosła z jednej komórki po prawej, rozchodząca się w lewo w zagnieżdżonych trójkątach — Reguła 110 z jednej czarnej komórki przy prawej krawędzi. Wyrenderowano w PictorX.

4. Brian's Brain

Stany: wyłączona, włączona (pobudzona) i w refrakcji. Reguły: wyłączona komórka włącza się, jeśli dokładnie 2 sąsiednie komórki są włączone. Włączona komórka przechodzi w stan refrakcji. Komórka w refrakcji się wyłącza. Zaprojektował go Brian Silverman. Ponieważ po pobudzeniu komórka musi odpocząć przez jedno pokolenie, każdy impuls stale oddala się od miejsca, w którym już był. W efekcie powstaje tłum samobieżnych wzorów, który przypomina fale w ośrodkach pobudliwych, takich jak tkanka nerwowa czy mięsień sercowy, i często wygląda żywo i organicznie.

Brian's Brain rozprzestrzeniający się z losowej plamy, pobudzone komórki na żółto i zanikające ślady na fioletowo — Brian's Brain 70 pokoleń po losowej plamie, z zanikającymi śladami. Wyrenderowano w PictorX.

5. Wireworld

Stany: pusta, głowa elektronu, ogon elektronu i przewodnik. Reguły: głowa staje się ogonem, ogon staje się przewodnikiem, a przewodnik staje się głową, gdy dokładnie 1 lub 2 jego sąsiednie komórki są głowami. Puste komórki pozostają puste. Wireworld również zaprojektował Brian Silverman, w 1987 roku. Komórki przewodnika to przewody, a głowa, za którą podąża ogon, to elektron biegnący wzdłuż nich. Można w nim symulować układy elektroniczne: pętla przewodu z jednym elektronem to zegar, małe wcięcie to dioda, a kilka komórek tworzy bramkę logiczną. Zbudowano w nim całe komputery, na przykład komputer Wireworld Davida Moore'a i Marka Owena, który oblicza liczby pierwsze.

Układ w Wireworld z dwiema pętlami zegarowymi, dwiema diodami i bramką XOR, elektrony na niebiesko i czerwono na żółtym przewodzie — Dwa zegary, dwie diody i bramka XOR w Wireworld. Wyrenderowano w PictorX.

256 reguł i cztery klasy Wolframa

Jednowymiarowa komórka z dwoma sąsiadami widzi jeden z ośmiu wzorów, od 111 do 000. Reguła podaje nowy stan dla każdego z nich, więc ma osiem bitów, a reguł elementarnych jest 2⁸ = 256. Odczytaj osiem odpowiedzi jako liczbę binarną, a otrzymasz nazwę reguły: Reguła 30 to 00011110, a Reguła 110 to 01101110. Stephen Wolfram uporządkował reguły według tego, co robią, od porządku do chaosu. 1. Klasa 1 dochodzi do jednolitego stanu. 2. Klasa 2 dochodzi do stabilnych lub powtarzających się struktur. 3. Klasa 3 pozostaje chaotyczna i wygląda na losową, jak Reguła 30. 4. Klasa 4 buduje struktury, które poruszają się i oddziałują na siebie na granicy porządku i chaosu, jak Reguła 110.

Ranking trudności

Gra w życie ★☆☆☆☆ · Reguła 30 ★☆☆☆☆ · Brian's Brain ★★☆☆☆ · Wireworld ★★★★☆ · Reguła 110 ★★★★★. Dwa pierwsze tłumaczą się same, gdy się im przyglądasz. Reguła 110 ukrywa swoje ruchome struktury w powtarzającym się tle.

Najpiękniejsze wizualnie

1. Brian's Brain · 2. Gra w życie Conwaya · 3. Reguła 30 · 4. Reguła 110 · 5. Wireworld.

Najważniejsze matematycznie

1. Reguła 110, ze względu na uniwersalność · 2. Gra w życie, ze względu na uniwersalność i emergencję · 3. Reguła 30, ze względu na chaos i losowość · 4. Wireworld, ze względu na logikę cyfrową · 5. Brian's Brain, ze względu na układy pobudliwe.

W przyrodzie, fizyce i kryptografii

Automaty komórkowe służą do symulowania złożonych układów w przyrodzie, fizyce i kryptografii. Pomysł sięga Stanisława Ulama i Johna von Neumanna, którzy w latach 1940–1949 użyli siatki komórek, by zaprojektować maszynę zdolną do kopiowania samej siebie. W realnym świecie automaty komórkowe widać w pigmencie niektórych muszli, na przykład muszli Conus textile, której trójkąty przypominają Regułę 30, oraz w łuskach jaszczurki perłowej, które przełączają się między zielenią a czernią według reguły bliskiej automatowi komórkowemu. Fizycy używają ich do modelowania przepływu gazu, stosów piasku i pożarów lasów. Pozorna losowość Reguły 30 sprawiła, że stała się kandydatką na generatory liczb losowych i szyfry strumieniowe.

Odkryj je w PictorX

Otwórz Automaty komórkowe, aby uruchomić wszystkie pięć. Obejrzyj działo szybowców, flotę statków kosmicznych albo R-pentomino, które potrzebuje 1103 pokoleń, by się ustabilizować. Wpisz dowolną regułę typu Life, na przykład B36/S23, albo dowolny numer reguły elementarnej od 0 do 255. Rysuj i wymazuj komórki, wysyłaj elektrony przez układy Wireworld, zawijaj krawędzie i przełącz na tryb kolorowy. Zapisz PNG lub otwórz płótno w edytorze PictorX.

Często zadawane pytania

Czym jest automat komórkowy?

Siatka komórek, w której każda komórka ma stan. W każdym takcie wszystkie komórki aktualizują się razem według jednej stałej reguły, która patrzy tylko na komórkę i jej sąsiadów. Mimo prostych reguł wzory mogą być złożone i nieprzewidywalne.

Kto wymyślił automaty komórkowe?

Stanisław Ulam i John von Neumann w latach 1940–1949 w Los Alamos. Gra w życie Johna Conwaya (1970) spopularyzowała ten pomysł, a Stephen Wolfram badał 256 reguł elementarnych w latach 1980–1989.

Które automaty komórkowe są zupełne w sensie Turinga?

Spośród pięciu automatów z tej strony udowodniono uniwersalność Reguły 110 i Gry w życie, a Wireworld może pomieścić cały komputer. Uniwersalność oznacza, że przy odpowiednim wzorze startowym mogą one wykonać każde obliczenie, które wykona komputer ogólnego przeznaczenia.

Czym są cztery klasy Wolframa?

Klasa 1 wygasa do jednolitego stanu, klasa 2 dochodzi do stabilnych lub powtarzających się struktur, klasa 3 pozostaje chaotyczna jak Reguła 30, a klasa 4 buduje ruchome, oddziałujące ze sobą struktury jak Reguła 110.

Dlaczego Reguła 30 wygląda na losową?

Każdy krok jest ustalony, ale każda komórka miesza swojego lewego sąsiada z dwiema pozostałymi komórkami w sposób, który szybko rozprzestrzenia małe różnice. W środkowej kolumnie nie znaleziono żadnego prostego wzoru, dlatego używano jej do generowania liczb losowych.