Skip to Main content Skip to Navigation
Conference papers

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
Complete list of metadata

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 : Monday, May 17, 2021 - 12:00:04 PM

File

447449_1_En_15_Chapter.pdf
Files produced by the author(s)

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

184

Files downloads

179