Prírodou inšpirované algoritmy

Hexagonálny reverzibilný segmentovaný CA

Hexagonálny reverzibilný segmentovaný CA

Hexagonálny segmentovaný celulárny automat (hexagonal partitioned cellular automata – HPCA) je model biliardového automatu, ktorého bunka je rozdelená (segmentovaná) na 6 častí. Každý segment má 2 stavy, čiže celkovo má tento automat 64 stavov. Formálne je definovaný nasledujúcim zápisom:

HPCA je reverzibilný celulárny automat, ktorý je symetrický podľa osi otáčania. Jeho lokálna prechodová funkcia je definovaná na nasledujúcom obrázku. Každé pravidlo má svoje rotácie, v poradí je ich počet rotácií nasledujúci: 1+6+6+6+3+6+2+6+6+6+6+3+6+1. Potom je celkový počet stavov 64.

Môžeme si ľahko overiť, že HPCA je reverzibilný a symetrický podľa osi otáčania. Aby bol HPCA logicky a výpočtovo univerzálny stačí ukázať, že sa v ňom dá realizovať šírenie signálu, smerovanie, oneskorenie signálu a Fredkinove hradlo.

Šírenie signálu a smerovanie

Signál hodnoty 1 je zobrazený ako čierna bodka. Tento signál sa šíri priamo v celulárnom priestore podľa pravidla (2) (pokiaľ nemá v ceste prekážku) tak ako je to na nasledujúcom obrázku. Signál 0 je reprezentovaný prázdnym políčkom. Z tohto dôvodu budeme počítať aj s časovou synchronizáciou.

Signál 1 môže zmeniť smer doprava alebo doľava o 120 stupňov použitím špeciálnej štruktúry, ktorú nazývame blok. Na ďalšom obrázku máme odraz doprava. Blok je štruktúra, ktorá pozostáva zo šiestich bodiek, ktoré sú pevne zoskupené podľa pravidla (3). Ak samotný bod dosiahne blok, tak ako je na obrázku odrazí sa podľa pravidla (9). Odraz doľava je realizovaný podobne použitím pravidla (8). V HPCA obrat o 60 stupňov nie je možný, preto sa signál môže šíriť len do troch smerov a nie do šiestich. Pre dosiahnutie ľubovolného bodu na ploche je to však postačujúce.

Oneskorovací člen

Je realizovaný kombináciou blokov ako na ďalšom obrázku. Pri tejto metóde je možné viacnásobne použiť časové oneskorenie troch časových jednotiek.

S-hradlo a inverzné S-hradlo

S-hradlo môže byť simulované jednou bunkou HPCA. Na nasledujúcom obrázku (a) je vstupno-výstupný vzťah, ktorý si môžeme ľahko overiť. Napríklad ak sú na vstupe kanály c a x a obidva nesú signál 1, potom obidva výstupné kanály c a cx dávajú hodnotu 1 podľa pravidla (4). Inverzné S-hradlo je tiež realizované jednou bunkou ako na nasledujúcom obrázku (b).

F-hradlo

F-hradlo realizované v celulárnom priestore HPCA je náležité spojenie dvoch S-hradiel a dvoch inverzných S-hradiel. Aby boli signály na hradlách synchronizované musíme použiť niekoľko oneskorovacích členov. Nasledujúci obrázok zachytáva konfiguráciu F-hradla. Veľkosť konfigurácie je 28x17 a oneskorenie hradla je 58 časových jednotiek.