Turing-Completeness of Asynchronous Non-camouflage Cellular Automata - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Communication Dans Un Congrès Année : 2017

Turing-Completeness of Asynchronous Non-camouflage Cellular Automata

Résumé

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.
Fichier principal
Vignette du fichier
447449_1_En_15_Chapter.pdf (716.87 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-01656362 , version 1 (05-12-2017)

Licence

Paternité

Identifiants

Citer

Tatsuya Yamashita, Teijiro Isokawa, Ferdinand Peper, Ibuki Kawamata, Masami Hagiya. Turing-Completeness of Asynchronous Non-camouflage Cellular Automata. 23th International Workshop on Cellular Automata and Discrete Complex Systems (AUTOMATA), Jun 2017, Milan, Italy. pp.187-199, ⟨10.1007/978-3-319-58631-1_15⟩. ⟨hal-01656362⟩
95 Consultations
110 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More