Turing machines [from cellular automata] Given any Turing machine with rules in the form used on page 888 and k possible colors for each cell, a cellular automaton which emulates it can be constructed using TMToCA[rules_, k_:2] := Flatten[{Map[g[#, k]&, rules], {_, x_, _}  x}] g[{s_, a_}  {sp_, ap_, d_}, k_] := {If[d  1, Identity, Reverse][{k s + a, x_, _}]  k sp + x, {_, k s + a, _}  ap} If the Turing machine has s states for its head, then the cellular automaton has k (s+1) colors for each cell.

Equivalential calculus Expressions with variables vars are equivalent if they give the same results for Mod[Map[Count[expr, #, {-1}] &, vars], 2] With n variables, there are thus 2 n equivalence classes of expressions (compared to 2 2 n for ordinary logic).

Complex maps Many kinds of nonlinear transformations on complex numbers yield nested patterns.

Second-order cellular automata Second-order elementary rules can be implemented using CA2EvolveList[rule_List, {a_List, b_List}, t_Integer] := Map[First, NestList[CA2Step[rule, #]&, {a, b}, t]] CA2Step[rule_List, {a_, b_}] := {b, Mod[a + rule 〚 8 - (RotateLeft[b] + 2 (b + 2 RotateRight[b])) 〛 , 2]} where rule is obtained from the rule number using IntegerDigits[n, 2, 8] .

MapIndexed[ #1  First[#2] &, Union[Map[# 〚 1, 1 〛 &, #]]] &[ With[{b = Ceiling[Log[2, k]] - 1}, Flatten[Table[ {Table[{Table[{{m, i, n, d}, c}  {{m, Mod[i, 2 n - 1 ], n - 1, d}, Quotient[i, 2 n - 1 ], 1}, {n, 2, b}, {i, 0, 2 n - 1}], Table[{ {m, i, 1, d}, c}  {{m, -1, 1, d}, i, d}, {i, 0, 1}], Table[ {{m, -1, n, d}, c}  {{m, -1, n + 1, d}, c, d}, {n, b - 1}], {{m, -1, b, d}, c}  {{0, 0, m}, c, d}}, {d, -1, 1, 2}], Table[{{i, n, m}, c}  {{ i + 2 n c, n + 1, m}, c, -1}, {n, 0, b - 1}, {i, 0, 2 n - 1}], With[{r = 2 b }, Table[ If[i + r c ≥ k, {}, Cases[rule, ({m, i + r c}  {x_, y_, z_})  {{i, b, m}, c}  {{x, Mod[y, r], b, z}, Quotient[y, r], 1})]], {i, 0, r - 1}]]}, {m, s}, {c, 0, 1}]]]] Some of these states are usually unnecessary, and in the main text such states have been pruned.

In the 1980s, particularly following discoveries in iterated maps and quasicrystals, studies of such spectra were made in the context of number theory and dynamical systems theory. … With k colors each giving a string of the same length s the recurrence relation is Thread[Map[ ϕ [#][t + 1, ω ] &, Range[k] - 1]  Apply[Plus, MapIndexed[Exp[  ω (Last[#2] - 1) s t ] ϕ [#1][t, ω ] &, Range[k] - 1 /. rules, {-1}], {1}]/ √ s ] Some specific properties of the examples shown include: (a) (Thue–Morse sequence) The spectrum is essentially Nest[Range[2 Length[#]] Join[#, Reverse[#]] &, {1}, t] .

In case (c), the following gives a list of the numbers of nodes generated up to step t : FoldList[Plus, 1, Join[{1, 4, 12, 10, -20, 6, 4}, Map[d, IntegerDigits[Range[4, t - 5], 2]]]] d[{___, 1}] = 1 d[{1, p : 0 .., 0}] := -Apply[Plus, 4 Range[Length[{p}]] - 1] + 6 d[{__, 1, p : 0 .., 0}] := d[{1, p, 0}] - 7 d[{___, p : 1 .., q : 0 ..., 1, 0}] := 4 Length[{p}] + 3 Length[{q}] + 2 d[{___, p : 1 .., 1, 0}] := 4 Length[{p}] + 2

The transitions between these states have probabilities given by m[Map[Length, list]] where m[s_] := With[{q = FoldList[Plus, 0, s]}, ReplacePart[ RotateRight[IdentityMatrix[Last[q]], {0, 1}], 1/Length[s], Flatten[Outer[List, Rest[q], Drop[q, -1] + 1], 1]]] The average spectrum of sequences generated according to these probabilities can be obtained by computing the correlation function for elements a distance r apart ξ [list_, r_] := With[{w = (# - Apply[Plus, #]/Length[#] &)[ Flatten[list]]}, w . MatrixPower[ m[Map[Length, list]], r] . w/Length[w]] then forming Sum[ ξ [Abs[r]] Cos[2 π r ω ], {r, -n/2, n/2}] and taking the limit n  ∞ .

Iterated run-length encoding Starting say with {1} consider repeatedly replacing list by (see page 1070 ) Flatten[Map[{Length[#], First[#]} &, Split[list]]] The resulting sequences contain only the numbers 1, 2 and 3, but otherwise at first appear fairly random.

A recurrence relation like f[0] = x; f[n_] := a f[n - 1] (1 - f[n - 1]) corresponds to an iterated map of the kind discussed on page 920 , and has complicated behavior for many rational x .