5-State Rotation-Symmetric Number-Conserving Cellular Automata are not Strongly Universal - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier
Communication Dans Un Congrès Année : 2015

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

Résumé

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.

Dates et versions

lirmm-01476796 , version 1 (25-02-2017)

Identifiants

Citer

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⟩
155 Consultations
0 Téléchargements

Altmetric

Partager

More