Abstract | ||
---|---|---|
We discuss attempts at the classification of cellular automata, in particular with a view towards decidability. We will see that a large variety of properties relating to the short-term evolution of configurations are decidable in principle, but questions relating to the long-term evolution are typically undecidable. Even in the decidable case, computational hardness poses a major obstacle for the automatic analysis of cellular automata. |
Year | DOI | Venue |
---|---|---|
2012 | 10.1080/03081079.2012.695899 | INTERNATIONAL JOURNAL OF GENERAL SYSTEMS |
Keywords | Field | DocType |
cellular automata, classification, Wolfram classes, decidability, automaticity | Obstacle,Cellular automaton,Discrete mathematics,Automata theory,Mobile automaton,Decidability,Automaticity,Mathematics,Undecidable problem | Journal |
Volume | Issue | ISSN |
41 | 6 | 0308-1079 |
Citations | PageRank | References |
6 | 0.56 | 6 |
Authors | ||
1 |
Name | Order | Citations | PageRank |
---|---|---|---|
Klaus Sutner | 1 | 119 | 19.42 |