Implementation [of patterning model] Given a 2D array of values a and a list of weights w , each step in the evolution of the system corresponds to WeightedStep[w_List, a_] := Map[If[# > 0, 1, 0]&, Sum[w 〚 1 + i 〛 Apply[Plus, Map[RotateLeft[a, #]&, Layer[i]]], {i, 0, Length[w] - 1}], {2}] Layer[n_] := Layer[n] = Select[Flatten[Table[{i, j}, {i, -n, n}, {j, -n, n}],1], MemberQ[#, n| - n]&]

Patterns produced by evolution according to a simple two-dimensional cellular automaton rule starting from rows of black cells of various lengths.

Huffman encoding with blocks of length 6 applied to patterns produced by cellular automata.

Thus, for example, with the rule {{1, 0}  {1, 1, -1}, {1, 1}  {2, 1, 1}, {2, 0}  {1, 0, -1}, {2, 1}  {1,0,1}} the head moves to the right whenever the initial condition consists of odd-length blocks of 1's separated by single 0's; otherwise it stays in a fixed region.

Non-deterministic Turing machines Generalizing rules from page 888 by making each right-hand side a list of possible outcomes, the list of configurations that can be reached after t steps is given by NTMEvolve[rule_, inits_, t_Integer] := Nest[ Union[Flatten[Map[NTMStep[rule, #]&, #], 1]]&, inits, t] NTMStep[rule_List, {s_, a_, n_}] /; 1 ≤ n ≤ Length[a] := Apply[{#1, ReplacePart[a, #2, n], n + #3}&, Replace[{s, a 〚 n 〛 }, rule], {1}]

The picture below shows the digit sequences of successive numbers in base -2; the row j from the bottom turns out to consist of alternating black and white blocks of length 2 j .

1D cellular automata In a cellular automaton with k colors and r neighbors, configurations that are left invariant after t steps of evolution according to the cellular automaton rule are exactly the ones which contain only those length 2r + 1 blocks in which the center cell is the same before and after the evolution.

If one ignores the first component of the spectrum the remainder is flat for a constant sequence, or for a random sequence in the limit of infinite length. It is also flat for maximal length LFSR sequences (see page 1084 ) and for sequences JacobiSymbol[Range[0, p - 1], p] with prime p (see page 870 ).

Arithmetic systems [emulating register machines] Given the program for a register machine with nr registers in the form on page 896 , an arithmetic system which emulates it can be obtained from RMToAS[prog_, nr_] := With[{p = Length[prog], g = Product[Prime[j], {j, nr}]}, {p g, Sort[Flatten[MapIndexed[ With[{n = First[#2] - 1}, #1 /. … If the register machine starts at instruction n with values regs in its registers, then the corresponding arithmetic system starts with the number n + Table[Prime[i]^reg 〚 i 〛 , {i, nr}] p - 1 where p = Length[prog] .

MemberQ[c, #], Append[c, #], AStep[c]]& [f[c] + f[{{1, 0}, {0, 1}, {-1, 0}, {0, -1}}]] f[a_]:=a 〚 Random[Integer, {1, Length[a]}] 〛 This implementation can easily be extended to any type of lattice and any number of dimensions. … With a grid of cells set up in advance, each step in this type of Eden model can be achieved with AStep[a_] := ReplacePart[a, 1, (# 〚 Random[ Integer, {1, Length[#]}] 〛 &)[Position[(1 - a)Sign[ ListConvolve[{{0, 1, 0}, {1, 0, 1}, {0, 1, 0}}, a, {2, 2}]], 1]]] This implementation can readily be extended to generalized aggregation models (see below ).