Rule 110 as a consequence of triangular tiles

To the extent that its ability to tile the plane with isosceles right triangles is relevant to the remaining properties of Rule 110, one ought to examine the uniqueness of this characteristic. Consider the eight neighborhoods of a $(2,1)$ automaton and their relation to tile formation:

0 0 0	0		quiescent state and interior of the triangle
0 0 1	1		left expansivity, defining hypotenuse
0 1 0	1		permanence of left edge (x10 $\rightarrow$ 1)
0 1 1	a		[square up top left corner]
1 0 0	0		interior, when next to left edge
1 0 1	b		[close off bottom]
1 1 0	1		permanence of left edge (x10 $\rightarrow$ 1)
1 1 1	0		top edge gives way to interior

Six of the eight transitions are hardly controversial; that the ones marked a and b should evolve to 1, if not evident at first sight, becomes apparent after examining a trial evolution. Leaving the values a and b open for the moment, the Wolfram scheme of rule numbering yields four alternatives,

$$\begin{eqnarray*} {\rm rule} & = & 70 + 8 a + 32 b, \end{eqnarray*}$$

which are

a/b	0	1
0	70	102
1	78	110.

Figure 1.2: Some slight variants on Rule 110, according to the retention of the upper left corner of triangles, and likewise whether the bottom vertex is closed off or not.

In Figure  1.2 we see that Rules 70 and 78 are clearly disappointing, whereas Rule 102 shows some character; nevertheless closing the right-angle vertex leads to lots of diagonal protuberances which do not look very tile-like.

In essence, Rule 110 seems to be uniquely defined for tiling purposes. Of course, we could experiment with triangles with a horizontal hypotenuse, and there may be other interesting figures, even if not available with (2,1) rules. Within the realm of binary, first-neighbor automata, are there other rules for which similar results can be inferred? The Santa Fe AI archive mentions Rule 54 as possibly having computability traits in common with Rule 110.

Generalizing to bigger neighborhoods, (2,2) rules might be a place to start. First choice might be the iterate of Rule 110, which is Rule 729E529E (in hexadecimal). Gliders still exist, although with an altered appearance due to essentially displaying every second generation of Rule 110 and seeing triangles collapse twice as fast because of the new light velocity.

To obtain a rule with the same rate of collapse, a table similar to the one shown above can be constructed. But the results are substantially the same, and there is much redundancy due to the don't-care conditions on the left to guarantee that the triangle has the desired right-hand structure. In fact, one is practically embedding a (2,1) automaton into a (2,2) automaton by ignoring the outer margin. However the choice of an image for the neighborhood (x x 1 1 0) is less critical, and gives some variation.

In fact, tinkering with any of the rules shouldn't alter their behavior much. Wentian Li and others have studied the amount of tinkering required to drastically change the nature of the rule, and of course found that some rules were more sensitive than others. In general, if any of the diagrams, especially the de Bruijn diagram, have meagre linkages between loops sparsely interconnected, cutting or adding links can have drastic consequences. If the diagrams are more prolifically connected, such changes can go practically unnoticed. There is a perturbation theory of sorts for rules and their graphs.

There are gliders in rules with more than two states, but relating them to a tiling supposes a better idea of what the tiles should look like than has been discussed here. As to why tiling by triangles or other tokens should be different from tiling with individual cells, the answer is that the rule has been subsumed into the shape of the tile, and the requirement is the purely geometric one of filling the plane (perhaps with selected overlap) and the rule need no longer be consulted. Although that just gives bigger tiles, it seems to be useful change of emphasis.

Some (2,2) rules displaying triangles and gliders to some extent or other are: 3CBC3CBC, 3CFC3CBC, 3CBC3CFC, 3CFC3CFC, 7CFCFCBC. The main freedom lies in deciding what to do with short sequences of 1's - start a new triangle, or not.

Figure 1.3: A (2,2) rule [3CBC3CFC] with characteristics similar to (2,1) Rule 110.

Figure 1.3 shows a sample of the evolution according to the second neighbor, binary rule 3CBC3CFC, which resembles Rule 110. Not all triangles are completely rimmed, and the gliders seem to be quite a bit weaker than those in Rule 110. But there are several other nearby rules, all of which show gliders to one degree or another, all waiting to be examined.

Figure 1.4: A (4,1/2) rule [1EF4BEF4] with characteristics similar to (2,1) Rule 110.

Although it still represents the same rule, there is a blocking technique described by Moore and Drisko [7] which will transform any rule into an equivalent two-neighbor rule. The (2,1) Rule 110 transforms into the (4,1/2) Rule 1EF4BEF4, a sample of whose evolution is shown in Figure 1.4. Gliders and the ether are still recognizable, but the half-integer radius breaks up the planar tiling which is the most evident aspect of Rule 110.

The right side of Figure 1.4 shows some mean field contours for Rule 1EF4BEF4 from which two fixedpoints are evident. one of which reflects the fact that 00 pairs, representing an unused quiescent background, give an unstable fixed point. The other corresponds to a higher density, and presumably relates to the stable background provided by the ether.