𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Universality and decidability of number-conserving cellular automata

✍ Scribed by Andrés Moreira

Publisher
Elsevier Science
Year
2003
Tongue
English
Weight
138 KB
Volume
292
Category
Article
ISSN
0304-3975

No coin nor oath required. For personal study only.

✦ Synopsis

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 deÿnition of the property to include cellular automata with any set of states in Z, 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 ÿnd this relabeling if the answer is positive.

📜 SIMILAR VOLUMES

Number conserving cellular automata II:
Number conserving cellular automata II: dynamics
✍ Enrico Formenti; Aristide Grange 📂 Article 📅 2003 🏛 Elsevier Science 🌐 English ⚖ 474 KB

In this second part, we study the dynamics of the number conserving cellular automata. We give a classiÿcation which focuses on pattern divergence and chaoticity. Moreover we prove that in the case of number-conserving cellular automata, surjectivity is equivalent to regularity. As a byproduct we ob