# Notes

## 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[#, 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 + 35 n) t + 33 t2 steps of combinator evolution.

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