Prírodou inšpirované algoritmy

Entrópia v reverzibilných CA

Entrópia v reverzibilných CA

Ak vyplníme bunky v celulárnom automate náhodne vybranými binárnymi hodnotami a potom tieto hodnoty rozvinieme použitím nejakých pravidiel (pravidiel života), uvidíme komplex úbytku a pretekania (prebytok) štruktúry a aktivity celého systému. Tieto vznikajúce a zanikajúce štruktúry nazývame klzáky. Objavujúce sa tu a tam pohybujúc sa okolo skupín núl, a potom sa ťahajú späť ku komplexu "vriaceho kotla" aktivity alebo znovu vzklíči do komplikovaného vzájomného pôsobenia v oblasti, ktorá má ustálený základ v periodicky oscilujúcej štruktúre.

Ak namiesto pravidiel života použijeme invertujúci časový rozvoj, nájdeme automat stále bez zmeny, t.j. v náhodnom stave tak ako bol na začiatku. Toto vyplýva z jednoduchého čítacieho argumentu, pretože vcelku vyzerá konfigurácia náhodne (ak počiatočné konfigurácie s veľmi malou náhodnosťou môžu byť zobrazené s daným počtom invertujúcich krokov do malej jednoducho vyzerajúcej konfigurácie, potom je celkové zobrazenie bijektívne).

To však neznamená, že reverzibilné CA sú menej dôležité ako nereverzibilné celulárne automaty. Spúšťanie RCA z náhodného stavu je ako spúšťanie termodynamického systému v stave maximálnej entrópie - je neprístupné brať jednoduchší prípad, pretože náhodnosť nemôže narastať a nemôže sa brať viac komplikovaný stav, pretože jeho náhodnosť je už maximálna a tak by sa vlastne z hľadiska entrópie nič nedialo.

Ak budeme spúšťať rekurzívny CA z nenáhodného stavu (malé štruktúry budú v pozadí núl) potom z toho môžeme dostať zaujímavý časový rozvoj. Ak si vyberieme pravidlo a počiatočný stav tak, že povoľuje šírenie informácie, potom má rekurzívny CA sklon k tomu, že jeho stav je čím ďalej viac komplikovanejší. To znamená, ak každý stav automatu sa nám javí ako správa s obsahom buniek, ktoré sú vlastne znaky správy a sú použité iba vzťažné lokálne vrstvy, potom stupeň informácie postupne narastá. Samozrejme v skutočnosti automat iba opakovane šifruje svoj stav a tak ak všetky vzájomné vzťahy sú brané do výpočtu potom sa stupeň informácie nemení.

Čo sa stane ak automat začne zavádzať redundanciu do správy a použije viac buniek na zakódovanie rovnakej informácie? Informácia, ktorá bola počiatočne inicializovaná sa rozšíri ako vzťah medzi stavom viacerých buniek a stane sa veľmi zložitou pre lokálny invertujúci rozvoj na vloženie redundantnej časti. Použitie analógie invertujúcej zobrazenie môže zmeniť dve kópie jedného dokumentu do jednej kópie a niekoľko hárkov čistého papiera. Dve oddelené invertujúce zobrazenia pracujú každý na jednej kópii a tak nemôžeme dokázať tento záver.

Z pohľadu bytostí "žijúcich" vo vnútri reverzibilného celulárneho automatu a z pohľadu neschopnosti použitia komplikovaných vzťahov medzi veľkými počtami buniek to znamená, že pre všetky praktické účely entrópia automatu narastá.