Introduction to an Elementary Cellular Automaton: Rule 250

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

Description:

This lesson introduces an elementary cellular automaton (ECA).

These ECA's depending on both the left and right neighbors, so their descriptions are slightly more complicated than the rules from the previous lessons.

The possible behaviors are quite varied, as we will see in the later lessons.

Here we concentrate on a rule which makes an easily understood pattern, Rule 250.

Pre - requisites:

Objectives:

Materials:

Graph paper

Computer

Further Notes:

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

Note: Compare an evolution of just a few iterations with that of a very large number of iterations

Note: For use in conjecturing, proving the prediction for the bit at {x,t}, one needs to be able to think in terms of odd versus even.

Note: Function of black cells is generally piecewise linear, concave function. From a single black cell it is linear. Function for {x,t} is periodic in both x and t, within the pattern.

Note: various functions as above.

Note: Main thing is to predict the pattern of rule 250 from a single black cell. Advanced lesson would have them predict from more general starting conditions.

Note: Functions above should be apparent from data.

Note: To talk about the xth bit on row t.

Note: Attributes which don't correspond to numbers (not measurable) like the type of pattern. Some attributes are measurable like the number of black cells.

Note: Conjecture what happens with a single black cell. Conjecture general case. Investigate.

Note: Prove conjecture about the evolution from a single black cell.

Note: Discuss what goes into making the conjecture and various attempts to prove it.

Note: Above functions can be expressed precisely. General case is one line of Mathematica code.

Background:

So far we have seen rules whose behaviors can be analyzed completely, even though we have only analyzed a couple of them. In this lesson, we are going to learn about rules which have a great variety of behavior. In fact, some of these behave in such a way that we can never hope to completely understand them.

However, we will try to understand them as much as we can.

We started with rules which didn't depend on their neighbors, and then in our last lesson we looked at rules which depend on the right neighbor.  For the next type of rules, we could look at those that just depend on the left neighbor, but those are just the right-neighbor dependent ones in reverse.

So in this lesson, we look at rules which depend on both the right neighbor and the left neighbor. They are called elementary cellular automata. The singular is elementary cellular automaton. It might be simplest to just use the acronym ECA.

For now we will just concentrate our attention on a single example, Rule 250. Later, we will try to see what we can about the ECA as a group of rules, and other examples showing typical behaviors found among the ECA.

Procedure:

Evolution of Rule 250 with simplest initial condition:

As we have just observed, a CA consists of a line of cells each colored either black or white. "At every step there is then a definite rule that determines the color of a given cell from the color of that cell and its immediate left and right neighbors on the step before".(NKS p.24).

What is going to happen if we apply Rule 250 to a single black cell ? In other words, what is going to happen in that case that the starting or initial condition consists of a single black cell.

Repeated application of Rule 250 leads to an evolution of the CA.

The correct template is found by finding the neighborhood of three cells above the marked cell.

Additionally, let us take a closer look at Step or Row 1. The first row is given and represents the initial condition. Then the task is to fill in the succeeding steps one at a time.The color of a cell depends on the color of the three cells above it. In the following example we can determine the color of the yellow marked cell by reference to the color of the three cells above it. These crucial cells have been highlighted in red.

Refer back to the Rule 250 table to find out what the actual color of the yellow cell is ...

So the new updated cell is white !

Let us update the right neighbor of the black cell :

Again, refer back to the Rule 250 table to find out what the actual color of the yellow cell is ...

The color of the cell that we were seeking turns out to be black.

Unbounded Cellular Automata [[CA]]

The tricky part arises when we want to update the first cell of this grid - the one that we labeled with X.

We have stated that the color of a cell depends on the color of the three cells above it.

Let's take a look at our assumptions about the array ... we assume that we deal with an infinite array meaning the array extends at both ends indefinitely.

Since the array extends indefinitely into both directions we know that the cells at the end of the existing array will have a white neighbor and these neighbors will in turn have further neighbors ad infinitum ....

Additionally, 3 consecutive white neighbors yield a white cell on the next step, so all these cells will be white unless there is a nearby black cell. We shall stop when there is a black cell near the edge.

The pattern which seems to be the result continues.

This rule generates a pattern that repeatedly alternates between black and white. 
The shape gives rise to a checkerboard form.
It is a simple rule which exhibits simple behavior.

Questions:

Assessment:

Answer:

Illustrated answer:

Illustrated answer: