Computability and Non-computability Issues in Amorphous Computing

Abstract : Amorphous computing systems consist of a huge set of tiny simple stationary or mobile processors whose computational, communication and sensory part is reduced to an absolute minimum. In an airborne medium the processors communicate via a short-range radio while in a waterborne medium via molecular communication. In some cases the computational part of the processors can be simplified down to finite state automata or even combinatorial circuits and the system as a whole can still possess universal computational power with a high probability. We will argue that the amorphous systems belong among the simplest (non-uniform) universal computational devices. On the other hand, it is questionable as to what extent the standard universal models of computation can faithfully capture the behavior of amorphous computing systems whose functionality also depends on the non-computational and/or unpredictable operations of certain parts of the entire system.
Document type :
Conference papers
Liste complète des métadonnées

Cited literature [18 references]  Display  Hide  Download

https://hal.inria.fr/hal-01556229
Contributor : Hal Ifip <>
Submitted on : Tuesday, July 4, 2017 - 5:45:49 PM
Last modification on : Monday, April 23, 2018 - 9:58:11 AM
Document(s) archivé(s) le : Friday, December 15, 2017 - 2:33:18 AM

File

978-3-642-33475-7_1_Chapter.pd...
Files produced by the author(s)

Licence


Distributed under a Creative Commons Attribution 4.0 International License

Identifiers

Citation

Jiří Wiedermann. Computability and Non-computability Issues in Amorphous Computing. 7th International Conference on Theoretical Computer Science (TCS), Sep 2012, Amsterdam, Netherlands. pp.1-9, ⟨10.1007/978-3-642-33475-7_1⟩. ⟨hal-01556229⟩

Share

Metrics

Record views

79

Files downloads

38