The Rule 110 Cellular Automaton…[No text on this page] Objects constructed from localized structures in rule 110, used for the emulation of cyclic tag systems. … (Note that all the structures are left-right reversed in rule 110.)

The Rule 110 Cellular Automaton…Pictures (a) and (b) on the previous page illustrate the consequences of applying the rules for a cyclic tag system, but in a sense give no indication of an explicit mechanism by which these rules might be applied. … By looking at picture (d), one can begin to see how it might be possible for a cyclic tag system to be emulated by rule 110: the basic

The Rule 110 Cellular Automaton…The pictures on the last few pages [ 683 , 684 , 685 , 686 ] were all made for a cyclic tag system with a specific underlying rule.

The Rule 110 Cellular Automaton

The Rule 110 Cellular Automaton

The Rule 110 Cellular Automaton

Note (a) for The Rule 110 Cellular Automaton…Initial conditions [for rule 110] The following takes the rules for a cyclic tag system in the form used on page 895 (with the restrictions in the note below), together with the initial conditions for the tag system, and yields a specification of initial conditions in rule 110 which will emulate it. … The b 1 blocks act like "clock pulses", b 2 encodes the initial conditions for the tag system and the b 3 blocks encode the rules for the tag system. … The core of the right-hand block grows approximately like 500 (Length[Flatten[rules]] + Length[rules]) , but to make a block that can just be repeated without shifts, between 1 and 30 repeats of this core can be needed.

Note (c) for The Rule 110 Cellular Automaton…Following my ideas about class 4 cellular automata I had come by 1985 to suspect that rule 110 must be universal. … 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.

Note (b) for The Rule 110 Cellular Automaton…Tag systems [for rule 110] The discussion in the main text and the construction above require a cyclic tag system with blocks that are a multiple of 6 long, and in which at least one block is added at some point in each complete cycle.

So what happens with other rules? … So what else is there in common between rule 90 and rule 150? … Rule 90 and rule 150 are also essentially the only fundamentally different elementary cellular automaton rules that have the property of being additive (see page 264 ).