Introduction to Universality:  Rule 110

Dr. Todd Rowland
todd_rowland@wolfram.com
Wolfram Science Group
http://www.wolframscience.com/reference/education/

Description:

In this lesson we introduce the concept of universality.

We have already examples of emulation, when one rule does what another rule does. We will see that Rule 110 can emulate a much more complicated rule. Then we will discuss the concept of universality, which is when a rule can emulate any other rule.

Pre-requisites:

Objectives:

Materials:

Computer

Further Notes:

From NCTM  http://www.nctm.org/standards/

Note:  Background is periodic.  Localized structures are essentially periodic.

Note:  Compute translation speed for various structures.

Note:  The presence of localized structures is not a quantity, but it is knowable.  One quantity that can be measured in a typical situation is the number of localized structures.  N.B. in general, the string of bits may not yet be resolved into localized structures, but one can always count the cases of any particular pattern.

Background:

The last major type of behavior in an elementary cellular automaton is exemplified by Rule 110. Though not truly random, the behavior is nonetheless very complicated.  It is computationally irreducible.   But it is no longer quite as random.

Within a typical evolution of Rule 110, we can see it have regions with a regular background.  On this background, or in between these regions, there are irregularities which don't spread out.  Instead they propagate through the background at a definite speed.

What makes it complicated is the way these structures interact.  But typically, the results of these interactions are more localized structures.  We will look at some examples.

One might like to think of these localized structures as being like particles.  When the particles collide, other particles get created.  

Or one might think of them as being like a more complicated program.  Rule 110 has a simple description with bits.  But when looked at from a larger distance, one sees these localized structures.  There are lots of different structures, and they interact in many different ways.  Imagine that these interactions are defined by a rule which has many elements.  That would be a rule with many more elements than an ECA.  Also the timing of their interactions is quite a bit more complicated than an ECA.

When looking at digital information, at the lowest level all one sees is bits.  But if the bits represent something more complicated, then one has to consider large pieces of the string.   Just as one can use bits to represent information with more elements, an ECA can emulate a rule with more elements.  What we see with Rule 110, is that at a larger scale it is really doing a much more complicated computation.

So Rule 110 emulates this much more complicated rule.  Even more is known about this more complicated rule which uses the localized structure of Rule 110.  It can emulate any other rule.  That is called universality.  It means that Rule 110 can emulate any other rule.

Procedure:

Show[
        Graphics[
          Raster[1  -  
              Reverse[CellularAutomaton[
                  110,  {1,  0,  0, 1,  1,  0,  1,  1,  1,  1,  
                    1,  0,  0,  0,  1,  0,  0,  1,   1,  0,  1,  
                    1,  1,  1,  1,  0,  0,  0,  1,  0,  0,  1,  
                    1,  0,  1,  1,  1,  1,  1, 0, 0,  0,  0,  1,  
                    0,  1,  1,  1,  1,  1,  0,  0,  0,  1,  0,  
                    0,  1,  1,  0,  1,  1,  1,  1,  1,  0,  0,  
                    0,  1,  0,  0,  1,  1,  0,  1,  1,  1,  1,  
                    1,  0,  0,  0,  1,   0,  0,  1,  1,  0,  1,  
                    1,  1,  1,  1,  1,  0,  0,  1,  1,  0,  1,  
                    0,  0,  0,  0,  1,  1,  0,  1,  1,  0,  0,  
                    1,  0,  1,  1,  0,  0,  1,  1,  0,  0,  1,  
                    0,  0,  1,   1,  0,  1,  1,  1,  1,  1,  0,  
                    0,  0,  1,  0,  0,  1,  1,  0,  1,  1,  1,  
                    1,  1, 0,  0,  0,  1,  0,  0,  1,  1,  0,  1,  
                    1,  1,  1,  1,  0,  0,  0},  
                  300]]]]];

Questions: