Universality and Decidability of Number-Conserving Cellular Automata
| dc.creator | Moreira, Andres | |
| dc.date | 2003-06-17 | |
| dc.date.accessioned | 2026-07-07T05:34:47Z | |
| dc.date.available | 2026-07-07T05:34:47Z | |
| dc.description | 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. | |
| dc.description | 13 pages | |
| dc.identifier | https://arxiv.org/abs/nlin/0306032 | |
| dc.identifier | http://arxiv.org/abs/nlin/0306032 | |
| dc.identifier | Final version published in Theoretical Computer Science, 292:711--721 (2003) | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/80504 | |
| dc.subject | Cellular Automata and Lattice Gases | |
| dc.title | Universality and Decidability of Number-Conserving Cellular Automata | |
| dc.type | text |