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
automaton and their relation to tile formation:
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,
which are
Figure 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 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 3: A (2,2) rule with characteristics similar
to (2,1) Rule 110.
Figure 3 shows a sample of evolution for 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.