Enumerating ECA Behaviors

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

Description:

In this lesson, we do a systematic survey of the elementary cellular automata by looking at their behavior from a single black cell. We will compare these evolutions to those we have seen already. Interesting cases will be singled out for future study (examples: Rule 30 and Rule 110).

Pre-requisites:

Objectives:

Materials:

Computer

Further Notes:

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

Note: When using simple rules, we see in this lesson that it is possible to include all of them in a survey. We can't view all possible evolutions. Instead, we observe the simplest cases. If we have time, we expand our search using random initial conditions. This "standard" is not as straight forward as it may seem. From a scientific point of view, we don't want to miss any interesting or relevant behavior. Only in special cases can we know a rule completely, as we will see in the next lesson. In a sense, this standard is about investigating the boundary between what is completely knowable and what can only be partially known. I am only trying to give a sense here of why this is not so simple, leading to philosophical issues like why things are the way they are, and whether anything in the natural world is knowable.

Note: In this lesson we survey the behaviors of the ECA, and we represent their evolutions in a graphical array.

Background:

In the last lesson we enumerated all of the elementary cellular automata.  This doesn't tell us what they do, but gives us a place to start in their study.

One approach would be to proceed systematically. Study the first ECA, Rule 0. Once satisfied that we know Rule 0 as much as we would like, we'd move on to Rule 1. And so on, until we had exhausted all of the possibilities.

Due to time constraints, we won't do that.  Instead, let's take the approach of looking at patterns which are new. Patterns for which we do not already have a descriptive formula.

We are going to proceed by looking at how each ECA behaves from the simplest initial condition, and comparing them. Since there are only 256, we can put their graphics into an array and look at them all at once.

We will see some patterns we saw before. Some patterns will seem immediately predictable, even though we haven't seen them before. Others will be completely new. We will make a list of the new ones, and later in the course we will investigate two of them in more detail.

Another thing to do with the array of graphics is to look at some general characteristics. For instance, the odd rules are easily distinguished from the even rules because the odd rules turn a white background into a black background.

Another characteristic is the shape the pattern makes. Some are symmetric. Some are triangular, with three basic types of triangles. Some defy such a simple description, and describing their shapes poses a challenging problem.

Procedure:

Questions: