Historical background

A cellular automaton is a discrete-dynamical system which evolves through time, cellular automata theory may be divided in four stages of important contributions, the first with its precursor John von Neumann, the second with John Horton Conway, the third with Stephen Wolfram and we add a fourth stage with Matthew Cook.

In the middle of the 40's von Neumann was trying to develop a mechanism with two essential characteristics: support complex behaviors and the capacity of self-reproduction. Stanislaw M. Ullam, friend of von Neumann proposed him to take the idea into a mathematical model handling cells, in this way we have the rise of the cellular automata theory [35].

Von Neumann's model is a cellular automaton which evolves in two dimensions with twenty nine elements in the set of states and the transition function is defined by the von Neumann neighborhood, and with this model von Neumann demonstrates the feasibility of constructing a self-reproducing and an universal constructor system.

At the beginning of the 70's Conway presents a two-dimensional cellular automaton which is able to reproduce the same behaviors that the model of von Neumann, this automaton is better known as The Game of Life. But the difference of Life is that the set of states has only two elements and the transition function evolves with the Moore's neighborhood [8]. In 1982 it is demonstrated that Life can realize universal computation simulating a register machine by means of implementing logic gates [4].

In the middle of the 80's Wolfram makes a complete systematic study in one-dimensional cellular automata, where the set of states has an arbitrary number of elements greater than zero and the transition function depends on a central cell and its neighbors at both sides in a linear array.

Wolfram establishes a classification which has been projected to $n$-dimensional cellular automata [40]. This classification can be discussed in several aspects [21], [11] and [42], but we will just say that it is a phenotypical classification.

Figure 1: Wolfram classes

Class I represents stable behaviors, class II periodic behaviors, class III chaotic behaviors and class IV complex behaviors, as Figure 1 illustrates. From this classification, Wolfram conjectures that every cellular automaton class IV is able to realize universal computation, in particular he indicates in 1985 the cellular automaton Rule 110.

At the beginning of the 90's Cook resolves the conjecture of Wolfram demonstrating that Rule 110 is universal ([41] and [7]). This result has an outstanding importance within the history and the theory of cellular automata, because it is the simplest and the smallest cellular automaton fulfilling the characteristics established by von Neumann.

The result is not trivial and with theoretical interest, in this sense it is possible to establish a fourth stage where it is demonstrated that an elementary cellular automaton can make universal computation, and unlike the model of Conway, this automaton evolves in one dimension and with a linear transition function, but this point will be discussed in detail in the following section.