Obsah
Úvod
Fredkinove hradlo
Model biliardového automatu
Margolusov biliárdový CA
Trojuholníkové reverzibilné segmentované celulárne automaty
16 stavové reverzibilné segmentované celulárne automaty
Hexagonálny reverzibilný segmentovaný CA
Energia v biliardových automatoch
Entrópia v reverzibilných CA
Príklady RPCA - videá
Applety
Literatúra a linky
O tejto kapitole



Ostatné kapitoly
Výpočtové schopnosti celulárnych automatov
Celulárne automaty - úvod
Samoreprodukujúce sa celulárne automaty
Kryštálove výpocty
HAL
Boidi
Floyi
Aplikácie celulárnych automatov
CAPOW
LIFE - Hra života
Fredkinov biliardový automat


Hlavne menu
 O nás
 Tutoriály
 Archiv


Ú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.

Hore
Kontakty:     webmaster     admin     chief
Valid HTML 4.01! Valid CSS!