Enumerating the Elementary Cellular Automata

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

Description:

This lesson introduces the enumeration of elementary cellular automata. It explains how rules get their numerical labels.

Pre-requisites:

Objectives:

Materials:

None

Further Notes:

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

Note: The main objective in this lesson is to use a counting technique to count the elementary cellular automaton. Also, the rule number labels are directly related to the counting technique, using numbers in base 2.

Note: Question whether we could have missed any ECA's, or whether we could have overcounted.

Background:

We saw that there were exactly unary functions.

The next case was slightly more complicated, but it was not too difficult to see thar there were sixteen boolean operators.

Let's investigate more carefully how we knew those figures were correct. In both cases we were able to list all the possibilities, and we could just count up to the total number. We might try counting the elementary cellular automata, but since there are so many we might make a mistake. We could by accident miss one, or count another more than once. While we might accidentally get the right answer, we shouldn't count on it. Also it would better to have a faster way.

In the case of neighbor independent rules, there were two possible cases to consider. The bit can be 0 or 1. A rule assigns to each of those independent cases one of two possibilities, 0 or 1. Two possibilities in two cases makes for (2^2)==4 rules.

We could have gotten confused here, because there are other ways to get four from two and two. Let's make sure we understand this by looking at the next case in more detail.

With right neighbor dependent rules, there are four cases. The bit and its right neighbor are either: white and white, white and black, black and white, black and black. The rule assigns a bit value to each of these cases independently. That makes two possibilities in four cases, or (2^4) == 16.

The first step in finding out how many elementary cellular automata there are is to find out how many cases there are. Then we raise 2 to that power to get the number of rules.

To get a numbering of the elementary cellular automata we follow the convention established by Stephen Wolfram in 1980.

Procedure:

For each of these different inputs one has one output; each output consists of 2 choices.

Assessment: