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.
Document type :
Conference papers
Liste complète des métadonnées

Cited literature [6 references]  Display  Hide  Download

https://hal.inria.fr/hal-01656362
Contributor : Hal Ifip <>
Submitted on : Tuesday, December 5, 2017 - 3:42:45 PM
Last modification on : Tuesday, December 5, 2017 - 3:55:38 PM

File

 Restricted access
To satisfy the distribution rights of the publisher, the document is embargoed until : 2020-01-01

Please log in to resquest access to the document

Licence


Distributed under a Creative Commons Attribution 4.0 International License

Identifiers

Citation

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⟩

Share

Metrics

Record views

80