Surprisingly enough, this simple procedure, which can be represented by the function s[list_] := Flatten[ Transpose[Reverse[Partition[list, Length[list]/2]]]] with or without the Reverse , is able to produce orderings which at least in some respects seem quite random.

Cyclic tag systems which allow any value for each element can be obtained by adding the rule CTStep[{{r_, s___}, {n_, a___}}] := {{s, r}, Flatten[{a, Table[r, {n}]}]} The leading elements in this case can be obtained using CTListStep[{rules_, list_}] := {RotateLeft[rules, Length[list]], With[{n = Length[rules]}, Flatten[Apply[Table[#1, {#2}] &, Map[Transpose[ {rules, #}] &, Partition[list, n, n, 1, 0]], {2}]]]}

An example is the algorithm of Anatolii Karatsuba from 1961 for finding products of n -digit numbers (with n = 2 s ) by operating on their digits in the nested pattern of page 608 (see also page 1093 ) according to First[f[IntegerDigits[x, 2, n], IntegerDigits[y, 2, n], n/2]] f[x_, y_, n_] := If[n < 1, x y, g[Partition[x, n], Partition[y, n], n]] g[{x1_, x0_}, {y1_, y0_}, n_] := With[{z1 = f[x1, y1, n/2], z0 = f[x0, y0, n/2]}, z1 2 2n + (f[x0 + x1, y0 + y1, n/2] - z1 - z0)2 n + z0] Other examples include the fast Fourier transform (page 1074 ) and related algorithms for ListConvolve , the quicksort algorithm for Sort , and many algorithms in fields such as computational geometry.

The list representing the complete history of the resulting cyclic tag system can then be interpreted using Map[Map[Position[#, 1] 〚 1, 1 〛 - 1 &, Partition[#, k]] &, Take[history, {1, -1, n k}]] This construction is relevant to the proof of the universality of rule 110 starting on page 678 .

Indeed, the symbolic dynamics approach that is often used in dynamical systems theory is quite close to the digit sequence approach I use here—Markov partitions in dynamical systems theory are essentially just generalizations of digit expansions.

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).

Blocks in such sequences obtained from Partition[list, n, 1] must all be distinct since they correspond to successive complete states of the shift register.

In this case, the evolution can be obtained using SSEvolveList[rule_, init_String, t_Integer] := NestList[StringReplace[#, rule]&, init, t] For a neighbor-dependent substitution system such as the first one on page 85 the rule can be given as {{1, 1}  {0, 1}, {1, 0}  {1, 0}, {0, 1}  {0}, {0, 0}  {0, 1}} And with this representation, the evolution for t steps is given by SS2EvolveList[rule_, init_List, t_Integer] := NestList[Flatten[Partition[#, 2, 1] /. rule]&, init, t] where the initial condition for the first example on page 85 is {0, 1, 1, 0} .

Beyond randomness, the last example in the previous chapter was rule 110: a cellular automaton whose behavior becomes partitioned into a complex mixture of regular and irregular parts.

[Converting from CAs with] more colors Given a rule that involves three colors and nearest neighbors, the following converts each case of the rule to a collection of cases for a rule with two colors: CA3ToCA2[{a_, b_, c_}  d_] := Union[Flatten[Table[Thread[ Partition[Flatten[{l, a, b, c, r} /. coding], 11, 1] 〚 {2, 3, 4} 〛  (d /. coding)], {l, 0, 2}, {r, 0, 2}], 2]] coding = {0  {0, 0, 0}, 1  {0, 0, 1}, 2  {0, 1, 1}} The problem of encoding cells with several colors by blocks of black and white cells is related to standard problems in coding theory (see page 560 ).