On the Universal Computing Power of Amorphous Computing Systems

0311251 - ÚI 2010 RIV US eng J - Journal Article
Wiedermann, Jiří - Petrů, L.
On the Universal Computing Power of Amorphous Computing Systems.
[Univerzální výpočetní síla amorfních výpočetních systémů.]
Theory of Computing Systems. Roč. 45, č. 4 (2009), s. 995-1010. ISSN 1432-4350. E-ISSN 1433-0490
R&D Projects: GA AV ČR 1ET100300517; GA ČR GD201/05/H014
Institutional research plan: CEZ:AV0Z10300504
Keywords : amorphous computing systems * universal computing * random access machine * simulation
Subject RIV: IN - Informatics, Computer Science
Impact factor: 0.726, year: 2009

Amorphous computing differs from the classical ideas about computations almost in every aspect. The architecture of amorphous computers is random, since they consist of a plethora of identical computational units spread randomly over a given area. Within a limited radius the units can communicate wirelessly with their neighbors via a single-channel radio. We consider a model whose assumptions on the underlying computing and communication abilities are among the weakest possible: all computational units are finite state probabilistic automata working asynchronously, there is no broadcasting collision detection mechanism and no network addresses. We show that under reasonable probabilistic assumptions such amorphous computing systems can possess universal computing power with a high probability.

Amorfní počítání se liší od klasických představ o výpočtech téměř ve všech ohledech. Architektura amorfních počítačů je náhodná, protože tyto se skládají z množství identických procesorů náhodně rozhozených v dané oblasti. Procesory mohou bezdrátově komunikovat pouze se svými blízkými použitím jedno-kanálového rádia. Budeme uvažovat model, jehož předpoklady jsou jedny z nejslabších možných: procesory jsou tvořeny asynchronními konečně-stavovými pravděpodobnostními automaty. Neexistují síťové adresy procesorů ani mechanismy pro detekci vysílacích kolizí. Ukážeme, že za rozumných pravděpodobnostních předpokladů amorfní výpočetní systémy mohou vládnout univerzální výpočetní silou s vysokou pravděpodobností.
Permanent Link: http://hdl.handle.net/11104/0162917