Rok Małpy (komórkowej)

Człowiek urodzony w roku Małpy posiada ponadprzeciętną inteligencję. Pierwsza notka w roku 2016 jest też nieprzeciętna. Te automaty komórkowe to nie wiadomo co to jest. Ani matematyka, ani fizyka, ani informatyka. Po co się w ogóle tym zajmować? A jednak ludzie się tym zajmują. Widać jest taka potrzeba. Jedni dlatego, że widzą tu możliwość budowania nowych modeli dla zjawisk fizycznych, biologicznych, społecznych. Inni, bo to może przydać się w wojsku. Jeszcze inni, bo to po prostu piękne. To nowe pole do badań złożoności. Badając automaty komórkowe, przydzielając im specjalną działkę na polu badań, lepiej poznajemy tajniki układów złożonych, gdzie całość to coś więcej niż tylko suma części.

Mnie osobiście te automaty ciekawiły od samego początku, gdy się tylko pojawiły. Dziś do nich powróciłem po tym, jak DEDA przypomniał mi, że Gerard 't Hooft, fizyk teoretyk, Nobel 1999, poważnie niezadowolony z mechaniki kwantowej, zaproponował mechanizm automatu komórkowego dla wyjaśnienia kuriozalnych zachowań kwantowych kotów. Wierzy mianowicie, że ich irracjonalne zachowanie może być wyjaśnione deterministycznie – przez odpowiedni automat komórkowy.

Oczywiście trzeba by jeszcze wtedy wyjaśnić kto ten automat zbudował, zaprogramował, kto uruchomił zegar i jak ten zegar taki kolosalny automat taktuje. Ale to już byłoby przyczepianie się. Póki co cieszmy się! Albo i nie. Nie wiem.

Mechanika kwantowa jest liniowa. Dobrze to i źle. Zająłem się automatem liniowym, Rule 90, bo prosty, symetryczny, liniowy. W pierwszym dniu nowego roku idę z nim dalej. Na tapecie jest odwracalność.

I tu musimy wybrać: czy interesuje nas automat skończony czy nieskończony? A jak skończony, to z jakimi warunkami brzegowymi?

Na początek weźmy skończony. Na początek warunki nałóżmy periodyczne. Dla warunków periodycznych reguła 90 kodowana jest w takiej oto macierzy:

Bjab i Tichy, w dyskusji pod poprzednimi notkami, zdaje się na to wpadli gdy zaczęli rozmawiać o rogach, diabłach i jednorożcach. Warunki periodyczne faktycznie dodają 1 w prawym górnym i w lewym dolnym rogu.

Automat skończony, periodyczny jest nieodwracalny. Stan samych jedynek przechodzi w 0. Tak samo dla nieskończonego. Oczywiście czasami krok wstecz można wykonać, czasami jest on nawet jednoznaczny. Można to zobaczyć na diagramie transformacji stanów. Oto te diagramy dla periodycznego automatu 90 dla kilku różnych rozmiarów:

n=3

n=4

n=5

n=6

n=7

n=8

A co z zerowymi warunkami brzegowymi? Dla zerowych warunków brzegowych macierz automatu jest prostsza – nie ma jedynek w rogach, są zera.

Taka macierz ma swoją nazwę: tridiagonal matrix. Wikipedia daje formułę na wyznacznik dla macierzy

W naszym przypadku współczynniki a_n są zerami. Współczynniki b_n=c_n=1. Dla n=1 wyznacznik jest 0, dla n=2 wyznacznik jest -1. Stąd dla dowolnego n nieparzystego wyznacznik jest zero. Dla n parzystego jest -1 lub +1. Więc wniosek: dla n parzystych reguła 90 jest odwracalna, dla n nieparzystych jest nieodwracalna.

Dla n nieparzystych możemy nawet w sposób jawny podać niezerowy stan, który przechodzi w stan zerowy. Ten stan to na przemian 1 i 0, przy czym jedynka jest w lewej skrajnej i prawej skrajnej komórce. Taki stan, z zerowymi warunkami brzegowymi, przechodzi w stan zerowy, bowiem 0+0=1+1=0 mod 2.

I tak oto załatwiliśmy sobie dowód twierdzenia 3.1 z pracy prof. Martina del Rey

http://inmabb.criba.edu.ar/revuma/pdf/v56n1/v56n1a06.pdf

Pracowity pierwszy dzień nowego roku.