Turing-Completeness of Asynchronous Non-camouflage Cellular Automata

Abstract : Asynchronous Boolean totalistic cellular automata have recently attracted attention as promising models for the implementation of reaction-diffusion systems. It is unknown, however, to what extent they are able to conduct computation. In this paper, we introduce the so-called non-camouflage property, which means that a cell’s update is insensitive to neighboring states that equal its own state. This property is stronger than the Boolean totalistic property, which signifies the existence of states in a cell’s neighborhood, but is not concerned with how many cells are in those states. We argue that the non-camouflage property is extremely useful for the implementation of reaction-diffusion systems, and we construct an asynchronous cellular automaton with this property that is Turing-complete. This indicates the feasibility of computation by reaction-diffusion systems.
Type de document :
Communication dans un congrès
Alberto Dennunzio; Enrico Formenti; Luca Manzoni; Antonio E. Porreca. 23th International Workshop on Cellular Automata and Discrete Complex Systems (AUTOMATA), Jun 2017, Milan, Italy. Springer International Publishing, Lecture Notes in Computer Science, LNCS-10248, pp.187-199, 2017, Cellular Automata and Discrete Complex Systems. 〈10.1007/978-3-319-58631-1_15〉
Liste complète des métadonnées

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

https://hal.inria.fr/hal-01656362
Contributeur : Hal Ifip <>
Soumis le : mardi 5 décembre 2017 - 15:42:45
Dernière modification le : mardi 5 décembre 2017 - 15:55:38

Fichier

 Accès restreint
Fichier visible le : 2020-01-01

Connectez-vous pour demander l'accès au fichier

Licence


Distributed under a Creative Commons Paternité 4.0 International License

Identifiants

Citation

Tatsuya Yamashita, Teijiro Isokawa, Ferdinand Peper, Ibuki Kawamata, Masami Hagiya. Turing-Completeness of Asynchronous Non-camouflage Cellular Automata. Alberto Dennunzio; Enrico Formenti; Luca Manzoni; Antonio E. Porreca. 23th International Workshop on Cellular Automata and Discrete Complex Systems (AUTOMATA), Jun 2017, Milan, Italy. Springer International Publishing, Lecture Notes in Computer Science, LNCS-10248, pp.187-199, 2017, Cellular Automata and Discrete Complex Systems. 〈10.1007/978-3-319-58631-1_15〉. 〈hal-01656362〉

Partager

Métriques

Consultations de la notice

27