Subset diagram

Why should Rule 110 and its equivalents end up being so interesting? Of course Wolfram picked it out of his rogue's gallery of typical (3,1) evolution on the grounds of having evident structures, but they were messy enough, the more so against a textured background, that it would seem only the faithful took them seriously.

One evident feature which can be verified is the existence of membranes and macrocells. The membrane is the vertical spine where one or more triangles is stacked vertically, which is never violated until the quiescent space on its right disappears. Macrocells comprise the space trapped between the spines, but there are evanascent because their protection eventually collapses, sooner rather than later. In fact, not only does this transience tend to obscure their existence, but programming it is not such a simple task either.

Another characteristic of Rule 110 is that it presents a tiling problem for the plane, with integer right isosceles triangles of all sizes. However, it is a variant not found in the tiling literature, say in the comprehensive treatise of Grünbaum and Shepard [90].

  

Figure: The subset diagram for Rule 110 shows that the shortest excluded word is 01010, and more typically the regular expression 00^*100^*10. Left: Only zero links are shown, from which four trees are apparent. Center: The full diagram, leaves and all. Note how the 1's free the paths from the 0^* traps. Right: Only one links are shown; aside from the empty set, there is one single tree rooted on the three-element node {01,10,11}.

Not only is the plane tiled by the right triangles; they are the only kind allowed and all cells in the zero state must be found inside one of them. One of the simplest prohibitions described by the subset diagram is that there cannot be two parallel columns of live cells surrounded by and separated by quiescent cells.