Počet záznamů: 1

On the Universal Computing Power of Amorphous Computing Systems

  1. 1.
    0311251 - UIVT-O 2010 RIV US eng J - Článek v odborném periodiku
    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
    Grant CEP: GA AV ČR 1ET100300517; GA ČR GD201/05/H014
    Výzkumný záměr: CEZ:AV0Z10300504
    Klíčová slova: amorphous computing systems * universal computing * random access machine * simulation
    Kód oboru RIV: IN - Informatika
    Impakt faktor: 0.726, rok: 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í.
    Trvalý link: http://hdl.handle.net/11104/0162917