Undecidability of CA Classification Schemes
Karel Culik II
Department of Computer Science, University of South Carolina,
Columbia, SC 29208, USA
Sheng Yu
Department of Mathematical Sciences, Kent State University,
Kent, OH 44242, USA
Abstract
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.
