Introduction to Irreducibility: Rule 30

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

Description:

In this lesson we look at Rule 30, which shows complicated behavior even from the simplest starting conditions.

The pattern this rule produces is not predictable, and so it is called irreducible. Moreover, the pattern seems random.

We will investigate what is called intrinsic randomness using this example.

Pre-requisites:

Objectives:

Materials:

Computer

Further Notes:

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

Note: Looking at the data associated with Rule 30, one reasonable conclusion is that it is essentially random. This doesn't mean one can't try to make conjectures!

Note: By contrast. This case is more extreme than before with the other rules. Not only is the pattern something which is not measurable as a quantity, but there is no definite pattern at all.

Note: The center column is for all intents a random variable. Compute its expected value after 10 steps, 100 steps, etc..

Background:

In the last lesson we looked at an array of graphics with all of the elementary cellular automata, and saw many new patterns we haven't investigated yet. One of those is found in Rule 30, which makes a fairly complicated pattern.

Because the definitions of the ECA are all fairly simple, it would have been reasonable to hypothesize that all of their behaviors are predictable. With Rule 30, we are presented with an example where at first we might not be so sure that this is the case. Perhaps if we ran it for more steps a regular pattern will emerge. Maybe there is some way to convert the output into something meaningful.

We will try some of these approaches. To date, nobody has ever found a way to find any regularity in Rule 30 that allows one to make reliable predictions. Except of course, one can just run the cellular automaton. This is called computational irreducibility.

It is the opposite of what we have seen so far. With cyclic patterns, one can speed up the computation once one knows what happens within a single cycle. With nested patterns, one can speed up the computation through understanding the nesting, although it is a bit more tricky than the cyclic case. When one can speed up the computation, it is called computationally reducible. When one can't, it is called computationally irreducible.

There are some regularities with Rule 30, and we will investigate these during the lesson. But for those regions without regularities, it looks quite random. 

This type of randomness is called intrinsic randomness. Even though the output is the result of a deterministic rule, and even though the output can be computed step by step, the result is essentially random. 

What do we mean by random? This is a good question that can be discussed forever. In fact, there is no universally accepted definition. (That doesn't mean there is no point in discussing it.) One way to think about it is that a string is random if it has no properties.

Procedure:

Total /@ CellularAutomaton[30, {{1}, 0}, 53]

Flatten[CellularAutomaton[30, {{1}, 0}, 53, {All, {0, 0}}]]

Table[Random[Integer], {53}]

Flatten[CellularAutomaton[90, {{1}, 0}, 13, {All, {0, 0}}]]

Flatten[CellularAutomaton[90, {{1}, 0}, 13, {All, {1, 1}}]]

Flatten[CellularAutomaton[250, {{1}, 0}, 13, {All, {0, 0}}]]

Questions: