Symbolic Dissection of Cellular Automaton Rule Number 110

Dimitry Gashinsky (dig@barecode.com)

© 2004/04/21

Needs["NKSExplorer`"]
Needs["NKS`CellularAutomaton`"]

Universality

What does it mean to be universal?

A universal machine can simulate any effective process of symbol-manipulation, be it mathematical or anything else. (Marvin Minsky)

One of the positive statements in the theory of computation.

There are so many negative notions like undecidability, unsolvability of the halting problem and other constrains.

Cellular Automaton Rule 110 is universal

It is possible to do any computation using rule 110.

How can we exploit the simplicity of the rule 110?

Is it practical to build a rule 110 machine?

Space (nano scale)

Time (terahertz clock speeds)

Some facts about rule 110

Graphical representation

NKSDisplay[24.1, {110}, Heading -> False];

Algebraic form and Boolean expression

Mod[(1 + p) q r + q + r, 2]

¬ (p ∧ q ∧ r) ∧ (q ∨ 
          r)

Formulas 1 and 2 describe a successive cell in the evolution of CA 110 where p is the left neighbor of the cell in the previous step, q is the previous step cell and r is the right neighbor of the previous cell.

Persistent Structures in the 110 Evolution

Show[
        CARasterGraphics[
          CellularAutomaton[110, 
            SymbolsToCA110[{" "[7], "a"[0], " "[1], "b"[
                  0], " "[1], "c"[0], " "[1], "d"[0], " "[
                  2], "e"[0], " "[1], "f"[0], " "[1], "g"[
                  0], " "[1], "h"[0], " "[1], "i"[0], " "[
                  1], "j"[0], " "[1], "k"[0], " "[1], "l"[
                  0], " "[1], "m"[0], " "[1], "n"[0], " "[
                  1], "o"[0], " "[8]}], 200]]];

g,h,i are all extensions of the f
e is an extension of the d
a and o are rifts in the background

Background in Rule 110

Graphical representation

Show[
        CADensityGraphics[CellularAutomaton[110, CABackground[0], 7], 2, 
          30]];

Algebraic form

CABackground[0]

CABackground[0][[Mod[x+4 t,14]+1]]

Formula 3 describes the color of the cell on step t at the position x.

Single Structure up and close

Show[
        CADensityGraphics[
          CellularAutomaton[110, 
              SymbolsToCA110[{" "[2], "k"[0], " "[1]}], 
              30] //. {x___, Sequence @@ CABackground[0], y___} -> 
              Flatten[{x, Table[ .1, {14}], y}], 2, 8]];

Microscope view

From Symbols To Structures And Back

From symbols to the initial condition

SymbolsToCA110[{" "[5], "o"[0][2], " "[1], "a"[
          0], " "[5]}, 4]

Show[
        CARasterGraphics[{SymbolsToCA110[{" "[5], "o"[0][
                  2], " "[1], "a"[0], " "[5]}, 4]}, 2, 
          3]];

From step of evolution back to symbols

CA110ToSymbols[SymbolsToCA110[{" "[5], "a"[0], " "[5]}, 4], 
        0] // InputForm

More steps

Cases[
        CA110ToSymbols /@ 
          CellularAutomaton[110, 
            SymbolsToCA110[{" "[5], "a"[0], " "[1], "m"[
                  0], " "[1]}], 
            100], {___, "a"[_], ___, "m"[_], ___}, Infinity] // 
      MatrixForm

From Symbols To Graphics

All the dots

Show[
        CADensityGraphics[
          CellularAutomaton[110, 
            SymbolsToCA110[{" "[2], "o"[0], " "[2], "e"[
                  0], " "[1]}], 70, {All, All}]]];

Collapsing space

Center Paded and Scrubed

\(\(Show[
        CADensityGraphics[\(PadCenter[
                Flatten[
                  Replace[
                    CA110ToSymbols[#], {\((" " | 0 | 1)\)[num_] -> 
                        0, name_[_] :> 
                        ToCharacterCode[name]\/ToCharacterCode["p"]}, {1}]], 50] &\) /@ 
            CellularAutomaton[110, 
              SymbolsToCA110[{" "[2], "o"[0], " "[2], "e"[
                    0], " "[1]}], 70, {All, All}]]];\)\)

Right Paded

\(\(Show[
        CADensityGraphics[\(PadRight[
                Flatten[
                  Replace[
                    CA110ToSymbols[#], {\((" " | 0 | 1)\)[
                          num_] ->  .1, 
                      name_[_] :> 
                        ToCharacterCode[name]\/ToCharacterCode["p"]}, {1}]], 50] &\) /@ 
            CellularAutomaton[110, 
              SymbolsToCA110[{" "[2], "o"[0], " "[2], "e"[
                    0], " "[1]}], 70, {All, All}]]];\)\)

From Symbols To Graphics

Systematically smashing structures in full view

Show[
        GraphicsArray[
          Partition[
            Table[CARasterGraphics[
                CellularAutomaton[110, 
                  SymbolsToCA110[{" "[2], "o"[0], " "[
                        2], FromCharacterCode[target][0], " "[1]}], 
                  150, {All, All}]], {target, 97, 97 + 14}], 
            7]]];

Systematically smashing structures in collapsed view

Center Paded and Scrubed

Show[
        GraphicsArray[
          Partition[
            Table[CARasterGraphics[PadCenter[
                      Flatten[
                        Replace[
                          CA110ToSymbols[#], {(" " | 0 | 1)[
                                num_] -> 0, 
                            name_[_] :> 
                              ToCharacterCode[name]/
                                ToCharacterCode["o"]}, {1}]], 50] & /@ 
                  CellularAutomaton[110, 
                    SymbolsToCA110[{" "[2], "o"[0], " "[
                          2], FromCharacterCode[target][0], " "[1]}], 
                    150, {All, All}]], {target, 97, 97 + 14}], 
            7]]];

Right Paded

Show[
        GraphicsArray[
          Partition[
            Table[CARasterGraphics[PadRight[
                      Flatten[
                        Replace[
                          CA110ToSymbols[#], {(" " | 0 | 1)[
                                num_] ->  .1, 
                            name_[_] :> 
                              ToCharacterCode[name]/
                                ToCharacterCode["o"]}, {1}]], 50] & /@ 
                  CellularAutomaton[110, 
                    SymbolsToCA110[{" "[2], "o"[0], " "[
                          2], FromCharacterCode[target][0], " "[1]}], 
                    150, {All, All}]], {target, 97, 97 + 14}], 
            7]]];