W komórce z artykułu 110

Artykuł 110 Kodeksu Cywilnego ewidentnie dotyczy złożoności obliczeń. Cytuję:

Art. 110

Jeżeli ustawa, orzeczenie sądu lub decyzja innego organu państwowego albo czynność prawna oznacza termin nie określając sposobu jego obliczania, stosuje się przepisy poniższe.

 

No, no..... Rzecz dotyczy złożoności obliczeniowej. W poprzedniej notce „Skandal w numerze 110”, wspomniałem inny artykuł, nie z kodeksu cywilnego a z gazety Science. Autorką była Melanie Mitchell. Pani prof. Melanie Mitchel ma na swoim koncie kilka książek, w tym jedną dedykowaną problemom złożoności obliczeniowej:

Pisze tam też, a jakże, o elementarnym automacie komórkowym Wolframa, tym z numerem 110. Tak na przykład pisze:

„... Reguła 110 jest przykładem bardzo prostego deterministycznego układu mogącego kreować nieprzewidywalne złożone zachowania.” Autorka niezupełnie podziela entuzjazm Wolframa, który wysuwa hipotezę iż Wszechświat jest w samej rzeczy automatem o bardzo bardzo bardzo prostej regule działania. Jak prostej? No, może cztery linijki kodu. A automat 110 jest najprostszym znanym automatem o tej własności, że wszystko co jest w ogóle obliczalne, może być obliczalne takim prostym automatem. Oczywiście tak prosty automat musi wykonać sporo kroków by cokolwiek obliczyć, niemniej, i to jest istotne, żadnego bardziej skomplikowanego komputera nie trzeba.

No, chyba, że, jak wierzy Penrose, życie i świadomość wymagają także procesów nieobliczalnych, ale mało kto się ze zdaniem Penrose'a liczy.

To rzekłszy, zajmijmy się bliżej artykułem/regułą 110. Do reguły 110 stosują się przepisy poniższe.

110 to dwójkowe 01101110. Co daje taką regułę przejść otoczeń

Wynika stąd w szczególności, że nasz automat startując z konfiguracji z jedną jedynką i pozostałymi zerami, po prawej stronie od jedynki będzie miała zawsze same zera. Jest wyraźnie asymetryczny. Spróbowałem zapisać formułę automatu jednym wzorem. Wyszło mi tak:

f(a,b,c) = b + c - bc – abc

Sprawdźmy:

f(1,1,1)=1+1-1-1=0, f(1,1,0)=1+0-0-0=1, f(1,0,1)=0+1-0-0=1, f(1,0,0)=0+0-0-0=0

f(0,1,1)=1+1-1-0=1, f(0,1,0)=1+0-0-0=1, f(0,0,1)=0+1-0-0=1, f(0,0,0)=0+0-0-0

Czyli wychodzi co trzeba, 110 dwójkowe zapisane ośmioma cyframi. Przypomnę, że na diagramach 1 to kwadracik czarny, 0 to kwadracik biały. Na razie nie widać nic specjalnie złożonego. Z formuły widać, że nasz automat jest mocno nieliniowy. Ma człon kwadratowy bc i człon trzeciego rzędu abc. Teraz co on takiego będzie robił z naszą jedną jedynką i wszystkimi zerami? Wolframa podobno natchnęła ta jego ewolucja do tego stopnia że stworzył Nowy Rodzaj Nauki (New Kind of Science, NKS). Nie tylko to. Jak wspominałem w poprzedniej notce napuścił nawet prawników na swojego asystenta by uniemożliwić mu przedwczesne opublikowanie własności automatu 110. Do dziś historia automatu 110 jest przedstawiana nieco inaczej w Wikipedii a nieco inaczej u samego Wolframa. Wikipedia twierdzi, że Wolfram dał ideę dowodu, a dowód przeprowadził Cook. Wolfram twierdzi, że udowodnił on, zaś Cook jedynie wygładził i załatał małe dziurki.

No dobrze, idąc śladami Wolframa, tymi w jego książce NKS, oto co nasz automat tworzy z jednej jedynki i reszty zer. Oto pierwsze 150 kroków:

A tu pierwsze 700 kroków

Przy lewym brzegu jakby nic ciekawego się więcej nie dzieje, jakiś wzorek okresowy. Po prawej też jakby się uspokoiło. Ale nie. Oto bowiem następne 700 kroków, już tylko w pobliżu prawego brzegu. Kroki 700-1400:

Jakoś coś tam się dalej dzieje. Nasz automat nie może się zdecydować co ma robić. Kaprysi. No to następne 700 kroków. Kroki 1400-2100:

I co on dalej z tym zrobi? Kroki 2100-2800:

Najwyraźniej zaczyna mu brakować wyobraźni. Kroki 2800-3500 zdają się świadczyć o tym, że wreszcie dał za wygraną:

Wpadł chyba wreszcie w cykl z którego już się nie wykaraska. A oto cała historia 3500 kroków z lotu ptaka.

Tyle nasz automat tworzy z jednej jedynki. A co będzie gdy zamiast jednej jedynki damy mu na wejściu co innego? Na wejściu możemy mu władować dane początkowe i kod programu. Wtedy on puści się w ruch i wyliczy co mu zostało dane do wyliczenia. Na tym polega jego uniwersalność. Tu istotna jest jego nieliniowość. Dla automatów liniowych wynik od sumy jest sumą wyników. Wiedzieć co automat robi dla jednej jedynki wystarczy. Bo więcej jedynek w rzędzie to suma rzędów jedno-jedynkowych. Dla automatu nieliniowego już tak dobrze nie ma. Grafiki jak wyżej, dla jednej jedynki na wejściu niewiele nam mówią o tym co będzie dla dwóch jedynek, położonych tak czy inaczej. A co dopiero trzech i więcej. Nasz automat jest zbyt złożony by był przewidywalny. I jest czymś bardziej złożonym niż automat niemal przypadkowy z regułą 90.