ABSTRACT
"Information" on the initial state thus propagates, typically at a fixed speed, through the cellular automaton. This chapter gives a more direct measure of the difficulty of computing the outcome of cellular automaton evolution in the context of a simple computational model involving Boolean functions. The simulations given in the table occur when only particular blocks occur in the configuration of a cellular automaton. While a large subset of possible initial configurations for a cellular automaton may be attracted to a particular form of behaviour, there are usually some special initial states, for which very different behaviour occurs. The set of configurations that can appear after t steps in the evolution of a one-dimensional cellular automaton can be shown to form a regular formal language. Starting from a disordered state in which all possible configurations occur with equal probability, irreversible cellular automaton evolution can lead to ensembles in which different configurations occur with different probabilities.
