The Unreasonable Simplicity of Universal Machines

Rule 110 cellular automata, or more specifically the one dimensional cellular automata (you can explore those here http://atlas.wolfram.com/01/01/ ) that has the following rule:

current pattern 111 110 101 100 011 010 001 000 new state for center cell 0 1 1 0 1 1 1 0

is all the complexity that one needs to create a machine that has all the computational capability of a Turing Machine, hence any computer system.

NAND gates (or alternatively NOR gates):

INPUT OUTPUT A B A NAND B 0 0 1 0 1 1 1 0 1 1 1 0

is all the logic one needs to compose any boolean equation.

How does a Rule 110 automata differ from a NAND gate? The NAND gate has 4 rules, the automata has however 8 rules. If we look closely, we see that the Rule 110 automata contains all the rules of the NAND gate. Specifically, 010 -> 1, 011 0 ->, 110 -> 1 and 111 -> 1. In other words, if the center cell is set to 1, then Rule 110 acts just like a NAND gate. However, there are 14 other cellular automata that captures NAND logic but are not universal.

The cellular automata state of 0 for Rule 110 automata apparently has some additional capability that leads to universal behavior. Let’s examine these, for when the center cell is 0, the behavior becomes:

1 0 1 -> 1

1 0 0 -> 0

0 0 1 -> 1

0 0 0 -> 0

or if we ignore the center cell:

1 1 -> 1

1 0 -> 0

0 1 -> 1

0 0 -> 0

The middle two rules appear to break symmetry in that there’s a clear distinction as to which neighbor cell is on.

Let’s examine another automata, Rule 30 that is known to be chaotic:

current pattern 111 110 101 100 011 010 001 000 new state for center cell 0 0 0 1 1 1 1 0

For when the center cell is 0:

101 -> 0

100 -> 1

001 -> 1

000 -> 0

which is a XOR

and when the center cell is 1:

111 -> 0

110 -> 0

011 -> 1

010 -> 1

with that symmetry breaking that we see in Rule 110.

The complement of Rule 110 is Rule 137:

current pattern 111 110 101 100 011 010 001 000 new state for center cell 1 0 0 0 1 0 0 1

Which is the same as 110, but instead with a universal NOR gate.

111 -> 1

110 -> 0

011 -> 1

010 -> 0

Which is the same behavior as Rule 110 but with the center state now 1 instead of 0.

If we replace the rule for 111 and 010 to 111 -> 0 and 010 -> 0 we have

current pattern 111 110 101 100 011 010 001 000 new state for center cell 0 0 0 0 1 1 0 1

which is Rule 13 and not universal.

So its not just the symmetry breaking that’s important, but the fact that 11->1 and 00->0 are important. Note: Flipping the rule for 10 and 01 are also universal.

So, what perhaps is the significance of this circuitry…

1 0 1 -> 1

1 0 0 -> 0

0 0 1 -> 1

0 0 0 -> 0

that leads to universality?

What we see with these rules is that the value on the right neighbor cell becomes the center cell. The mirror rule 124 shifts from the left and the complement rule shifts also from the right. So to achieve a universal machine one just needs two rules. A NAND or NOR operator and a shift operator. The center cell determines which operator is active at the time. The simplest universal cellular automata has a computational element and a memory element.

Now that we have found the simplest machine possible, can we now attempt to identify the simplest machine that can learn? If we are able to do this, we can then show that a majority of systems in nature are in fact learning machines!

References:

A Concrete View of Rule 110 Computation https://arxiv.org/abs/0906.3248

Originally published at blog.alluviate.com.