Universality and Decidability of Number-Conserving Cellular Automata

Details Universality and Decidability of Number-Conserving Cellular Automata Universality and Decidability of Number-Conserving Cellular Automata

2003-06-17

arxiv.org/abs/nlin/0306032v1

Final version published in Theoretical Computer Science, 292:711--721 (2003)

Nonlinear Sciences

Cellular Automata and Lattice Gases

13 pages

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Universality and Decidability of Number-Conserving Cellular Automata does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Universality and Decidability of Number-Conserving Cellular Automata, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Universality and Decidability of Number-Conserving Cellular Automata will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-51202