A nested example: Rule 90

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

Description:

This lesson introduces a rule which makes a nested pattern.

It is not periodic but it still has many regularities.

Importantly, we discuss the fact that the ECA exhibits sufficient regularity for its future evolution to be predicted.

Pre - requisites:

Objectives:

Materials:

Graph paper

Computers

Further Notes:

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

Note: The pattern is closely related to the powers of two.  Show nesting in the powers of two.

Note: Determine functions for black cells, as before with XoR (Rule 102).

Note: For conjecturing the bit value at {x,t}.

Note: Dilations by a factor of two show the nesting pattern.

Note: Successive dilations by two show the pattern approximate a fractal.

Note: Attempt to conjecture a rule that predicts the color at the xth bit on row t.

Background:

In this lesson we will look at another elementary cellular automaton, Rule 90.  Last time, we saw that Rule 250 makes either a checkerboard or a solid triangle pattern. Rule 90 instead makes what is called a nested pattern. We will see what that means.

In fact we may have seen a similar pattern before when looking at the boolean operators. The "exclusive or", otherwise known as as "Xor" makes a similar pattern as a right neighbor dependent rule. As an elementary cellular automaton that right neighbor dependent rule is Rule 102. We will make some comparisons between Rule 90 and Rule 102.

We say that Rule 90 from a single black cell emulates Rule 102 from a single black cell.  There are other examples of emulation which you should be able to notice. For instance some right neighbor dependent rules are like the neighbor independent rules except they also have shifting. There the emulation was more direct than the emulation of this nested pattern.

One feature of the pattern made from a single black cell with Rule 90 is that it looks similar from different scales. This feature will allow is to be able to make predictions about its future evolution.

Procedure:

90  =  
      0 * (2^0) +  1*(2^1) + 0*(2^2) + 1*(2^3) + 1*(2^4) + 0*(2^5) + 1*(2^6) + 
        0*(2^7)

Evolution of Rule 90 :

Starting with a single black cell and applying Rule 90 for one step .....

({{, , }, {, ,  }})

... applying Rule 90 a further steps ....

... evolved over a couple of more steps ...

This CA does not seem to repeat

This rule exhibits a very regular nested pattern

Questions:

A cell should be black whenever one or the other but not both of its neighbors were black on the step before.

Assessment: