Yet to take full advantage of universality one must consider not only translations between objects but also translations between complete proofs. … But in the end history seems to be the only real determining factor. … And most often what has happened is that there are only certain kinds of questions or statements that have been considered of real mathematical interest.

Part (b) of the picture shows a version of the evolution compressed to include only A register machine whose behavior seems in some ways random. … Part (b) shows the evolution in compressed form, with only those steps included at which either of the registers has just decreased to zero. … If one value is n , then the next value is 3n/2 if n is even, and (3n+1)/2 if n is odd.

In a sense what is happening here is that even though rule 126 usually shows class 3 behavior, it is possible to find special initial conditions that make it behave like a simple class 2 rule. … Rule 126 will for example behave just like rule 90 if one starts it from special initial conditions that contain only blocks consisting of pairs of black and white cells. … If one looks only on every other step, then the blocks behave exactly like individual cells in rule 90.

And of the 256 elementary cellular automata with two colors and nearest-neighbor rules, only the six shown below turn out to be reversible. And as the pictures demonstrate, all of these exhibit fairly trivial behavior, in which only rather simple transformations are ever made to the initial configuration of cells.

In the first two cases, there are then only two distinct blocks that occur, so each of these can be represented by a codeword consisting of a single cell, with the result that substantial compression is achieved. … In cases (a) and (b), only two possible blocks occur, and these are assigned codewords consisting of a single black cell and a single white cell.

But as we saw in the previous chapter , such analysis tends to be useful only when the overall behavior one is studying is fairly simple. … If traditional science was our only guide, then at this point we would probably be quite stuck.

To get behavior that is more complicated than simple nesting, it follows therefore that one must consider substitution systems whose rules depend not only on the color of a single element, but also on the color of at least one of its neighbors. The pictures below show examples in which the rules for replacing an element depend not only on its own color, but also on the color of the element immediately to its right.

However, as was shown in the 1800s, this method can yield only numbers formed by operating on rationals with combinations of Plus , Times and Sqrt . … (Linkages were used by the late 1800s not only in machines such as steam engines, but also in devices for analog computation. … Note that above degree 4, algebraic numbers cannot in general be expressed in radicals involving only Plus , Times and Power (see page 945 ).

But usually these turn out to lead only to modest speedups, and despite various hopes over the years there seem in the end to be no techniques that work well across any very broad range of systems. … Typically the idea is that after a sufficiently long time a system should be found only in states that are invariant under the application of its evolution rules. … Instead, as the pictures at the top of the facing page show, one sees a variety of patterns that very Two of the 28 elementary cellular automata whose only invariant states are uniform in color.

And because this active cell is the only one that ever gets updated, there is never any issue about synchronizing behavior of different elements at a given step. … But because an observer who is part of a mobile automaton can in effect only occasionally tell what has happened, then as far as such an observer is concerned, many cells can appear to have been updated in parallel between successive moments of time. … But in fact, it turns out that it is sufficient just to look at the evolution of the mobile A mobile automaton in which only the single active cell indicated by a dot is updated at each step, thereby avoiding the issue of global synchronization.