Prírodou inšpirované algoritmy

16 stavové reverzibilné segmentované celulárne automaty

16 stavové reverzibilné segmentované celulárne automaty

Poznáme dva modely týchto 16 stavových automatov. Na oboch modeloch je možné simulovať biliardové automaty. Tieto automaty majú bunky rozdelené na 4 segmenty. Segmenty sú dvojhodnotové, čiže celkový počet stavov je v tomto prípade 16.

Model 1

Je to rekurzívny segmentovaný celulárny automat symetrický podľa osi otáčania a aj zrkadlovo symetrický. Na nasledujúcom obrázku je uvedených 16 pravidiel lokálnej prechodovej funkcie. Tento model vyhovuje podmienkam konzervatívnosti, izotropie a symetrickosti.

Zostrojíme funkciu F-hradla v tomto modeli. Tak ako je to v biliardovom modeli, tak aj tu signál pozostáva z dvoch častí (nasledujúci obrázok) a šíri sa priamo pokiaľ nemá v ceste nejakú prekážku.

Pevný blok je štvorec pozostávajúci zo šiestich tmavých častí, ktoré zostávajú nemenné (viď. nasledujúci obrázok).

Dva pevné bloky vedľa seba hrajú úlohu zrkadla, ktoré odráža signál tak ako je na ďalšom obrázku.

Netriviálne prekríženie je na nasledujúcom obrázku.

I-hradlo je realizované zrážkou dvoch signálov a odrazu v pravom uhle ako je to zobrazené na ďalšom obrázku.

Konfiguráciu F-hradla máme na nasledujúcom obrázku, kde S-hradlo(obrázok pod ním), inverzné S-hradlo a zrkadlá sú náležite pospájané. Časové oneskorenie medzi vstupom a výstupom v tejto konfigurácii má 164 krokov.

Značenie a význam signálov zodpovedá príslušným funkciám popísaných v statiach Fredkinovo hradlo a Model biliardového automatu.
Tento model je tiež implementovaný v applete vrátane príkladov okrem F-hradla. Ako typ automatu vyberte 16 stavový CA. .

Model 2

Prechodová funkcia tohto modelu je na nasledujúcom obrázku. Tento model je konzervatívny, izotropný, a reverzibilný, ale nie je symetrický. Signál, pevný blok a I-hradlo sú také isté ako v predchádzajúcom modeli. Až na pevný blok, pri ktorom sa to láme, ak signál prichádza z pravej strany.

Avšak ak signál prichádza zľava funguje to ako zrkadlo (ľavá časť nesledujúceho obrázku). Potom je zrejmé, že obrat doľava je realizovaný iba jedným blokom a obrat doprava musí byť tvorený troma obratmi doľava. V pravej časti toho istého obrázka je konfigurácia S-hradla a na poslednom obrázku je znázornené F-hradlo. Časové oneskorenie v tomto prípade je 174 krokov.

Odkaz na pdf dokument o podrobnejšom popise 16 stavových segmentovaných RCA je v podkapitole literatúra.