5-state rotation-symmetric number-conserving cellular automata are not strongly universal

DOI10.1007/978-3-319-18812-6_3MaRDI QIDQ5501611zbMATH OpenOpenAlexFDO

Authors Katsunobu Imai, Hisamichi Ishizaka, Victor Poupet

Publication date 4 August 2015

Published in Cellular Automata and Discrete Complex Systems (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1610.00333

Mathematics Subject Classification ID

Cellular automata (computational aspects) (68Q80)

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.

Recommendations

• Universality of one-dimensional reversible and number-conserving cellular automata
• A characterization of von Neumann neighbor number-conserving cellular automata
• On radius 1 nontrivial reversible and number-conserving cellular automata
• Three-dimensional rotation-symmetric number-conserving cellular automata
• A Construction Method of Moore Neighborhood Number-Conserving Cellular Automata

Cites work

• A characterization of von Neumann neighbor number-conserving cellular automata
• scientific article; zbMATH DE number 1886322 (Why is no real title available?)
• scientific article; zbMATH DE number 3323530 (Why is no real title available?)
• scientific article; zbMATH DE number 3338162 (Why is no real title available?)
• Number-conserving cellular automata I: Decidability.
• Universality and decidability of number-conserving cellular automata

Cited in

(10)

• A split-and-perturb decomposition of number-conserving cellular automata
• Efficient enumeration of three-state two-dimensional number-conserving cellular automata
• A decomposition theorem for number-conserving multi-state cellular automata on triangular grids
• Number-conserving cellular automata with a von Neumann neighborhood of range one
• Reversibility of non-saturated linear cellular automata on finite triangular grids
• Three-dimensional rotation-symmetric number-conserving cellular automata
• On radius 1 nontrivial reversible and number-conserving cellular automata
• Two-dimensional rotation-symmetric number-conserving cellular automata
• In search of cellular automata that preserve numbers: advances, limitations, and open problems
• Recent insights into number-conserving cellular automata

This page was built for publication: 5-state rotation-symmetric number-conserving cellular automata are not strongly universal

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5501611)