Notes

Chapter 11: The Notion of Computation

Section 12: Universality in Turing Machines and Other Systems


Cellular automaton combinators

With k and s[k] representing respectively cell values 0 and 1, a combinator f for which f[a-1][a0][a1] gives the new value of a single cell in an elementary cellular automaton with rule number m can be constructed as

Apply[p[p[p[#1][#2]][p[#3][#4]]][ p[p[#5][#6]][p[#7][#8]]] /. {0 -> k, 1 -> s[k]} &, IntegerDigits[m, 2, 8]] //. crules

where

p = ToC[z[y][x], {x, y, z}] //. crules

The resulting combinator has size 61, but for specific rules somewhat smaller combinators can be found—an example for rule 90 is s[k[k]][s[s][k[s[s[s[k][k]][k[s[k]]]][k[k]]]]] with size 16.

To emulate cellular automaton evolution one starts by encoding a list of cell values by the single combinator

p[num[Length[list]]][ Fold[p[Nest[s, k, #2]][#1] &, p[k][k], list]] //. crules

where

num[n_] := Nest[inc, s[k], n] inc = s[s[k[s]][k]]

One can recover the original list by using

Extract[expr, Map[Reverse[IntegerDigits[#1, 2]] &, 3 + 59(16^Range[Depth[expr[s[k]][s][k] //. crules] - 1, 1, -1] - 1)/ 15)]]/. {k -> 0, s[k] -> 1}

In terms of the combinator f a single complete step of cellular automaton evolution can be represented by

w=cr[p[inc[inc[x[s[k]]]]][inc[x[s[k]]][ cr[p[y[s[k]][k]][p[y[s[k]][s[k]]][y[k]]], {y}]][ p[x[s[k]][ cr[p[ p[f[y[k][k][k][s[k]]][y[k][k][s[k]]][ y[k][s[k]]]][y[s[k]]]][y[k][k]], {y}]][p[p[k][k]][p[k][x[k]]]][s[k]]][ p[k][p[k][k]]]][k]], {x}] cr[expr_, vars_]:=ToC[expr//.crules, vars]

where there is padding with 0 on either side. With this setup t steps of evolution are given simply by Nest[w, init, t]. With an initial condition of n cells, this then takes roughly (100 + 35n)t + 33t^2 steps of combinator evolution.


From Stephen Wolfram: A New Kind of Science [citation]