|
| | | | |
| | | |
| Stat |
Members: 3645
Articles: 2'506'133
Articles rated: 2609
26 April 2024 |
|
| | | | |
|
Article overview
| |
|
|
Universality and Decidability of Number-Conserving Cellular Automata | | Andres Moreira
; | | Date: |
17 Jun 2003 | | Journal: | Final version published in Theoretical Computer Science, 292:711--721 (2003) | | Subject: | Cellular Automata and Lattice Gases | nlin.CG | | Abstract: | 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 $set$, 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. | | Source: | arXiv, nlin.CG/0306032 | | Services: | Forum | Review | PDF | Favorites | |
|
|
No review found.
Did you like this article?
Note: answers to reviews or questions about the article must be posted in the forum section.
Authors are not allowed to review their own article. They can use the forum section.
browser Mozilla/5.0 AppleWebKit/537.36 (KHTML, like Gecko; compatible; ClaudeBot/1.0; +claudebot@anthropic.com)
|
| |
|
|
|
|
News, job offers and information for researchers and scientists:
| |
REGISTER