Principle of Computational Equivalence [PCE]

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

Description:

The basic idea of this lesson is to summarize the behavior we have seen so far with ECAs.

After making some comparisons we will discuss the idea of the Principle of Computational Equivalence. The students can make conjectures about which rules are computationally equivalent.

Pre-requisites:

Objectives:

Materials

Computer

Further Notes:

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

Note:  By comparing patterns, conjecture which ones can emulate which others.

Background:

We have seen several rule systems.  The very simplest were the neighbor independent rules.  These were very predictable. Then we allowed the rules to have more stuff in them, and looked at those which depended on their right neighbor.  One of these was nested. Then we moved on to the elementary cellular automaton, and discovered that there were many different behaviors.  A few of them are computationally irreducible.  Some completely random, while others have some local structure.

The basic observation is that even simple rules can lead to very complex behavior.

The thing to notice is that there are rules which produce computations which are not easily predictable.  How do they compare in terms of their ability to emulate other rules? It is not easy to answer this question.

We also saw examples of one rule emulating another, and we discussed the phenomenon of universality.  Some rules can emulate other rules with more complicated descriptions.  Some of these rules have the computational power to emulate any other rule.  An example of such a universal rule is Rule 110. Some elementary cellular automata are quite simple, and we can always predict their future behavior.  So we know these can't be universal.  Because any rule emulated by a predictable rule must itself be predictable using the emulation.  But what about the others, the one's which give complex behavior? The Principle of Computational Equivalence says that these are also universal.  For now, it has not been proven to be true, but all the evidence suggests that that is the case.

We have seen the most common types of behaviors of the elementary cellular automata.  The cyclic and nested behaviors are predictable so they can't be universal.  The essentially random behavior of Rule 30, and the complicated behavior of Rule 110, are the other main types of behavior. The Principle of Computational Equivalence says that the other rules which show similar behavior are universal.  It gives us a way to think about complicated behavior.

Procedure:

Questions:

Assessment: