W automacie komórkowym mogą istnieć stany, które mają przyszłość, ale nie mają żadnej możliwej przeszłości
Automat komórkowy jest zwykle definiowany jako reguła przechodzenia z jednej konfiguracji do następnej. Naturalnie można więc zapytać odwrotnie: jakie konfiguracje mogły wystąpić krok wcześniej? Okazuje się, że niektóre automaty mają tzw. Garden of Eden — konfiguracje, które są poprawnymi stanami planszy, ale nie są wynikiem działania reguły na żadnym wcześniejszym stanie. Mogą istnieć wyłącznie jako warunek początkowy. Deterministyczny świat może więc zawierać obrazy dopuszczalne „teraz”, lecz niemożliwe do wytworzenia przez własną historię.
Reguła do przodu nie musi mieć odwrotności
Deterministyczność mówi, że każdy stan ma jednoznaczną następną konfigurację. Nie mówi, że każda konfiguracja ma poprzednika ani że poprzednik jest jedyny. Dwie różne plansze mogą przejść do tej samej planszy, a pewne plansze mogą nie mieć żadnego preobrazu. Automat może więc tracić informację podczas ewolucji.
Garden of Eden to konfiguracja bez rodzica
Nazwa pochodzi z metafory stanu „stworzonego na początku”, a nie narodzonego z wcześniejszej ewolucji. Jeżeli konfiguracja C nie jest wynikiem zastosowania globalnej reguły do żadnej konfiguracji B, to C jest Garden of Eden. Możemy ręcznie ustawić ją jako stan początkowy, a automat będzie od niej dalej ewoluował, ale cofnięcie czasu o jeden krok jest niemożliwe.
Moore i Myhill połączyli ten pomysł z własnościami globalnymi
Stanford Encyclopedia przypomina twierdzenia Garden-of-Eden z początku lat 60., które podają warunki związane z istnieniem takich stanów w automatach komórkowych. Wynik jest ważny, bo łączy lokalną regułę aktualizacji z globalnym pytaniem o to, czy pewne konfiguracje w ogóle mają historię.
Brak przeszłości jest inny niż niemożliwy stan
Garden of Eden nie jest błędnym układem komórek. Każda komórka ma legalny stan, a po uruchomieniu automat normalnie policzy jego przyszłość. Niemożliwa jest jedynie sytuacja, w której konfiguracja pojawia się po co najmniej jednym kroku ewolucji. To subtelna różnica między „stan nie należy do przestrzeni możliwości” a „stan należy do przestrzeni, lecz nie leży w obrazie reguły”.
Zjawisko pokazuje strzałkę informacji
Jeśli wiele stanów może prowadzić do jednego wyniku, a niektóre wyniki nie mają poprzedników, aktualizacja nie zachowuje pełnej informacji o przeszłości. Patrząc na aktualną planszę, nie zawsze można odtworzyć wcześniejszą. To matematyczny model nieodwracalności: reguła jest całkowicie deterministyczna w przyszłość, ale niekoniecznie wstecz.
Proste lokalne prawo narzuca globalne ograniczenia historii
Najbardziej zaskakujące jest to, że każda komórka wykonuje tylko lokalną instrukcję dotyczącą sąsiadów, a mimo to powstaje globalny zakaz: pewne całe nieskończone konfiguracje nie mogą być rezultatem żadnej wcześniejszej konfiguracji. To kolejny przykład emergencji własności, której nie widać po przeczytaniu pojedynczej lokalnej reguły.
Odwracalny automat nie może mieć Garden of Eden
Jeżeli globalna reguła automatu jest bijekcją — każdy stan ma dokładnie jednego poprzednika i jednego następcę — konfiguracje bez przeszłości nie mogą istnieć. Garden of Eden jest więc sygnałem utraty odwracalności. Ta obserwacja łączy pozornie zabawną nazwę z ważnym pytaniem o zachowanie informacji. W automatach projektowanych jako modele odwracalnych procesów fizycznych szczególną uwagę poświęca się właśnie temu, by aktualizacja nie usuwała informacji o stanie poprzednim. W zwykłych automatach lokalna reguła często skleja wiele możliwych przeszłości w jedną przyszłość, co otwiera drogę do stanów pozbawionych jakiegokolwiek preobrazu.