Number of the records: 1
On the Universal Computing Power of Amorphous Computing Systems
- 1.
SYSNO ASEP 0311251 Document Type J - Journal Article R&D Document Type Journal Article Subsidiary J Článek ve WOS Title On the Universal Computing Power of Amorphous Computing Systems Title Univerzální výpočetní síla amorfních výpočetních systémů Author(s) Wiedermann, Jiří (UIVT-O) RID, SAI, ORCID
Petrů, L. (CZ)Source Title Theory of Computing Systems. - : Springer - ISSN 1432-4350
Roč. 45, č. 4 (2009), s. 995-1010Number of pages 16 s. Language eng - English Country US - United States Keywords amorphous computing systems ; universal computing ; random access machine ; simulation Subject RIV IN - Informatics, Computer Science R&D Projects 1ET100300517 GA AV ČR - Academy of Sciences of the Czech Republic (AV ČR) GD201/05/H014 GA ČR - Czech Science Foundation (CSF) CEZ AV0Z10300504 - UIVT-O (2005-2011) UT WOS 000268585400019 EID SCOPUS 70349500521 DOI 10.1007/s00224-009-9178-6 Annotation 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. Workplace Institute of Computer Science Contact Tereza Šírová, sirova@cs.cas.cz, Tel.: 266 053 800 Year of Publishing 2010
Number of the records: 1