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

DOI10.1007/978-3-319-18812-6_3zbMATH Open1432.68278arXiv1610.00333OpenAlexW938177330MaRDI QIDQ5501611FDOQ5501611

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)

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.

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

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

Mathematics Subject Classification ID

Cellular automata (computational aspects) (68Q80)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Number-conserving cellular automata I: Decidability.
• Universality and decidability of number-conserving cellular automata
• A characterization of von Neumann neighbor number-conserving cellular automata
• Title not available (Why is that?)

Cited In (8)

• Reversibility of non-saturated linear cellular automata on finite triangular grids
• Number-conserving cellular automata with a von Neumann neighborhood of range one
• Two-dimensional rotation-symmetric number-conserving cellular automata
• On radius 1 nontrivial reversible and number-conserving cellular automata
• Three-dimensional rotation-symmetric number-conserving cellular automata
• A decomposition theorem for number-conserving multi-state cellular automata on triangular grids
• A split-and-perturb decomposition of number-conserving cellular automata
• Efficient enumeration of three-state two-dimensional 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)