5-State Rotation-Symmetric Number-Conserving Cellular Automata are not Strongly Universal
classification
💻 cs.FL
nlin.CG
keywords
automatastatescellulargivenumber-conservingrncarotation-symmetricstrongly
read the original 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.
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.