%0 Conference Proceedings
%T Turing-Completeness of Asynchronous Non-camouflage Cellular Automata
%+ University of Electro-Communications [Tokyo] (UEC)
%+ University of Hyogo
%+ Osaka University [Osaka]
%+ Tohoku University [Sendai]
%+ The University of Tokyo (UTokyo)
%A Yamashita, Tatsuya
%A Isokawa, Teijiro
%A Peper, Ferdinand
%A Kawamata, Ibuki
%A Hagiya, Masami
%Z Part 2: Regular Papers
%< avec comité de lecture
%( Lecture Notes in Computer Science
%B 23th International Workshop on Cellular Automata and Discrete Complex Systems (AUTOMATA)
%C Milan, Italy
%Y Alberto Dennunzio
%Y Enrico Formenti
%Y Luca Manzoni
%Y Antonio E. Porreca
%I Springer International Publishing
%3 Cellular Automata and Discrete Complex Systems
%V LNCS-10248
%P 187-199
%8 2017-06-07
%D 2017
%R 10.1007/978-3-319-58631-1_15
%Z Computer Science [cs]Conference papers
%X 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.
%G English
%Z TC 1
%Z WG 1.5
%2 https://inria.hal.science/hal-01656362/document
%2 https://inria.hal.science/hal-01656362/file/447449_1_En_15_Chapter.pdf
%L hal-01656362
%U https://inria.hal.science/hal-01656362
%~ IFIP-LNCS
%~ IFIP
%~ IFIP-TC
%~ IFIP-TC1
%~ IFIP-WG1-5
%~ IFIP-AUTOMATA
%~ IFIP-LNCS-10248