Preliminaries in Rule 110

The study of Rule 110 began with the first investigations of Wolfram about one-dimenional cellular automata.

Let us define some basic concepts used in the literature of cellular automata. Dynamics in one dimension is simple, we have a set of states $\Sigma \in \mathbb{Z}^{+}$, a finite linear array where each element takes a value from the set of states, this array is the initial configuration of the system. A neighborhood has a central cell and $r$ neighbors on each side, where $r \in \mathbb{Q}$ and $k = \vert \Sigma \vert$; thus the neighborhood is of size $2r+1$ and the transition function $\varphi$ simultaneously evaluates each one of the $k^{2r+1}$ neighborhoods throughout the array in each generation $t$, where $t$ represents time. The previous concepts are illustrated in Figure 2.

Figure 2: Dynamics in one dimension

Wolfram develops a complete systematic analysis in this type of cellular automata with order $(2,1)$, discovering that Rule 110 has complex behaviors and he establishes the conjecture that this rule can realize universal computation.

Rule 110 is a one-dimensional cellular automaton of order $(2,1)$ also called elemental by Wolfram, two states and a neighbor on each side. This automaton belongs to class IV because it has complex behaviors, that is, regions with stable, periodic and chaotic behaviors in the same evolution space. The evolution rule 110 (01110110$_{2}$) is defined for the transformation of each neighborhood: 000, 100 and 111 evolve into state 0 in the following generation and neighborhoods 001, 010, 011, 101 and 110 evolve into state 1.

Figure 3: Random evolution in Rule 110

Figure 3 illustrates an example for the evolution of Rule 110 from a initial random configuration, we can see regions with stable behaviors (periodic background called ether by Cook), periodic regions represented by gliders, chaotic regions constructed by non-periodic structures during a long time which produces complex behaviors. The right figure is the same evolution but we have changed the ether colors which makes easier to identify gliders and chaotic constructions in the evolution space.

Cook specifies a classification of these periodic structures known in cellular automata literature as gliders [6], where glider means a periodic structure moving through time.

Figure 4: List of gliders according to the classification given by Cook

Figure 4 shows all the gliders until now known in Rule 110. Note that there exists gliders with shifts from right to left, from left to right and with no shift as the case of the C gliders. An interesting structure is the glider Gun which generates A and B gliders periodically. Other relevant remark is the ample variety of options for constructing a glider Gun, among other complicated constructions in Rule 110 as we can see in [16].

The first article dedicated to the analysis of Rule 110 is by Wentian Li and Mats G. Nordahl in 1992 [20], where a statistical study is developed and some of the most common behaviors in the evolution space of Rule 110 are ilustrated.

In 1998 during a conference celebrated in Santa Fe Institute, Cook demonstrates how Rule 110 can realize universal computation. In January 1999 Cook presents a list of gliders found in the evolution space of Rule 110 [6]. At the present time this information is not available in Internet by legal problems, nevertheless these data can be consulted in [23], [41] and [15]. A good reference discussing this legal problem may be consulted in [9].

On the other hand, in 1999 Harold V. McIntosh develops an investigation based in Rule 110 is a problem of covering the evolution space with triangles [23].

Wolfram presented in March 2002 the book A New Kind of Science, where the cover is indeed an evolution of Rule 110. The book includes an ample variety of subjects and many illustrations, emphasizing the operation of an equivalent Turing system in Rule 110.