ABSTRACT
This chapter discusses an approach to a more complete mathematical characterization of self-organizing processes in cellular automata, and possible quantitative measures of the "complexity" generated by them. It considers the limiting sets of configurations generated after many time steps of cellular automaton evolution. The chapter shows that the set of configurations generated after a finite number of steps in the evolution of any cellular automaton forms a regular language. It also shows that, starting with all possible initial configurations, the sets generated by a finite number of time steps of cellular automaton evolution always correspond to regular formal languages. The chapter suggests the general result that the regular language complexity is non-decreasing with time for all cellular automata. It discusses some preliminary steps in the application of computation theory to the global analysis of cellular automata. The chapter suggests that in fact even simple, natural, questions concerning the limiting behaviour of cellular automata are often undecidable.
