One can characterize the symmetry of a pattern by taking the list v of positions of cells it contains, and looking at tensors of successive ranks n : Apply[Plus, Map[Apply[Outer[Times, ##] &, Table[#, {n}]] &, v]] For circular or spherical patterns that are perfectly isotropic in d dimensions these tensors must all be proportional to (d - 2)!!

Universal cellular automaton The rules for the universal cellular automaton are {{_, 3, 7, 18, _}  12, {_, 5, 7 | 8, 0, _}  12, {_, 3, 10, 18, _}  16, {_, 5, 10 | 11, 0, _}  16, {_, 5, 8, 18, _}  7, {_, 5, 14, 0 | 18, _}  12, {_, _, 8, 5, _}  7, {_, _, 14, 5, _}  12, {_, 5, 11, 18, _}  10, {_, 5, 17, 0 | 18, _}  16, {_, _, x : (11 | 17), 5, _}  x - 1, {_, 0 | 9 | 18, x : (7 | 10 | 16), 3, _}  x + 1, {_, 0 | 9 | 18, 12, 3, _}  14, {_, _, 0 | 9 | 18, 7 | 10 | 12 | 16, x : (3 | 5)}  8 - x, {_, _, _, 8 | 11 | 14 | 17, x : (3 | 5)}  8 - x, {_, 13, 4, _, x : (0 | 18)}  x, {18, _, 4, _, _}  18, {_, _, 18, _, 4}  18, {0, _,4, _, _}  0, {_, _, 0, _, 4}  0, {4, _, 0 | 18, 1, _}  3, {4, _, _, _, _}  4, {_, _, 4, _, _}  9, {_, 4, 12, _, _}  7, {_, 4, 16, _, _}  10, {x : (0 | 18), _, 6, _, _}  x, {_, 2, 6, 15, x : (0 | 18)}  x, {_, 12 | 16, 6, 7, _}  0, {_, 12 | 16, 6, 10, _}  18, {_, 9, 10, 6, _}  16, {_, 9, 7, 6, _}  12, {9, 15, 6, 7, 9}  0, {9, 15, 6, 10, 9}  18, {9, _, 6, _, _}  9, {_, 6, 7, 9, 12 | 16}  12, {_, 6, 10, 9, 12 | 16}  16, {12 | 16, 6, 7, 9, _}  12, {12 | 16, 6, 10, 9, _}  16, {6, 13, _, _, _}  9, {6, _, _, _, _}  6, {_, _, 9, 13, 3}  9, {_, 9, 13, 3, _}  15, {_, _, _, 15, 3}  3, {_, 3, 15, 0 | 18, _}  13, {_, 13, 3, _, 0 | 18}  6, {x : (0 | 18), 15, 9, _, _}  x, {_, 6, 13, _, _}  15, {_, 4, 15, _, _}  13, {_, _, _, 15, 6}  6, {_, _, 2, 6, 15}  1, {_, _, 1, 6, _}  2, {_, 1, 6, _, _}  9, {_, 3, 2, _, _}  1, {3, 2, _, _, _}  3, {_, _, 3, 2, _}  3, {_, 1, 9, 1, 6}  6, {_, _, 9, 1, 6}  4, {_, 4, 2, _, _}  1, {_, _, _, _, x : (3 | 5)}  x, {_, _, 3 | 5, _, x : (0 | 18)}  x, {_, _, x : (1 | 2 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17), _, _}  x, {_, _, 18, 7 | 10, 18}  18, {_, _, 0, 7 | 10, 0}  0, {_, _, 0 | 18, _, _}  9, {_, _, x_, _, _}  x} where the numbers correspond to the icons shown in the main text according to The block in the initial conditions for the universal cellular automaton corresponding to a cell with color a is given by Flatten[{Transpose[{Join[{4, 18(1 - a), 6}, Table[9, {2 2 r + 1 - 3}]], 10 - 3 rtab}], Table[{9, 1}, {r}], 9, 13}] where r is the range of the rule to be emulated ( r = 1 for elementary rules) and rtab is the list of outcomes for that rule (starting with the outcome for {1, 1, (1) ...} ).

In predicate logic the tab at the top specifies how to construct rules (which in this case are often called rules of inference, as discussed on page 1155 ). x_ ∧ y_  x_ is the modus ponens or detachment rule (see page 1155 ). x_  ∀ y_ x_ is the generalization rule. x_  x_ ∧ # & is applied to the axioms given to get a list of rules.

To set up the generalized diagonal argument one needs a way to list all possible programs.

In both cases it then turns out that h can be obtained from (see note above ) h[a_, b_] := FromDigits[g[ListConvolve[ IntegerDigits[a, k], IntegerDigits[b, k], {1, -1}, 0]], k] where for multiplication rules g = Identity and for additive cellular automata g = Mod[#, k] & .

Probably the simplest is a statement shown to be unprovable in Peano arithmetic by Laurence Kirby and Jeff Paris in 1982: that certain sequences g[n] defined by Reuben Goodstein in 1944 are of limited length for all n , where g[n_] := Map[First, NestWhileList[ {f[#] - 1, Last[#] + 1} &, {n, 3}, First[#] > 0 &]] f[{0, _}] = 0; f[{n_, k_}] := Apply[Plus, MapIndexed[#1 k^f[{#2 〚 1 〛 - 1, k}] &, Reverse[IntegerDigits[n, k - 1]]]] As in the pictures below, g[1] is {1, 0} , g[2] is {2, 2, 1, 0} and g[3] is {3, 3, 3, 2, 1, 0} . g[4] increases quadratically for a long time, with only element 3 × 2 402653211 - 2 finally being 0.

On the website associated with this book I plan to maintain a list of questions that I believe are of particular interest.

In addition to those with whom I have had direct contact, other individuals have provided input indirectly through my assistants or others (excluding photograph sources listed in the colophon): Bill Beyer, Sheila Blair, Victor Dan, Brent Daniel, Noam Elkies, Peter Falloon, Erich Friedman, Jochen Gerber, Branko Grünbaum, Richard Guy, Michel Janssen, Martin Kraus, Temur Kutsia, Richard Langley, Bernd Löchner, Crista Malick, Brendan McKay, Thomas Scanlon, Rob Scharein, Marjorie Senechal, Marc Sher, David Singmaster, Neil Sloane, Milton Van Dyke, Bob Veroff, Curtis Wilson, Mirek Wójtowicz.

With the development of lambda calculus in the early 1930s it became clear that given any expression expr such as x[y[x][z]] with a list of variables vars such as {x, y, z} one can always find a combinator equivalent to a lambda function such as Function[x, Function[y, Function[z, x[y[x][z]]]]] , and it turns out that this can be done simply using ToC[expr_, vars_] := Fold[rm, expr, Reverse[vars]] rm[v_, v_] = id rm[f_[v_], v_] /; FreeQ[f, v] = f rm[h_, v_] /; FreeQ[h, v] = k[h] rm[f_[g_], v_] := s[rm[f, v]][rm[g, v]] So this shows that any lambda function can in effect be written in terms of combinators, without anything analogous to variables ever explicitly having to be introduced.

Correspondence systems Given a list of pairs p with {u, v} = Transpose[p] the constraint to be satisfied is StringJoin[u 〚 s 〛 ]  StringJoin[v 〚 s 〛 ] Thus for example p = {{"ABB", "B"}, {"B", "BA"}, {"A", "B"}} has shortest solution s = {2, 3, 2, 2, 3, 2, 1, 1} .