Prírodou inšpirované algoritmy

Úvod

Úvod

Celulárny automat (CA) je systém pozostávajúci z nekonečného počtu konečných automatov (bunky), ktoré sú usporiadané vedľa seba. Použitím lokálnych prechodových funkcií určujeme stav bunky v nasledujúcom časovom kroku. Stav bunky v nasledujúcom kroku sa určí podľa stavu okolitých (susedných) buniek v súčastnom časovom kroku. To ako sa zmení stav určujú prechodové funkcie (pravidlá). Všetky bunky menia alebo nemenia svoj stav (podľa funkcií) paralelne (súčastne) v každom časovom kroku.

CA sa nazýva reverzibilný ak každá konfigurácia (globálny stav buniek) má najviac jedného predchodcu. Preto v reverzibilných CA môžeme nájsť iba jediný spätný pohyb.

Výpočtová univerzalita RCA

Hoci RCA majú veľmi veľké obmedzenia, ich výpočtová univerzalita je dokázateľná. Toffoli dokázal, že každý k rozmerný nereverzibilný CA môže byť simulovaný na k+1 rozmernom reverzibilnom CA, preto dvojrozmerný RCA je výpočtovo univerzálny. Keď budeme na Turingov stroj pozerať ako na jednorozmerný automat potom je zrejmé, že dvojrozmerný RCA ho môže simulovať.

Norman Margolus navrhol dvojrozmerný dvojstavový model reverzibilného celulárneho automatu a ukázal jeho univerzalitu. Ukázal, že biliardový model (BBM) môže byť vložený do jeho reverzibilného celulárneho priestoru. BBM je taký výpočtový model, ktorého logické operácie sú realizované elastickými zrážkami gúľ. Na druhej strane Fredkin dokázal, že Fredkinove hradlo môže byť realizované biliardovým modelom. Fredkinove hradlo má 3 vstupy, 3 výstupy; je to reverzibilný bit zachovávajúci logický element. Je univerzálny tým, že každý logický obvod môže byť zostrojený použitím Fredkinovho hradla. Z toho vyplýva aj univerzalita Margolusovho modelu.