Introduction

In the last years the study of dynamical systems has had a lot of interest, mainly in complex systems and chaos theory. Cellular automata are discrete dynamical systems that evolve through time, these can evolve in several dimensions.

In general, cellular automata can be represented by a set $K$ of states, a transition function $\varphi$, a neighborhood radius $r$ and an initial configuration $c_{i}$. Rule 110 is a cellular automaton with two states in its alphabet and which evolves in one dimension.

A neighborhood is formed by a central cell and $r$ cells to right and $r$ cells to the left, that is, its neighbors. The transition function evaluates each one of the neighborhoods of the evolution rule, determining the state of cell for the following generation.

The initial configuration is a linear array of finite length, a single element or the set $K$ is assigned to each one of the cells, this assignation can be made in a random way. The transition function evaluates each one of the neighborhoods defined by the evolution rule, forming a new configuration from a given generation to the next.

Using the notation defined by Stephen Wolfram [9], rule 110 is a cellular automaton of order $k=2$ and $r=1$, the set of states is $K=\{0,1\}$, a neigborhood is formed by $2r+1$ cells and the evolution rule has $k^{2r+1}$ neighborhoods, this way rule 110 is represented like:

Table 1.1: Evolution rule 110

Transition function
$\varphi(0,0,0) = 0$	$\varphi(1,0,0) = 0$
$\varphi(0,0,1) = 1$	$\varphi(1,0,1) = 1$
$\varphi(0,1,0) = 1$	$\varphi(1,1,0) = 1$
$\varphi(1,1,0) = 1$	$\varphi(1,1,1) = 0$

in decimal notation we have $2^{0}(0)+2^{1}(1)\cdots+2^{7}(0)=110$.

Mathew Cook has made an extensive study of this cellular automaton, finding complex behaviors produced by the evolution rule in the evolution spaces. In [2] Cook presents a classification of the gliders^1.1 produced by rule 110. This one is the serious motivation to make a detailed analysis of the gliders and their collisions, taking the studies made by Harold V. McIntosh on [6] and [7] as basis.

Rule 110 shows behaviors similar to those observed in ``The Game of Life'', a cellular automaton of two dimensions proposed by John Horton Conway [1]. If the central cell is the state 0, then in the following generation it has the same value that its right neighbor. If the central cell is the state 1, in the following generation it conserves this same value; but if both neighbors are equal to the state 1, the cell changes to 0.

One of the main differences between rule 110 and The Game of Life, is that rule 110 evolves in a periodic background and Life evolves in a stable one.

Rule 110 almost operates like the binary fuction OR operating on the two right cells of each neighborhood, except for the last one. Cook notices that in the case when the central cell is 0, in the following generation this one takes the value from its right neighbor and in any other case it follows the binary fuction NAND.

This cellular automaton can support complex behaviors through the interaction of gliders or decompositions of long transient structures. McIntosh in [6] presents an approach different from the one presented by Cook in [2], showing that rule 110 can be represented with mosaics.

This viewpoint is used in this analysis for dertermining with detail each one of the gliders, so that the amount of mosaics necessary to construct each one of them. The mosaics differ in size from T1 to T45 [7], these mosaics are rectangular triangles where the size of the triangle is defined by its interior, adding the amount of zeros which exist in any of its sides. Different combinations of Tn's can reproduce any structure generated by rule 110. Finally rule 110 can be see like a problem of covering the plane with triangles [3].

This initial study presents that rule 110 is defined in four fundamental phases, each one of these characterizes the different types of collisions which exist between gliders. These phases are determined by the periodic background or ``ether'' and all reproducible structure in the evolution space follows these phases.

It is important to see that the phases of ether can determine each one of the collisions between gliders and they restrict a distance among them as well. That distance is determined by the period 14 of the ether and it allows to give a space for the phases of each one of these structures, but this does not imply that it is the minimum distance that can exist.

First, the two types of triangles that can exist for a given Tn are presented, then each glider is characterized in full detall, in this part it is seen that each glider can cover the whole evolution space. Gliders are partitioned in phases, this allows to specify each one of the chains that produce given glider with a particular phase.

The contact points that a given glider has are determined, these contact points specify the type of collision that is desired to calculate. Finally all the collisions that can be produced of natural way in the evolution space are showed, finding very simple, very complex, symmetrical and some very pretty results.

In the list it is possible to see how a given glider can be obtained from others, besides some solitons, some symmetrical productions and united groups of gliders are presented.