Rule 110

Given the concepts explained in the previous section, it has been established a direct relation to study Rule 110. First we can say is that it is a cellular automaton of the von Neumann type, as well as the automaton of Conway. The von Neumann model is a two-dimensional cellular automaton with twenty nine states in the system and five cells for each transformation ($29^{5}$). The model of Conway is a two-dimensional automaton with two states and eight cells for each transformation ($2^{9}$). Rule 110 evolves in one dimension with two states and three cells in its transition rule ($2^{3}$).

The order of each model is really representative, nevertheless although Rule 110 has a smaller order than the model of von Neumann and Conway, the complexity that may be reproduced by this automaton is really complicated. In Rule 110 we can find each one of the elements to identify a cellular automaton of von Neumann type.

Rule 110 has an own universe originated by the variety of gliders that the system can produce and the number of interactions that they have, where this is an unlimited interaction. Since it had been mentioned, there are extensions and nonfinite groups of glides. For example, B$^{3}$ glider at the present time is not produced through some way.

Figure 6: B$^{3}$ glider

Figure 6 shows two examples rising a B$^{3}$ glider,¹ the interest is if it is possibly reproduced through others gliders (with a collision) or is product of a configuration in the Garden of Eden. All gliders in Figure 4 has $n$ extensions for every $n \geq 1$.

Rule 110 is able to yield an unlimited growth in an infinite space, Cook solves this problem on finding a glider gun as shown in Figure 4.

Rule 110 cannot construct it everything, for example the sequence (01010)* is a configuration that can just exist in the initial configuration, is a Garden of Eden and therefore the evolution rule can never construct it in the evolution space.

Rule 110 is able to create mechanisms inducing computations and therefore it is a system which supports universal computation. Each one of the devices used by Cook in the simulation of the cyclic tag system is really complicated because the synchronization of several collisions between several different gliders in a huge space is one to one, a change in a single bit destroys all the system [17].

Rule 110 can support complex emergent behaviors in large scale both in a microscopic and macroscopic level. Rule 110 is able to construct reliable components from nonreliable organism and supporting self-reproduction.

Rule 110 has many similarities with The Game of Life, a interesting problem is to know some objects that can be useful to simulate computations or other phenomena and how they can be constructed.

Figure 7: Eater and fuses objects

Figure 7 shows two new objects found in ``Rule 110 Winter WorkShop.'' The first object can be seen as a eater glider, the E glider eliminates D$_{1}$ and C$_{2}$ gliders in each collision.

The second object can be seen as a shift between gliders, D$_{1}$ and C$_{2}$ gliders are changed by a pair of C gliders in each collision against an E glider. Some of the characteristics and similarities with The Game of Life are discussed by Cook in [6].

An interesting question is: is there some evolution which never becomes stable in Rule 110?.

On the other hand, Rule 110 can directly simulate some physical phenomena, for example the simulation of solitons between structures of different construction [12] and [18], in a completely deterministic atmosphere and without forcing the cellular automaton.

The features presented by Rule 110 to implement mechanisms realizing computations or some other process based on collisions among gliders can be as extensive as The Game of Life. In this direction we can see a large number of alternatives in collision-based computing, as we can see in the book of Andrew Adamatzky [1], for example the implementation of a Turing machine in the model of Conway made by Paul Rendell.