Prírodou inšpirované algoritmy

Fyzika a Reverzibilný Celulárny Automat - RCA

Z pohľadu fyziky je model celulárneho automatu plne diskrétny systém. Priestor je diskrétny, čas je diskrétny a taktiež je ohraničená množina stavov v ktorom sa môže ľubovoľná bunka nachádzať.

Najzákladnejšia z vlastností, ktorú CA modelujú je vlastnosť lokálnosti fyzikálnych zákonov: Stav bunky na danej pozícií závisí iba od predchádzajúcich stavov okolitých buniek. Pri fyzikálnych dejoch je známe, že sa tiež odohrávajú v lokálnej interakcií. Objekty, agenti ktoré sú bližšie k sebe sa ovplyvňujú viac ako tie, ktoré sú vzdialenejšie.

Ďalšou z dôležitých vlastnosti fyzikálnych dejov je reverzibilita. Mikrofyzika sa ukazuje ako plne reverzibilná. Vlastnosť reverzibility spôsobuje fakt, že informácia v uzavretom systéme nemôže vzniknúť a nemôže sa ani vytratiť, čo korešponduje s druhým termodynamickým zákonom fyziky. V prípade informácií hovoríme o zákone zachovania informácií. V tomto ponímaní informácia je práve tým, čo v prípade ak by bol čas reverzibilný - bežal dozadu presne po takej dráhe akou išiel dopredu by umožnilo reverzibilnosť systému. Všetky reverzibilné systémy sa riadia zákonom zachovania informácií.

(Fredkin, 1992) vysvetľuje vo svojej práci zákon zachovania informácií nasledovne. Predstavme si 3-D reverzibilný celulárny automat s definovanými pravidlami pre lokálne susedstvo siedmich buniek a to sever, juh, východ, západ, hore, dole a predchádzajúci stav aktuálnej bunky. Môžeme teda definovať funkciu F, ktorá pre každú možnú kombináciu okolitých buniek udáva nový stav aktuálnej bunky nasledovne:

Sx,y,z,t+1 = F(Sx-1,y,z,t, Sx+1,y,z,t, Sx,y-1,z,t, Sx,y-1,z,t, Sx,y,z-1,t, Sx,y,z+1,t, Sx,y,z,t-1)

kde premenná x označuje sever/juh; y označuje východ/západ; z označuje hore/dole a t označuje čas.

Na to aby bol systém reverzibilný musí existovať ďalšia funkcia G a to:

Sx,y,z,t-1 = G(Sx-1,y,z,t, Sx+1,y,z,t, Sx,y-1,z,t, Sx,y-1,z,t, Sx,y,z-1,t, Sx,y,z+1,t, Sx,y,z,t+1)

Ak funkcie F a G existujú potom takýto systém zachováva informácie a teda sa riadi zákonom zachovania informácií.

V klasickej fyzike si môžeme reverzibilnosť predstaviť založenú na tom, že žiaden dôsledok sa nemôže stratiť, pretože akokoľvek sa tento dôsledok zmenší stále bude existovať. Tento prístup ako popisuje (Fredkin, 1992) potom môže viesť i k takému pohľadu, že fakt, že o 5 rokov zasiahne Zem asteroid môže byt dôsledkom toho, že sa na mesiaci vplyvom gravitačnej sily zvalila skala dole kopcom pred dvoma miliardami rokov a jemne tak odchýlila obežné dráhy Zeme a asteroidov.

Vo výpočtových modeloch, ktoré nie sú reverzibilné dochádza k strate informácií počas vykonávania výpočtov. Ak chceme vytvoriť model ktorý bude odrážať termodynamický zákon potom sa informácia nemôže strácať ale môže zmeniť svoju formu tak ako vo fyzike sa nemôže strácať energia, tá môže iba zmeniť svoju formu. Táto forma môže v reálnom systéme predstavovať aj teplo. Ak sa veľké množstvo energie mení rýchlo na teplo, ktoré sa zo systému stráca, je známe, že na to aby proces mohol ďalej prebiehať bude potrebné do systému dodávať energiu ekvivalentnú tejto strate z vonka.

Pre dosiahnutie kvalitného modelu je teda vhodné použiť celulárny automat ktorý je reverzibilný, pretože ten spĺňa obe spomínané vlastnosti.