Game of Life

Gra w życie, znana również po prostu jako Życie, to automat komórkowy opracowany przez brytyjskiego matematyka Johna Hortona Conwaya w 1970 roku.

Gra jest grą typu zero-player, co oznacza, że jej ewolucja zależy od stanu początkowego i nie wymaga dalszych działań. Z Grą w Życie wchodzi się w interakcję, tworząc początkową konfigurację i obserwując jej ewolucję, lub, w przypadku zaawansowanych graczy, tworząc wzory o określonych właściwościach.

Zasady

Wszechświat Gry w Życie to nieskończona, dwuwymiarowa ortogonalna siatka kwadratowych komórek, z których każda znajduje się w jednym z dwóch możliwych stanów, żywy lub martwy (lub odpowiednio zaludniony i niezamieszkany). Każda komórka wchodzi w interakcję z ośmioma sąsiadami, którymi są komórki sąsiadujące ze sobą poziomo, pionowo lub po przekątnej. Na każdym etapie występują następujące przejścia:

1. Każda żywa komórka z mniej niż dwoma żywymi sąsiadami umiera, jakby przez niedostateczną populację.
2. Każda żywa komórka z dwoma lub trzema żywymi sąsiadami żyje w następnym pokoleniu.
3. Każda żywa komórka z więcej niż trzema żywymi sąsiadami umiera, jakby przez przeludnienie.
4. Każda martwa komórka z dokładnie trzema żywymi sąsiadami staje się żywą komórką, jakby przez reprodukcję.

Początkowy wzór stanowi zalążek systemu. Pierwszą generację tworzy się, stosując powyższe zasady jednocześnie do każdej komórki w nasieniu; narodziny i zgony następują jednocześnie, a dyskretny moment, w którym to następuje, jest czasami nazywany tyknięciem. Każde pokolenie jest czystą funkcją poprzedniego. Zasady są nadal stosowane wielokrotnie, aby stworzyć kolejne pokolenia.


Pod koniec 1940 roku John von Neumann zdefiniował życie jako kreację (jako istotę lub organizm), która może się rozmnażać i symulować maszynę Turinga. Von Neumann myślał o rozwiązaniu inżynieryjnym, które wykorzystywałoby elementy elektromagnetyczne unoszące się losowo w cieczy lub gazie. Okazało się to nierealne przy dostępnej wówczas technologii. Stanisław Ulam wynalazł automaty komórkowe, które miały symulować teoretyczne konstrukcje elektromagnetyczne von Neumanna. Ulam omówił wykorzystanie komputerów do symulacji swoich automatów komórkowych w dwuwymiarowej siatce w kilku artykułach. Równolegle Von Neumann próbował skonstruować automat komórkowy Ulama. Chociaż odniósł sukces, był zajęty innymi projektami i pozostawił pewne szczegóły niedokończone. Jego konstrukcja była skomplikowana, ponieważ próbowała symulować jego własny projekt inżynieryjny.

Motywowany pytaniami z logiki matematycznej, a częściowo pracą nad grami symulacyjnymi m.in. Ulama, John Conway zaczął przeprowadzać eksperymenty w 1968 r. z różnymi regułami automatu komórkowego 2D. Początkowym celem Conwaya było zdefiniowanie interesującego i nieprzewidywalnego automatu komórkowego. Dlatego chciał, aby niektóre konfiguracje przetrwały przez długi czas przed śmiercią, inne konfiguracje trwały wiecznie bez cykli itp. Było to znaczące wyzwanie i otwarty problem przez lata, zanim eksperci od automatów komórkowych zdołali udowodnić, że rzeczywiście Conway's Game of Life przyznał się do konfiguracji, która była żywa w sensie spełniania dwóch ogólnych wymagań Von Neumanna. Podczas gdy definicje sprzed Conway's Life były zorientowane na dowód, konstrukcja Conwaya miała na celu prostotę bez apriorycznego dostarczania dowodu, że automat żyje.

Conway starannie wybrał swoje zasady, po wielu eksperymentach, aby spełnić następujące kryteria:

1. Nie powinno być gwałtownego wzrostu.
2. Powinny istnieć małe początkowe wzorce z chaotycznymi, nieprzewidywalnymi wynikami.
3. Powinien istnieć potencjał uniwersalnych konstruktorów von Neumanna.
4. Zasady powinny być tak proste, jak to możliwe, przy jednoczesnym przestrzeganiu powyższych ograniczeń.

Wiele wzorów w Grze w Życie ostatecznie staje się kombinacją martwych natur, oscylatorów i statków kosmicznych; inne wzory można nazwać chaotycznymi. Wzór może pozostać chaotyczny przez bardzo długi czas, aż w końcu ustali się w takiej kombinacji.