pith. sign in

arxiv: 1610.00333 · v1 · pith:SZQVIOTTnew · submitted 2016-10-02 · 💻 cs.FL · nlin.CG

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

classification 💻 cs.FL nlin.CG
keywords automatastatescellulargivenumber-conservingrncarotation-symmetricstrongly
0
0 comments X
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.