Skip to Main content Skip to Navigation
Conference papers

5-State Rotation-Symmetric Number-Conserving Cellular Automata are not Strongly Universal

Katsunobu Imai 1 Hisamichi Ishizaka 1 Victor Poupet 2
2 ESCAPE - Systèmes complexes, automates et pavages
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : We study two-dimensional rotation-symmetric number- conserving cellular automata working on the von Neumann neighborhood (RNCA). It is known that such automata with 4 states or less are trivial, so we investigate the possible rules with 5 states. We give a full characterization of these automata and show that they cannot be strongly Turing universal. However, we give example of constructions that allow to embed some boolean circuit elements in a 5-states RNCA.
Document type :
Conference papers
Complete list of metadatas

https://hal-lirmm.ccsd.cnrs.fr/lirmm-01476796
Contributor : Victor Poupet <>
Submitted on : Saturday, February 25, 2017 - 7:39:45 PM
Last modification on : Thursday, June 6, 2019 - 3:40:20 PM

Links full text

Identifiers

Collections

Citation

Katsunobu Imai, Hisamichi Ishizaka, Victor Poupet. 5-State Rotation-Symmetric Number-Conserving Cellular Automata are not Strongly Universal. AUTOMATA, Jul 2014, Himeji, Japan. pp.31-43, ⟨10.1007/978-3-319-18812-6_3⟩. ⟨lirmm-01476796⟩

Share

Metrics

Record views

207