The Rule 110 Cellular Automaton…Like any of the 256 so-called elementary rules, rule 110 can be specified as below by giving the outcome for each of the eight possible combinations of colors of a cell and its nearest neighbors. … For despite the simplicity of its underlying rules, rule 110 supports a whole variety of localized structures—that move around and interact in many complicated ways. … The underlying rules for the rule 110 cellular automaton discussed in this section .

The Rule 110 Cellular Automaton…can be used whatever the underlying rule is. And the pictures below show schematically what happens with a few other choices of rules. … Schematic diagrams of how cyclic tag systems with four different underlying rules can be emulated.

The Rule 110 Cellular Automaton…This is then finally how universality is achieved in rule 110. … For as the pictures earlier in this section demonstrate, the way we have made rule 110 emulate cyclic tag systems relies on many details of the interactions between localized structures in rule 110. … And this means that rule 110 is indeed universal.

The Rule 110 Cellular Automaton…But in rule 110 there are only two possible colors for each cell. … A typical example of the behavior of rule 110 with random initial conditions. … Note that page 292 already showed many of the types of localized structures that can occur in rule 110.

The Rule 110 Cellular Automaton…[No text on this page] A schematic diagram of how rule 110 can be made to emulate a cyclic tag system. Each line in this diagram corresponds to one localized structure in rule 110. … Note also that lines shown in different colors here often correspond to the same structure in rule 110.

The Rule 110 Cellular Automaton…And indeed in the case of rule 110 it took several years of work to develop the necessary ideas and tools. But finally it has turned out to be possible to show that the rule 110 cellular automaton is in fact universal. … So if we can succeed in demonstrating that rule 110 can emulate any cyclic tag system, then we will have managed to prove that rule 110 is itself universal.

The Significance of Universality in Rule 110…The Significance of Universality in Rule 110 Practical computers and computer languages have traditionally been the only common examples of universality that we ever encounter. … But what in fact we have seen is that a cellular automaton with one of the very simplest possible 256 rules manages to be universal. … But knowing that a system like rule 110 is universal, the whole picture changes, and now it seems likely that instead universality should actually be seen in a very wide range of systems, including many with rather simple rules.

The Rule 110 Cellular Automaton…[No text on this page] Four views of a cyclic tag system with rules as shown above, drawn so as to be progressively closer to what can be emulated directly in rule 110. … Picture (c) is a skewed version of (b) in which the way information is used from the underlying rules at each step is explicitly indicated.

The Rule 110 Cellular Automaton…One might assume that by using more and more sophisticated underlying rules, one would always be able to construct systems with ever greater computational capabilities. … But how complicated do the underlying rules need to be in a specific case in order actually to achieve universality? … And by not imposing this constraint, one might expect that one would be able to find universal cellular automata that have at least somewhat simpler underlying rules.

The Rule 110 Cellular Automaton…idea is to have each of the various kinds of lines in the picture be emulated by some collection of localized structures in rule 110. … Note that because of the particular form of rule 110, the objects in the second two pictures on the previous page move to the left rather than to the right. And indeed in setting up a correspondence with rule 110, it is convenient to left-right reverse all pictures of cyclic tag systems.