The key idea is to represent data of any kind by a symbolic expression of the general form head[arg 1 , arg 2 , …] . ( a + b 2 is thus Plus[a, Power[b, 2]] , {a, b, c} is List[a, b, c] and a = b + 1 is Set[a, Plus[b, 1]] .)

However, as was shown in the 1800s, this method can yield only numbers formed by operating on rationals with combinations of Plus , Times and Sqrt . (Thus it is impossible with ruler and compass to construct π and "square the circle" but it is possible to construct 17-gons or other n -gons for which FunctionExpand[Sin[ π /n]] contains only Plus , Times and Sqrt .) … Note that above degree 4, algebraic numbers cannot in general be expressed in radicals involving only Plus , Times and Power (see page 945 ).

In case (c), the following gives a list of the numbers of nodes generated up to step t : FoldList[Plus, 1, Join[{1, 4, 12, 10, -20, 6, 4}, Map[d, IntegerDigits[Range[4, t - 5], 2]]]] d[{___, 1}] = 1 d[{1, p : 0 .., 0}] := -Apply[Plus, 4 Range[Length[{p}]] - 1] + 6 d[{__, 1, p : 0 .., 0}] := d[{1, p, 0}] - 7 d[{___, p : 1 .., q : 0 ..., 1, 0}] := 4 Length[{p}] + 3 Length[{q}] + 2 d[{___, p : 1 .., 1, 0}] := 4 Length[{p}] + 2

But in the so-called lambda calculus of Alonzo Church from around 1930 what were instead used were pure functions such as s = Function[x, x + 1] and plus = Function[{x, y}, If[x  0, y, s[plus[x - 1, y]]]] —of just the kind now familiar from Mathematica.

[Turing] machine 596440 For any list of initial colors init , it turns out that successive rows in the first t steps of the compressed evolution pattern turn out to be given by NestList[Join[{0}, Mod[1 + Rest[FoldList[Plus, 0, #]], 2], {{0}, {1, 1, 0}} 〚 Mod[Apply[Plus, #], 2] + 1] 〛 &, init, t] Inside the right-hand part of this pattern the cell values can then be obtained from an upside-down version of the rule 60 additive cellular automaton, and starting from a sequence of 1 's the picture below shows that a typical rule 60 nested pattern can be produced, at least in a limited region.

Applying FoldList[Plus, 0, 2list - 1] to the whole sequence yields the pattern shown below. … This is similar to picture (c) on page 131 , and is a digit-by-digit version of FoldList[Plus, 0, Table[Apply[Plus, 2 Rest[IntegerDigits[i, 2]] - 1], {i, n}]] Note that although the picture above has a nested structure, the original concatenation sequences are not nested, and so cannot be generated by substitution systems.

The number of states with spatial period m is given by s[m_, k_]:= k m - Apply[Plus, Map[s[#, k] &, Drop[Divisors[m], -1]]] or equivalently s[m_, k_]:=Apply[Plus, (MoebiusMu[m/#] k # &)[Divisors[m]]] In a cellular automaton with a total of n cells, the maximum possible repetition period is thus s[n, k] .

The functions And , Xor and Not are equivalent to Times , Plus and 1 - # & for variables modulo 2, and in this case algebraic functions like PolynomialReduce can be used for minimization.

Digit count sequences Starting say with {1} repeatedly replace list by Join[list, IntegerDigits[Apply[Plus, list], 2]] The resulting sequences grow in length roughly like n Log[n] .

This yields a chord such as Play[Evaluate[Apply[Plus, Flatten[Map[Sin[1000 # t] &, N[2 1/12 ]^Position[list, 1]]]]], {t, 0, 0.2}] A sequence of such chords can sometimes provide a useful representation of cellular automaton evolution.