| Abstrakt: | Definujeme nový výpočtový model nepravidelných asynchrónnych bunkových
automatov a skúmame ich výpočtovú silu. Nepravidelný asynchrónny bunkový
automat je graf, ktorý má v každom vrchole konečne stavový automat, ktorý vidí
svoj stav a stavy svojich susedov. Všetky vrcholy sú riadené rovnakým
"programom", ktorý nazveme prechodová schéma. V každom kroku výpočtu urobia
prechod niektoré vrcholy. Požaduje sa, aby výsledok výpočtu celého automatu (za
predpokladu, že ten automat je dostatočne veľký) bol nezávislý od výberu
počítajúcich vrcholov (za predpokladu, že ten výber je spravodlivý) a ich grafu prepojení
(za predpokladu, že ten graf je súvislý).
Dokážeme, že nepravidelné asynchrónne bunkové automaty majú rovnakú výpočtovú
silu ako Turingove stroje.
|
|---|