Jednowymiarowy automat opisany ośmioma odpowiedziami 0/1 potrafi wykonywać dowolne obliczenia
Rule 110 jest jednym z najprostszych automatów komórkowych: komórki stoją w jednym szeregu, każda ma tylko stan 0 lub 1, a nowy stan zależy od niej samej i dwóch sąsiadów. Ponieważ istnieje tylko osiem możliwych trójek bitów, całą lokalną regułę można zapisać ośmioma odpowiedziami 0/1. Matthew Cook udowodnił jednak, że Rule 110 jest obliczeniowo uniwersalny. Odpowiednio przygotowany wzór początkowy może emulować dowolny algorytm. Ogromna moc obliczeniowa nie wymaga więc ogromnego zestawu instrukcji.
Cała fizyka świata mieści się w ośmiu przypadkach
Komórka patrzy na trzy bity: lewego sąsiada, siebie i prawego sąsiada. Możliwe są wyłącznie układy 000, 001, 010, 011, 100, 101, 110 i 111. Dla każdego reguła mówi, czy środkowa komórka w następnym kroku będzie 0 czy 1. Osiem odpowiedzi tworzy kompletny opis systemu. Numer 110 pochodzi z binarnego zapisu wyników tej tabeli.
Z prostego startu powstają ruchome lokalne struktury
Ewolucja Rule 110 nie jest ani całkowicie regularna, ani jednolicie chaotyczna. W tle pojawiają się powtarzalne wzory, po których przemieszczają się lokalne zaburzenia przypominające cząstki. Mogą zderzać się, zmieniać i tworzyć nowe struktury. Właśnie takie „glidery” i ich interakcje stały się kluczem do zakodowania obliczeń.
Cook zamienił zderzenia wzorców w elementy programu
W pracy z 2004 roku Matthew Cook przedstawił dowód uniwersalności Rule 110. Zamiast budować klasyczne tranzystory, wykorzystał naturalne struktury pojawiające się w automacie do symulacji prostszych systemów obliczeniowych, w tym cyklicznych systemów tagowych. Jeśli Rule 110 potrafi symulować system już znany jako uniwersalny, sam również jest uniwersalny.
Uniwersalność oznacza możliwość wykonania dowolnego algorytmu
Cook wyjaśnia, że system uniwersalny może uruchomić dowolny program po odpowiednim zakodowaniu danych wejściowych i odczytaniu wyniku. Nie chodzi więc o to, że Rule 110 „rozwiązuje dużo zadań” w potocznym sensie. Chodzi o równoważność mocy obliczeniowej z maszyną Turinga — fundamentalnym abstrakcyjnym modelem komputera.
Prostota reguły nie przekłada się na prostotę zachowania
Można znać tabelę ośmiu przypadków na pamięć i nadal nie być w stanie przewidzieć złożonej ewolucji dużej konfiguracji bez wykonywania obliczeń. Informacja o regule jest bardzo skompresowana, ale informacja rozwijana przez wiele kroków może być ogromna. To jedna z najbardziej sugestywnych demonstracji, że długość opisu praw lokalnych nie ogranicza w oczywisty sposób bogactwa zjawisk globalnych.
Uniwersalność niesie ze sobą także nierozstrzygalność
Sam artykuł Cooka zauważa, że z uniwersalności wynikają formalnie nierozstrzygalne pytania o zachowanie Rule 110, na przykład dotyczące wystąpienia odpowiednio zakodowanych sekwencji czy długoterminowej periodyczności w ogólności. Gdy prosty automat staje się pełnoprawnym komputerem, dziedziczy nie tylko jego możliwości, ale również fundamentalne ograniczenia teorii obliczeń.
Reguła jest krótka, ale program może być zakodowany w bardzo dużym stanie początkowym
Uniwersalność Rule 110 nie oznacza, że kilka losowych komórek natychmiast zachowuje się jak komputer ogólnego przeznaczenia. Aby zasymulować wybrany program, trzeba przygotować odpowiednio skonstruowaną konfigurację, w której rozmieszczenie struktur niesie dane i sterowanie. To ważne, bo złożoność może znajdować się w dwóch miejscach: w prawie ewolucji i w stanie początkowym. Rule 110 pokazuje skrajny przypadek, w którym prawo jest niemal minimalne, a mimo to potrafi interpretować bardzo bogato zakodowane warunki początkowe. Prostota reguły nie eliminuje złożoności danych.