Each step in its evolution can be implemented using LifeStep[a_List] := MapThread[If[(#1  1 && #2  4) || #2  3, 1, 0]&, {a, Sum[RotateLeft[a, {i, j}], {i, -1, 1}, {j, -1, 1}]}, 2] A more efficient implementation can be obtained by operating not on a complete array of black and white cells but rather just on a list of positions of black cells.

And in this way the discrete system x  If[EvenQ[x], 3x/2, 3(x + 1)/2] from page 122 can be emulated by the continuous iterated map x  (3 + 6 x - 3 Cos[ π x])/4 . This approach can then be applied to the universal arithmetic system on page 673 , establishing that continuous iterated maps can in principle emulate discrete universal systems.

This list can then be updated using CCAEvolveStep[f_, list_List] := Map[f, (RotateLeft[list] + list + RotateRight[list])/3] CCAEvolveList[f_, init_List, t_Integer] := NestList[CCAEvolveStep[f, #] &, init, t] where for the rule on page 157 f is FractionalPart[3#/2] & while for the rule on page 158 it is FractionalPart[# + 1/4] & .

To give evidence that this is not merely a reflection of continual injection of randomness from the environment what is normally done is to show that at least some aspect of the behavior of the system can be fit by a definite simple iterated map or differential equation.

One feature of it, however, is that it maps the equation for quantum mechanical time evolution into the equation for probabilities in statistical mechanics, with imaginary time corresponding to inverse temperature.

One class of systems where some types of complexity were noticed in the 1950s are so-called iterated maps.

For any sequence s this can be done using Module[{c, m = 0}, Map[c[#] = {m, m += Count[s, #]/Length[s]} &, Union[s]]; Function[x, (First[RealDigits[2 # Ceiling[2 -# Min[x]], 2, -#, -1]] &)[Floor[Log[2, Max[x] - Min[x]]]]][ Fold[(Max[#1] - Min[#1]) c[#2] + Min[#1] &, {0, 1}, s]]] Huffman coding of a sequence containing a single 0 block together with n 1 blocks will yield output of length about n ; arithmetic coding will yield length about Log[n] .

Given a list of initial cell colors for the cellular automaton, the initial conditions for the mobile automaton are given by Flatten[{p[0], Map[p, list], p[0]}] surrounded by x 's, with the active cell being placed initially just before the first p[0] .

Implementation [of proof example] Given the axioms in the form s[1] = (a_ ⊼ a_) ⊼ (a_ ⊼ b_)  a; s[2, x_] := b_  (b ⊼ b) ⊼ (b ⊼ x); s[3] = a_ ⊼ (a_ ⊼ b_)  a ⊼ (b ⊼ b); s[4] = a_ ⊼ (b_ ⊼ b_)  a ⊼ (a ⊼ b); s[5] = a_ ⊼ (a_ ⊼ (b_ ⊼ c_))  b ⊼ (b ⊼ (a ⊼ c)); the proof shown here can be represented by {{s[2, b], {2}}, {s[4], {}}, {s[2, (b ⊼ b) ⊼ ((a ⊼ a) ⊼ (b ⊼ b))], {2, 2}}, {s[1], {2, 2, 1}}, {s[2, b ⊼ b], {2, 2, 2, 2, 2, 2}], {s[5], {2, 2, 2}}, {s[2, b ⊼ b], {2, 2, 2, 2, 2, 1}}, {s[1], {2, 2, 2, 2, 2}}, {s[3], {2, 2, 2}}, {s[1], {2, 2, 2, 2}}, {s[4], {2, 2, 2}}, {s[5], {}}, {s[2, a], {2, 2, 1}}, {s[1], {2, 2}}, {s[3], {}}, {s[1], {2}}} and applied using FoldList[Function[{u, v}, MapAt[Replace[#, v 〚 1 〛 ] &, u, {v 〚 2 〛 }]], a ⊼ b, proof]

Given the original list s and the complete prime implicant list p the so-called Quine–McCluskey procedure can be used to find a minimal list of prime implicants, and thus a minimal DNF: QM[s_, p_] := First[Sort[Map[p 〚 # 〛 &, h[{}, Range[Length[s]], Outer[MatchQ, s, p, 1]]]]] h[i_, r_, t_] := Flatten[Map[h[Join[i, r 〚 # 〛 ], Drop[r, #], Delete[Drop[t, {}, #], Position[t 〚 All, # 〛 ], {True}]]] &, First[Sort[Position[#, True] &, t]]]], 1] h[i_, _, {}] := {i} The number of steps required in this procedure can increase exponentially with the length of p .