5-State Rotation-Symmetric Number-Conserving Cellular Automata are not Strongly Universal - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier
Conference Papers Year : 2015

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

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.

Dates and versions

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

Identifiers

Cite

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⟩
144 View
0 Download

Altmetric

Share

More