For much as on page 943 , one can imagine setting up a 1D cellular automaton with the property that, say, the absence of a particular color of cell throughout the 2D pattern formed by its evolution signifies satisfaction of the constraints. … And although it is somewhat more difficult to show, this question remains undecidable even if one allows any possible configuration of cells on the starting line.

Implementation [of operators from axioms] Given an axiom system in the form {f[a, f[a, a]]  a, f[a, b]  f[b, a]} one can find rule numbers for the operators f[x, y] with k values for each variable that are consistent with the axiom system by using Module[{c, v}, c = Apply[Function, {v = Union[Level[axioms, {-1}]], Apply[And, axioms]}]; Select[Range[0, k k 2 - 1], With[{u = IntegerDigits[#, k, k 2 ]}, Block[{f}, f[x_, y_] := u 〚 -1 - k x - y 〛 ; Array[c, Table[k, {Length[v]}], 0, And]]] &]] For k = 4 this involves checking nearly 16 4 or 4 billion cases, though many of these can often be avoided, for example by using analogs of the so-called Davis–Putnam rules. (In searching for an axiom system for a given operator it is in practice often convenient first to test whether each candidate axiom holds for the operator one wants.)

Simple examples in Mathematica include: First[Prepend[p, q]] === q Join[Join[p, q], r] === Join[p, Join[q, r]] Partition[Union[p], 1] === Split[Union[p]] One can set up axiom systems say by combining definitions of programming languages with predicate logic (as done by John McCarthy for Lisp in 1963). … But I suspect that enough computational irreducibility usually remains to make unprovability common when one asks about all possible forms of behavior of the program.

This constraint can then be represented in terms of a set of allowed templates; the set for rule 30 is as follows: To reproduce an ordinary picture of cellular automaton evolution, one would have to specify in advance a whole line of black and white cells. … If one specifies no cells in advance, or at most a few cells, as in the systems discussed in the main text, then the issue is different, however.

And if one looks at the center cell in the pattern one finds that it is never black on two successive steps, and the probability for white to follow white is about twice the probability for black to follow white.

Note that if one makes a hole in a shell, the pattern is usually quite unaffected, suggesting that the pattern is primarily a consequence of features of the underlying mantle. … It is not clear whether multiple kinds of shell patterns can occur within one species, or whether they are always associated with genetically different species.

One can also consider conservation of a vector quantity such as momentum which has not only a magnitude but also a direction. … One possibility is to use a hexagonal rather than square grid, thereby allowing six particle directions rather than four.

The expressions use the minimum possible number of operators; when there are several equivalent forms, I give the most uniform and symmetrical one.

Sources of repeatable randomness In using repeatability to test for intrinsic randomness generation, one must avoid systems in which there is essentially some kind of static randomness in the environment.

Multiway systems [and operator systems] One can use ideas from operator systems to work out equivalences in multiway systems (compare page 1169 ). One can think of concatenation of strings as being an operator, in terms of which a string like "ABB" can be written (a ∘ b) ∘ b . … Taking ∘ to be each of these operators, one can work out a representation for any given string like "ABAA" by for example constructing the expression ((a ∘ b) ∘ a) ∘ a and finding its value for each of the k 2 possible pairs of values of a and b .