W Game of Life istnieją pytania o przyszłość, których żaden ogólny algorytm nie potrafi rozstrzygać
Game of Life jest deterministyczne: znając dokładny układ komórek, każdy kolejny krok jest jednoznaczny. Można więc oczekiwać, że przy wystarczająco dobrym programie zawsze da się przewidzieć, czy dana skończona konfiguracja kiedyś całkowicie zniknie. Tymczasem Jarkko Kari przytacza twierdzenie wynikające z uniwersalności Life: nie istnieje algorytm, który dla każdej skończonej konfiguracji zawsze poprawnie rozstrzygnie, czy kiedyś umrze. Problem zatrzymania komputera można zakodować w układzie komórek. Determinizm nie gwarantuje więc algorytmicznej przewidywalności.
Każdy pojedynczy krok jest banalnie obliczalny
Aby przejść z jednej generacji Life do następnej, wystarczy policzyć żywych sąsiadów każdej komórki i zastosować trzy proste przypadki narodzin, przeżycia lub śmierci. Nie ma żadnej losowości ani niejasności. Jeśli pokażemy dwóm komputerom tę samą planszę, oba wygenerują identyczną następną planszę.
Pytanie o nieskończenie daleką przyszłość jest innego rodzaju
Możemy bez problemu policzyć milion kolejnych kroków konkretnego wzoru. To jednak nie daje ogólnej procedury rozstrzygającej pytanie „czy ten wzór kiedykolwiek całkowicie zniknie?”. Jeśli po milionie kroków nadal istnieje, może zniknąć w milion pierwszym albo działać wiecznie. Sama symulacja nie ma uniwersalnego momentu, po którym zawsze wiadomo, że dalsze czekanie niczego nie zmieni.
Life potrafi zasymulować problem zatrzymania
Ponieważ Life jest obliczeniowo uniwersalne, można skonstruować konfigurację odpowiadającą dowolnej maszynie Turinga. Kari opisuje konstrukcję, w której skończona konfiguracja Life umiera wtedy i tylko wtedy, gdy zakodowana maszyna Turinga zatrzymuje się na pustej taśmie. Gdyby istniał algorytm rozstrzygający śmierć dowolnego wzoru Life, rozwiązywałby też problem zatrzymania.
Turing udowodnił, że takiego algorytmu być nie może
Problem zatrzymania jest nierozstrzygalny: nie istnieje jeden algorytm, który dla każdego programu i wejścia zawsze poprawnie odpowie, czy program się zatrzyma. Skoro pytanie o zatrzymanie można przełożyć na pytanie o śmierć wzoru Life, ogólny algorytm dla Life również nie może istnieć. To formalna granica obliczalności, nie tylko praktyczna trudność wynikająca z dużej planszy.
To jest inny rodzaj nieprzewidywalności niż chaos
W chaosie problemem jest wrażliwość na niedokładność warunków początkowych. W Game of Life możemy znać każdą komórkę dokładnie i nadal napotkać nierozstrzygalność pewnych pytań o dowolne konfiguracje. Niepewność nie pochodzi z błędu pomiarowego, lecz z tego, że system jest zdolny reprezentować dowolne obliczenie wraz z nierozstrzygalnymi problemami teorii obliczeń.
Krótka reguła potrafi więc stworzyć formalną granicę wiedzy algorytmicznej
To być może najbardziej ekstremalna wersja motywu „proste reguły, ogromna złożoność”. Zasady Life można wyjaśnić dziecku w minutę, ale nie istnieje uniwersalna metoda odpowiadająca na każde pytanie o ich długoterminowy wynik. Złożoność nie polega tylko na tym, że symulacja może trwać bardzo długo — w pewnych rodzinach pytań nie ma algorytmicznego skrótu gwarantującego odpowiedź dla wszystkich przypadków.
Nierozstrzygalność nie znaczy, że żadnego konkretnego wzoru nie da się przewidzieć
Wiele konfiguracji Life jest banalnych: blok pozostaje nieruchomy, blinker oscyluje, a mały wzór może zgasnąć po kilku krokach. Dla konkretnych przypadków często można udowodnić przyszłość dokładnie. Twierdzenie mówi coś innego: nie istnieje jedna procedura, która działa dla wszystkich możliwych skończonych konfiguracji i zawsze kończy się poprawną odpowiedzią. To różnica między „ten problem jest trudny” a „nie istnieje ogólny algorytm rozwiązujący całą klasę”. Nierozstrzygalność pojawia się dopiero wtedy, gdy dopuszczamy dowolnie skomplikowane wejścia zdolne zakodować dowolne obliczenie.