Different runs [of initially random cellular automata] The qualitative behavior seen with a given cellular automaton rule will normally look exactly the same for essentially all different large random initial conditions—just as it does for different parts of a single initial condition.

User interface and operating system programs are not normally intended to halt in an explicit sense, although without external input they often reach states that do not change. Mathematica works by taking its input and repeatedly applying transformation rules—a process which normally reaches a fixed point that is returned as the answer, but with definitions like x = x + 1 ( x having no value) formally does not.

Inevitably, however, I do discuss computers, even though I fully expect that some of the terms and concepts I use in connection with them will end up seeming dated in a matter of a few decades.

Sorting networks Any list can be sorted using Fold[PairSort, list, pairs] by doing a fixed sequence of comparisons of pairs PairSort[a_, p : {_, _}] := Block[{t = a}, t 〚 p 〛 = Sort[t 〚 p 〛 ]; t] (Different comparisons often do not interfere and so can be done in parallel.) … (Quicksort does not use a fixed sequence of comparisons.)

(Note that if an axiom system does manage to reproduce logic in full then as indicated on page 814 its consequences can always be derived by proofs of limited length, if nothing else by using truth tables.) … (Note that even if it works for all finite k this does not establish its validity.) Another way to do this is to look for invariants that should not be present—seeing if there are features that differ between equivalent expressions, yet are always left the same by transformations in the axiom system.

One can also do this—as in the rule 110 proof in the previous chapter—by having programs and data be encoded separately, and appear, say, as distinct parts of the initial conditions for the system one is studying.

Doing this for the combinator system from page 711 yields the so-called combinatory algebra {((s ∘ a) ∘ b) ∘ c  (a ∘ c) ∘ (b ∘ c), (  ∘ a) ∘ b  a} .

The lack of regularity in this picture can be viewed as a sign that it is difficult to tell which theorems hold, and thus in effect to do mathematics.

For rule 45, the maximum possible period discussed above is achieved for n = 9 , but does not appear to be achieved for any larger n .

In any case, knowing a complete and ultimate model does make it impossible to have miracles or divine interventions that come from outside the laws of the universe—though working out what will happen on the basis of these laws may nevertheless be irreducibly difficult.