ABSTRACT
Cellular automata are mathematical models for complex natural systems containing large numbers of simple identical components with local interactions. This chapter discusses the nature of this complex behaviour, its characterization, and classification. Based on investigation of a large sample of cellular automata, it suggests that many cellular automata fall into four basic behaviour classes. The chapter describes some preliminary steps towards a general theory of cellular automaton behaviour. It discusses general qualitative features of cellular automaton evolution illustrating the four behaviour classes. The chapter introduces entropies and dimensions which characterize global features of cellular automaton evolution. Successive sections consider each of the four classes of cellular automata in turn. The chapter covers a broad area, and includes many conjectures and tentative results. It concerns one-dimensional cellular automata. Two-dimensional cellular automata also appear to exhibit a few distinct classes of behaviour. The complexity of regular grammar may be used to characterize the complexity of large time behaviour of the cellular automaton.
