Introduction

Recently the cellular automaton labeled ``rule 110'' by Wolfram way of naming these[14] , has been shown to have the capability of universal computation. Matthew Cook built an intricate system of glider collisions and coding of a cyclic tag system to establish this result[1].

Inspection of the evolution of rule 110 reveals an orderly combination of right isosceles triangles which not only combine to forms the gliders, but some of them combine into a background where gliders appear as defects.

Triangles commonly appear in the space-time diagram of cellular automaton evolution, but those of rule 110 define a covering of the plane by a family of triangles which can be interpreted as a shift of finite type. This gives an entirely different perspective to the proof of computational universality. In the following, we elaborate the algebraic foundation of this point of view, beginning with some elementary definitions[7][8][9].

Cellular automata are dynamical systems, discrete in time that involve four elements for their definition:

1. Cellular space $S$ . An array of dimension $d\in\mathbb{N}^+$ , of sites called cells.
2. A neighborhood configuration, that is the same for all cells in the cellular space.
3. A set of cellular states $K\leftrightharpoons\{0,\dots,k-1\}$ ; where normally $k << \infty$ . The $\leftrightharpoons$ symbol means ``defined as" or ``equals by definition''.
4. A local evolution rule $\phi$ , defined over all neighborhood space $\phi :K^r \rightarrow K$ . Where $r$ is the neighborhood radius.

In our case $d=1$ , i.e. $S=<\dots,s_{i-1},s_i,s_{i+1},\dots>$ . However, for computational reasons, we need to consider a finite cellular space, so $S=<s_0,s_1,\dots,s_{i-1},s_i,s_{i+1},\dots,s_{n-2},s_{n-1}>$ . We consider cyclical conditions in boundaries of cellular space. The neighborhood configuration for a cell is constituted by all cells in radius 1, including the central cell; in symbols, $\nu=<s_{i-1},s_i,s_{i+1}>$ , for $i=0,\dots, n-1 \mod{n}$ , where $n$ is the size of the cellular space.

When the system evolves in discrete time steps, graphical patterns emerge from their evolution, which can be visualized by putting in a plane successive instances of cellular space. The main interest is centered into the apparent interaction of those graphical forms. This interaction could represent some kind of computation, and furthermore, if it makes computation, what are its capabilities including the universal computation. However, the rule 110 is not the only rule that generate this kind of patterns, as we can see in figure 1. The local evolution rules are in table 1.

Figure 1: Group of similar rules to rule 110, this includes rules 110, 124, 137 and 193. The clear color means 0-state and dark color means 0-state.

Table 1: Binary expansion of similar rules of rule 110

		110	124	137	193
0	000 $\to$	0	0	1	1
1	001 $\to$	1	0	0	0
2	010 $\to$	1	1	0	0
3	011 $\to$	1	1	1	0
4	100 $\to$	0	1	0	0
5	101 $\to$	1	1	0	0
6	110 $\to$	1	1	0	1
7	111 $\to$	0	0	1	1

Triangles under these evolution rules are formed due to combinations of cells neighborhoods in a time evolution step. Table 2 gives the possible combinations of neighborhoods for the creation of similar triangles. Table 1 shows the rule of evolution for all four automata, while table 2 explains why forms with triangle shape emerge. Because of the symmetry it is sufficient to discuss the rule 110 only(fig. 1).

Table 2: $lca(2,1)_{110}$ and how it is formed triangles shapes.

0	$000\to 0$	Makes the triangle's interior
1	$001\to 1$	Makes diagonal from top to bottom and from right to left
2	$010\to 1$	Makes the left boundary.
3	$011\to 0$	In the vertex, its makes the left boundary.
4	$100\to 1$	Forms part of the interior of each triangle,
		precisely the triangle's part that is joined to left border.
5	$101\to 1$	Finish the triangle shape in its bottom vertex.
6	$110\to 1$	Forms left border.
7	$111\to 0$	Forms part of the interior of each triangle,
		precisely the triangle's part that is joined to top border.

There are some basic definitions in algebraic topologic area that are necessary to remember. For a deep study of these basic concepts, refer to [4][5].

A cell $c_i\leftrightharpoons<x_{c_i},y_{c_i}>$ in the cellular space has only one type of neighbor, its four horizontal and vertical neighbors $c_j\leftrightharpoons<x_{c_j},y_{c_j}>$ , such that $\vert x_{c_i}-x_{c_j}\vert+\vert y_{c_i}-y_{c_j}\vert=1$ . All cells $c_j$ are the neighbors for $c_i$ and we say that $c_j$ is adjacent to $c_i$ . A path is a sequence of cells $c_1=<c_{i_0},c_{i_1},c_{i_2},\dots,c_{i_m}>=c_2$ such that $c_{i_{l-1}}$ is adjacent to $c_{i_l}$ , $1\leq l \leq n-1$ [11].