The recent claim that Rule 110 is Universal depends on an intricate series of glider collisions, which at first sight is simply bewildering. On examination, it appears that there may be a chain of reasoning which will lead up to the construction which has ben presented, or possibly even to alternative constructions.
Structures which are technically gliders of many kinds exist in Rule 110, but those which seem to offer the most potential and variety are those which are confined to the ether background, of which around a dozen exist. Due to the cyclic nature of the ether, spatial period 14 and temporal period 7, there are parity rules for dislocations in the ether; the most useful of these is for simple binary parity itself. Thus gliders are either even or odd, combinations of gliders add their parities, and the overall parity must be conserved throughout a collision and ever afterwards.
Collisions between odd gliders either give an even, possibly null, result or produce another pair of odd gliders. It is not excluded that these are the same gliders, simply having changed places, giving an instance of solitons. The existence of solitons suggests the transmission of information from one end of a block of structures to the other so that activities could go on in several places and be related to one another, rather than having to wait for the intervening space to work itself out in a more complicated and unpredictable way.
Experimental evolutions and de Bruijn diagrams reveal the existence of gliders and quantify them according to possible shift periodicities. Further experiments reveal the consequences of glider collisions, although they become tedious due to the number of gliders that have to be included. As more and more gliders are involved in simultaneous collisions, the task becomes unmanageable. For Rule 110 several solitonic combinations have been discovered, involving C, F, and EBar gliders. Many other combinations wherein A and B gliders are absorbed and later reemitted can be taken as solitonic. There may be multipliers, which would produce more gliders than the number which first collided. Pure absorbers would be black holes, pure emitters would be glider guns. So far only one glider gun is known, creating A's and B's in equal quantities.
A recent universality proposal relies extensively on the interactions of static C gliders with travelling EBar gliders. Actually the most viable candidate for a static glider was one (or more) of the C gliders, which are already static. Two velocities, to allow overtaking, seems necessary and zero velocity is not an a priori requirement. Playing EBar's off against F's doesn't seem very promising, whereas C's are more appealing. En's are plausible candidates for the second member of the pair, but the final proposal calls for EBars.
Beyond creating a data flow from one part of an extended structure to another, there should be some way to start and stop the flow, which implies a predicate to make the decision. Indeed, one procedure divides a flow into two parts, from which the predicate deletes one, allowing the survivor to continue on its way. Thus there are two tasks; erasure and the decision as to when to apply it. It also turns out that more complicated solitons are required than just those found by examining binary collisions.
We consider three parts of the possibilities of data movement in turn: erasure of oncoming elements, the predicate determining whether erasure will take place, and the solitonic requirements to cross intervening space. Stopping the flow at the other end is also required, but was already more fully understood.
According to [19], page 1115 (Stephen Wolfram speaking):
`` ... [1991] ... the general outline of what had to be done was fairly clear -- but there was an immense number of details to be handled, and I asked a young assistant of mine named Matthew Cook to investigate them. His initial results were encouraging, but after a few months he became increasingly convinced that rule 110 would never in fact be proved universal. I insisted, however, that he keep on trying, and over the next several years he developed a systematic computer-aided design system for working with structures in rule 110. Using this he was then in 1994 successfully able to find the main elements of the proof. Many details were filled in over the next year, some mistakes were corrected in 1998, and the specific version in the note below was constructed in 2001. Like most proofs of universality, the final proof he found is conceptually quite straightforward, but is filled with many excruciatingly elaborate details. And among these details it is certainly possible that a few errors still remain. But ...''
The eventual solution can be divided into two parts; the first consists in identifying promising glider collisons, the second in getting them to work together in the semblance of a computation. The mechanism chosen for the latter is a Cyclic Tag System, similar to the scheme introduced by Emil Post in the 1920's, but its details need not concern us.
The useful collisions, which are described forthwith in detail, permit erasure, filtratration through a barrier, and the selection of alternatives; a predicate, if you will.
It might be opportune to explain that the word ``universal,'' as applied to computation, has two meanings. The general, expansive, form asserts that ``You can compute anything.'' As such, it is a variant of Church's thesis, that all logical or mathematical reasoning is based on specific procedures. These are the arithmetical operations, tests for equality, and the use of certain rules of inference. Whitehead and Russel's Principia Mathematica goes to some length to establish this foundation.
The narrower interpretation is embodied in Turing's construction of a model computer, which procedes in three stages. The first shows how an extremely simple, but nevertheless definite and concrete, device can realize the primitive operations, such as balancing parentheses, adding numbers, copying lists, and so on.
In the second stage, it is shown that there is a description of such a device, using parentheses, lists, comparisons and such like, given by a set of quintuples. Universality consists in showing that there is one special device, admitting its own description via a quintuple set, which can mimic the operation of any other, including itself. It is universal, because it is the only device you will ever need to preform calculations according to the agreed procedure.
The third stage, of course, is the notorious one; such a device cannot even bebug itself!
A certain balance is involved in all this. To be called ``computing'' a process must have a certain complexity - the ability to do arithmetic. But the enterprise has its limitations, so a criterion for not being universal is certainly not leaving any uncertainty in the results. From there on, the use of the word universal is purely a philosophical problem.
The ``universal constructor'' of John von Neumann and the discovery of the Garden of Eden may illustrate the point. His constructor was implemented via a cellular automaton with certain rules and was capable of building anything for which it had a blueprint, and (in principle; it was complicated) had its own blueprint. Yet there were configurations of the automaton which could not be constructed, because they could only exist at the first step, as initial states.
So bear in mind -- universality in the strict sense can sometimes be demonstrated, although establishing an adequate system of collisions for Rule 110 shows how arduous the process can be. The possibility for universality in the general sense, that ``you can compute anything,'' only then becomes a possibility, ranking as an alternative route to Church's thesis.
That it is a possibility only establishes a possible degree of complexity; it does not say that the environment will ever perform a computation, much less some specific one. Such complexity could well be evident on other grounds.
In any event, we are only going to exhibit a series of interesting glider collisions which will confirm the existence of a Cyclic Tag System; their possible utility and eventual application is something else again.