Przeczytaj
Zasady Gry w życie
Na samym początku przypomnijmy przedstawione w czasie poprzedniej lekcji reguły ewolucji komórki w Grze w życie. Komórka przyjmuje jeden z dwóch stanów: może być żywa lub martwa. Jej stan w następnym cyklu automatu jest podyktowany następującymi zasadami:
martwa komórka, która ma dokładnie trzech żywych sąsiadów, staje się żywa;
żywa komórka, która ma dwóch lub trzech żywych sąsiadów, pozostaje nadal żywa;
żywa komórka umiera, jeśli ma mniej niż dwóch albo więcej niż trzech żywych sąsiadów.
Dlaczego stosowany jest taki właśnie zestaw zasad? Otóż Conway tworząc Grę w życie chciał zasymulować życie jednostki w pewnego rodzaju społeczeństwie. Pierwsza zasada symbolizuje narodziny nowego osobnika, ze względu na obecność pozostałych w sąsiedztwie. Druga jest odzwierciedleniem zaistnienia idealnych warunków życiowych dla komórki, co pozwala jej przeżyć.
Ostatnia reguła ma za to dwa warianty. Jeżeli żywa komórka ma mniej niż dwóch żywych sąsiadów, to umiera z samotności. Natomiast jeżeli ma ich więcej niż trzech, umiera wskutek przeludnienia. Automat komórkowy Conwaya pomimo swojej prostoty w pewien sposób odzwierciedla życie organizmów w pewnej gromadzie.
Rodzaje obiektów
Gra w życie ma niewielki zestaw prostych reguł, po zastosowaniu których generowane są skomplikowane kształty i obiekty. Mogą one na siebie wzajemnie wpływać, tworząc w efekcie złożone mechanizmy.
Struktury niezmienne
Pierwszym rodzajem obiektów są struktury niezmienne. Są to układy komórek, które zgodnie z zasadami gry nie zmieniają kształtu w kolejnych cyklach ewolucji. Do grupy tej należą obiekty takie jak klocek, ul, łódka, statek czy bochenek.
Oscylatory
Film dostępny pod adresem /preview/resource/RA5IvhDb6GvdN
Film nawiązujący do treści materiału
Oscylatory są wzorami okresowymi. Oznacza to, że przyjmują cyklicznie kilka postaci następujących jedna po drugiej. Istnieje wiele oscylatorów o różnych okresach.
Tak naprawdę większość liczb naturalnych może być długościami okresu oscylatora. Wyjątkiem są liczby 19, 23, 38 oraz 41. Oscylatory o okresach takiej długości nie zostały jeszcze odnalezione. Tworzenie oscylatorów jest dosyć trudne i wymaga dużej wyobraźni.
Statki
Film dostępny pod adresem /preview/resource/RXTg1rKJ8eF6v
Film nawiązujący do treści materiału
Statki, podobnie jak oscylatory, są układami okresowymi. Po kilku generacjach wracają do swojej początkowej formy, ale w innym miejscu niż to, w którym zaczęły ewoluować. Mają one zdolność poruszania się po planszy.
Istnieją różne rodzaje statków. Różnią się one wielkością oraz szybkością poruszania się po planszy. Prędkość statku jest bardzo często wyrażana jako iloraz liczby komórek, które zmieniły pozycję i długości cyklu. Przykładowo, statek który w trakcie okresu trwającego pięć cykli przesunie się o dwie komórki w lewo, ma prędkość
Najszybsze statki w tradycyjnym wydaniu Gry w życie nie przekraczają prędkości .
Puffer
Film dostępny pod adresem /preview/resource/RqOo3ZAVgOGT2
Film nawiązujący do treści materiału
Specjalnym rodzajem statku są tak zwane puffery, które w trakcie przemieszczania się po planszy zostawiają za sobą pewien ślad. Często ślad ten jest wykorzystywany przez inne obiekty, albo po prostu przez nie usuwany.
Breeder
Film dostępny pod adresem /preview/resource/RFwR96Usjvrje
Film nawiązujący do treści materiału
Kolejnym rodzajem statków są breedery, które swoim zachowaniem przypominają puffery. Także pozostawiają one za sobą struktury, lecz tym razem są one o wiele bardziej skomplikowane. Breedery potrafią zostawiać za sobą inne statki albo działa. Kluczowym warunkiem określającym czy statek jest breederem, jest kwadratowy przyrost jego komórek w czasie ewolucji.
Działa
Film dostępny pod adresem /preview/resource/RP3xDVdiKOIWe
Film nawiązujący do treści materiału
Działo jest stacjonarnym wzorem tworzącym nowe statki. Najczęściej spotykane działa produkują najprostsze statki w pojedynczym nurcie. Istnieją jednak rodzaje zdolne do równoległej produkcji wielu obiektów.
Istnieją wzory, które nie mogą powstać w wyniku żadnego procesu ewolucji, a więc tym samym mogą pojawić się wyłącznie jako populacja początkowa. Są one znane jako Eden (z ang. Garden of Eden).
Logika i kompletność Turingakompletność Turinga
Okazuje się, że możemy wykorzystać obiekty takie jak statki i działa do budowy działających bramek logicznych. Ciąg statków może reprezentować strumień bitów. Przykładowo, obecność statku w strumieniu może reprezentować 1, natomiast jego brak 0. W ten sposób możemy skonstruować bardzo prymitywny, ale działający komputer, który jest w stanie wykonywać dowolne obliczenia.
Rzeczą, która potwierdza uniwersalność Gry w życie, jest możliwość zbudowania w niej maszyny Turingamaszyny Turinga. Wynika to z faktu, że jest ona w stanie wykonać dowolne obliczenia.
Słownik
cecha maszyny lub języka programowania polegająca na tym, że może on rozwiązać taką samą klasę problemów jak maszyna Turinga
matematyczny model abstrakcyjnej maszyny, która jest w stanie symulować dowolny algorytm