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.
Type de document :
Communication dans un congrès
Jos C. M. Baeten; Tom Ball; Frank S. Boer. 7th International Conference on Theoretical Computer Science (TCS), Sep 2012, Amsterdam, Netherlands. Springer, Lecture Notes in Computer Science, LNCS-7604, pp.1-9, 2012, Theoretical Computer Science. 〈10.1007/978-3-642-33475-7_1〉
Liste complète des métadonnées

Littérature citée [18 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01556229
Contributeur : Hal Ifip <>
Soumis le : mardi 4 juillet 2017 - 17:45:49
Dernière modification le : lundi 23 avril 2018 - 09:58:11
Document(s) archivé(s) le : vendredi 15 décembre 2017 - 02:33:18

Fichier

978-3-642-33475-7_1_Chapter.pd...
Fichiers produits par l'(les) auteur(s)

Licence


Distributed under a Creative Commons Paternité 4.0 International License

Identifiants

Citation

Jiří Wiedermann. Computability and Non-computability Issues in Amorphous Computing. Jos C. M. Baeten; Tom Ball; Frank S. Boer. 7th International Conference on Theoretical Computer Science (TCS), Sep 2012, Amsterdam, Netherlands. Springer, Lecture Notes in Computer Science, LNCS-7604, pp.1-9, 2012, Theoretical Computer Science. 〈10.1007/978-3-642-33475-7_1〉. 〈hal-01556229〉

Partager

Métriques

Consultations de la notice

73

Téléchargements de fichiers

20