The positions of the black cells are given by (and this establishes the connection with the picture on page 117 ) Fold[Flatten[{#1 - #2, #1 + #2}] &, {0}, 2^DigitPositions[t]] DigitPositions[n_] := Flatten[Position[Reverse[IntegerDigits[n, 2]], 1]] - 1 The actual pattern generated by rule 90 corresponds to the coefficients in PolynomialMod[Expand[(1/x + x) t ], 2] (see page 1091 ); the color of a particular cell is thus given by Mod[Binomial[t, (n + t)/2], 2] /; EvenQ[n + t] .

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]&]

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}]

Neighbor-dependent [2D] substitution systems Given a list of individual replacement rules such as {{_, 1}, {0, 1}}  {{1, 0}, {1, 1}} , each step in the evolution shown corresponds to Flatten2D[Partition[list, {2, 2}, 1, -1] /. rule] One can consider rules in which some replacements lead to subdivision of elements but others do not.

Applying BitReverseOrder to this matrix yields a matrix which has an essentially nested form, and for size n = 2 s can be obtained from Nest[With[{c = BitReverseOrder[Range[0, Length[#] - 1]/ Length[#]]}, Flatten2D[MapIndexed[#1 {{1, 1}, {1, -1} (-1)^c 〚 Last[#2] 〛 } &, #, {2}]]] &, {{1}}, s] Using this structure, one obtains the so-called fast Fourier transform which operates in n Log[n] steps and is given by With[{n = Length[data]}, Fold[Flatten[Map[With[ {k = Length[#]/2}, {{1, 1}, {1, -1}} .

Starting with an ordinary base 2 digit sequence, one prepends a unary specification of its length, then a specification of that length specification, and so on: (Flatten[{Sign[-Range[1 - Length[#], 0]], #}] &)[ Map[Rest, IntegerDigits[Rest[Reverse[NestWhileList[ Floor[Log[2, #] &, n + 1, # > 1 &]]],2]]] (d) Binary-coded base 3. … Flatten[IntegerDigits[ Append[2 - With[{w = Floor[Log[3, 2n]]}, IntegerDigits[n - (3 w + 1 - 1)/2, 3, w]], 3], 2, 2]] (e) Fibonacci encoding.

One way to achieve this is to break the array into 2 n × 2 n blocks, then successively to fill in pixels in each block until the appropriate gray level is reached, as in the pictures below, in an order given for example by Nest[ Flatten2D[{{4 # + 0, 4 # + 2}, {4 # + 3, 4 # + 1}}] &, {{0}}, n] An alternative to this so-called ordered dither approach is the Floyd–Steinberg or error-diffusion method invented in 1976. … The method can be implemented using Module[{a = Flatten[data], r, s}, {r, s} = Dimensions[data]; Partition[Do[ a 〚 i + {1, s - 1, s, s + 1} 〛 += m (a 〚 i 〛 - If[a 〚 i 〛 < 1/2, 0, 1]), {i, r s - s - 1}]; Map[If[# < 1/2, 0, 1] &, a], s]] In its original version m = {7, 3, 5, 1}/16 , as in the first row of pictures below.

Multiway systems based on numbers One can consider for example the rule n  {n + 1, 2 n} implemented by NestList[Union[Flatten[{# + 1, 2 #}]] &, {0}, t] In this case there are Fibonacci[t + 2] distinct numbers obtained at step t .

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.

Junctional calculus Expressions are equivalent when Union[Level[expr, {-1}]] is the same, and this canonical form can be obtained from the axiom system of page 803 by flattening using (a ∘ b) ∘ c  a ∘ (b ∘ c) , sorting using a ∘ b  b ∘ a , and removing repeats using (a ∘ a)  a .