Figure 51: A and C gliders, colliding just right,
transform into an F.
However, that was not the reason for the interest in a straightjacket. Two diagrammatic studies supplement plain search programs. Labelled de Bruijn diagrams will reveal all the possible cycle lengths for shift periodic automata (at least, without further complication, in one dimension). From these gliders can be picked out directly, and with a certain versatility, some other things related to gliders, such as puffer trains. In a similar spirit, the Wuensche-Lesser basin diagrams will reveal all periodicities inherent in cyclic configurations; gliders can often be perceived from examining these diagrams too.
Within their range of applicability both diagrams give complete results, eliminating doubts as to whether something was overlooked; and as a theoretical matter, establish bounds (even though exponential) on the lengths of periods given the cycle, or the length of cycles, given the period. As a practical matter, that exponential factor rather severely limits the range to which the diagrams can be applied, leaving the search programs as the effective alternative.
Figure 52: One of the reasons that large
triangles do not occur often in evolutions is that they do not pack well.
Using cyclic configurations to find gliders has limitations, especially when the gliders are sought against a textured background, as in the case of Rule 110. The idea of the straightjacket consists in fixing the boundary cells of an interval and looking at the evolution so constrained, which is certainly not a new idea by any means. In the case of gliders, the boundary can be staggered according to the velocity of the glider.
However, there is a complication, namely that the postulated boundary may not be compatible with the evolution of the full field, after all. The result is that running out the constrained basin diagram gives a necessary, but not sufficient, condition that the nuclear (transient-free) diagram defines gliders which can be inserted into the given background. Between necessity and sufficiency lies a compatibility problem, expressible via the Post Correspondence Principle, a/k/a the word problem, with a good liklihood of being undecidable: ``It is undecidable whether there exists a glider of arbitrary velocity s/d (displacement/generation) in a textured automaton.''
``Textured'' rules out arbitrary Class III automata unless agreement on an ``ether'' can be reached, whereas Class I and II automata do not have enough texture to raise the word problem out of triviality. In other words, it all depends on whether the sequence the straightjacket program generates is complex enough to create a word problem when checked against the boundary sequence.
Note a difference between the basin calculation and what is proposed here: Basin programs generate trees rooted on loops (and hence loop nuclei) because of the functional character of cyclic evolution. A stipulated boundary has to compensate the degradation of the automaton's interval due to the discrepancy between neighborhood and cell; when there is shifting, it has to be thicker still. Therefore the map of a glider's- width-interval always depends on some boundary cells, but still more at shift points. An interval will always have a successor, but possibly more than one, in contradistinction to the cyclic case; therefore nuclei need not be simple loops. Otherwise there would be no word problem.
As far as actually testing this, the gliders reported by Cook and Lind together with the margins they require imply a greater computational effort than that to which I have been accustomed. But at least I hope that I finally have a glimmering as to how Cook actually relates Rule 110 to a Post Tag Sequence.