Automaty komórkowe i Reguła 110

Automaty komórkowe są bardzo ciekawym działem matematyki. Wnioski wyciągnięte z ich badania można zastosować do praktycznie wszystkich działów nauki: chemii, biologii, fizyki a nawet astronomii.

Najprostszym przykładem automatu komórkowego jest jednowymiarowy automat. Wyobraźmy sobie nieskończoną taśmę podzieloną na komórki. Każda komórka może być czarna lub biała. Można tym kolorom przypisać liczby: białe – 0, czarne – 1. Zatem całkiem biała taśma wygląda tak:

...00000000000000000...

Całkiem czarna tak:

...11111111111111111...

Możliwe są też różnorodne wzory. Co druga komórka biała (jednowymiarowa szachownica):

...01010101010101010101...

Dodajmy teraz możliwość przekształcania komórek. Załóżmy, że stan komórki będzie zależał od jej koloru oraz od koloru jej sąsiadów. Dla przykładu, reguła:

010 => 0

oznacza, że jeśli komórka jest czarna (środkowa jedynka) a po bokach ma komórki białe to sama też staje się biała.

Reguła:

110 => 0

oznacza, że czarna komórka zmienia kolor gdy jej lewy sąsiad jest czarny a prawy biały.

Ponieważ istnieje osiem różnych kombinacji trzech cyfr 0 i 1 to podając osiem takich reguł można określić kompletną metodę przekształcania każdej z komórek.

poprzedni wzór 111 110 101 100 011 010 001 000
wynik           0   0   1   1   0   0   1   1

Powyższa reguła zamienia wszystkie białe komórki w taśmie na czarne i na odwrót. Jak widać nie są brane pod uwagę kolory sąsiadów.

Jeśli popatrzymy na cyfry 0 i 1 w wyniku to można je potraktować jako liczbę binarną. Ośmiocyfrowa liczba binarna oznacza, że jest 256 różnych reguł opisujących transformację taśmy. Można też użyć tych liczb do oznaczania reguł. Podana powyżej miałaby numer 51 (kolejne cyfry mnożone przez potęgi dwójki czyli 0*128+0*64+1*32+1*16+0*8+0*4+1*2+1*1=51).

Możemy zatem dokładnie opisać następny stan komórki biorąc pod uwagę kolor jej oraz jej sąsiadów. Zastosujmy teraz tą regułę do wszystkich komórek (nieskończonej) taśmy. Otrzymamy drugą taśmę – zwaną drugą generacją. Proces ten można powtarzać w nieskończoność. Taśma ma tylko jeden wymiar ale jeśli narysujemy kolejne generacje jedna pod drugą to pokryją one płaszczyznę tworząc dwuwymiarowe wzory. Poniżej znajduje się wzór generowany przez regułę 30 z taśmy początkowej zawierającej pojedynczą czarną komórkę:

Reguła 30

Rysunek ten pokazuje dwa znaczące fakty:

  • oprócz numeru reguły istotny jest również stan początkowy, od którego zaczynamy generować kolejne taśmy
  • nawet proste stany początkowe mogą prowadzić do bardzo skomplikowanych wzorów, nawet wyglądających na losowe

Mimo, że istnieje 256 różnych reguł to niektóre z nich można traktować jak bliźniaki. Jeśli ciąg cyfr 0 i 1 opisujący regułę odwrócimy to wzory przez nią generowane również się odwrócą ale ich kształt i zachowanie pozostanie bez zmian. Podobnie jeśli zamienimy zera na jedynki a jedynki na zera. Kształt i zachowanie generowanych wzorów będzie bez zmian – zmieni się tylko ich kolor na przeciwny. Oczywiście oba przekształcenia można połączyć: odwrócić kolejność cyfr i zamienić kolory. Ponownie: nie wpłynie to na zachowanie reguły.

Podsumowując, istnieje tylko 88 istotnie różnych reguł, co trochę ułatwia ich klasyfikację. Dokonał jej Stephan Wolfram dzieląc reguły na cztery klasy:

  • Klasa 1. Reguły szybko prowadzące do taśmy jednolitego koloru (całej czarnej lub całej białej). Przykładem reguły 0, 32, 160 i 250.
  • Klasa 2. Reguły prowadzące do stanu stałego lub oscylującego. Stan stały oznacza, że wzór nie zmienia się z pokolenia na pokolenie a oscylujący oznacza, że co określoną liczbę pokoleń stan powtarza się. Przykładem reguły 4, 108, 218 i 232
  • Klasa 3. Reguły pozostające w stanie losowym. Przykładem reguły 22, 30, 126, 150, 182
  • Klasa 4. Reguły tworzące fragmenty losowe lub oscylujące ale także formy przenikające się lub wchodzące w zależności. Przykładem reguła 110

Najciekawsza jest klasa 4. Szczególnie reguła 110. Udowodniono bowiem, że za jej pomocą można przeprowadzać obliczenia. Co więcej można na jej podstawie zbudować system będący kompletny w sensie Turinga. Co oznacza kompletność Turinga? Alan Turing badał języki programowania. Starał się uprościć je pozostawiając jednakże możliwość tworzenia dowolnych programów i algorytmów. Stworzył maszynę Turniga (abstrakcyjną, bardzo prostą maszynę pozwalającą na jej programowanie przy użyciu nieskończonej taśmy) i dowiódł, że jest ona w stanie wykonać dowolnie skomplikowany algorytm (jest kompletna w sensie Turinga). Jeśli zatem uda się przy pomocy języka programowania zasymulować działanie maszyny Turinga to tym samym dowiedzie się, że tenże język jest kompletny w sensie Turinga.

Reguła 110 w połączeniu ze specjalnie dobranym stanem początkowym jest w stanie zasymulować maszynę Turinga. Mimo swej prostoty jest równoważna językom programowania używanym do pisania aplikacji. Można – odpowiednio kolorując taśmę – rozwiązać za jej pomocą dowolny problem, dla którego znamy algorytm. Oczywiście nie będzie to praktyczne rozwiązanie. Nawet tak proste zadanie jak dodanie dwóch liczb będzie wymagało bardzo wielu symboli na taśmie oraz setek tysięcy generacji. Jednak z punktu widzenia matematyki nie ma to znaczenia.

Odkrycie kompletności reguły 110 ma istotne implikacje. Oznacza to, że nawet tak wydawałoby się prymitywne mechanizmy mogą tworzyć bardzo skomplikowane struktury. Nie da się ich opisać prostą matematyczną formułą – trzeba zasymulować wszystkie pokolenia aby poznać wynik.

Analogiczne cechy wykazuje dwuwymiarowa wersja automatu komórkowego zwana grą w życie. Również za jej pomocą można zbudować maszynę Turinga. Ale to już opowieść na inną okazję.

Dodaj komentarz

Twój adres email nie zostanie opublikowany. Pola, których wypełnienie jest wymagane, są oznaczone symbolem *


*