Undecidability of CA classification schemes. (English) Zbl 0657.68054

Stephen Wolfram introduced the use of cellular automata as models of complex systems and proposed a classification of these automata based on their statistically observed behavior. We investigate various properties of these classes; in particular, we ask whether certain properties are effective, and we obtain several somewhat surprising results. For example, we show that it is undecidable whether all the finite configurations of a given cellular automaton eventually become quiescent. Consequently, it is undecidable to which class a given cellular automaton belongs, even when choosing only between the two simplest classes.


68Q80 Cellular automata (computational aspects)
68Q25 Analysis of algorithms and problem complexity