2003/06/17 by Andres Moreira
Physics and Astronomy · #nlin.CG
published as Final version published in Theoretical Computer Science, 292:711--721 (2003) · 13 pages
arxiv created 2003/06/17 · arxiv updated 2009/11/30
Number-conserving cellular automata (NCCA) are particularly interesting, both because of their natural appearance as models of real systems, and because of the strong restrictions that number-conservation implies. Here we extend the definition of the property to include cellular automata with any set of states in \Zset, and show that they can be always extended to ``usual'' NCCA with contiguous states. We show a way to simulate any one dimensional CA through a one dimensional NCCA, proving the existence of intrinsically universal NCCA. Finally, we give an algorithm to decide, given a CA, if its states can be labeled with integers to produce a NCCA, and to find this relabeling if the answer is positive.