The value of each cell can be any gray level between 0 and 1. For the generalization of rule 90, the values of the left and right cells are added together, and the value of the cell on the next step is then found by applying the continuous generalization of the modulo 2 function shown at the right.

Diophantine equations Any algebraic equation—such as x 3 + x + 1  0 —can readily be solved if one allows the variables to have any numerical value. … And in fact, even though such so-called Diophantine equations have been studied since well before the time of Diophantus around perhaps 250 AD, only limited results about them are known. … (The equation (2x + 1) y  z also for example has solutions only when z is not of the form 2 j .)

Non-power bases One can consider representing numbers by Sum[a[n] f[n], {n, 0, ∞ }] where the f[n] need not be k n . So long as f[n] grows less rapidly than 2 n (as when f = Fibonacci or f = Prime ), digits 0 and 1 will suffice, though the representation is not generally unique.

Cellular automaton combinators With k and s[k] representing respectively cell values 0 and 1 , a combinator f for which f[a -1 ][a 0 ][a 1 ] gives the new value of a single cell in an elementary cellular automaton with rule number m can be constructed as Apply[p[p[p[#1][#2]][p[#3][#4]]][p[p[#5][#6]][p[#7][ #8]]] /. {0  k, 1  s[k]} &, IntegerDigits[m, 2, 8]] //. crules where p = ToC[z[y][x], {x, y, z}] //. crules The resulting combinator has size 61, but for specific rules somewhat smaller combinators can be found—an example for rule 90 is s[k[k]][s[s][k[s[s[s[k][k]][k[s[k]]]][k[k]]]]] with size 16. To emulate cellular automaton evolution one starts by encoding a list of cell values by the single combinator p[num[Length[list]]][ Fold[p[Nest[s, k, #2]][#1] &, p[k][k], list]] //. crules where num[n_] := Nest[inc, s[k], n] inc = s[s[k[s]][k]] One can recover the original list by using Extract[expr, Map[Reverse[IntegerDigits[#, 2]] &, 3 + 59(16^Range[Depth[expr[s[k]][s][k] //. crules] - 1, 1, -1] - 1)/ 15)]]/. … With an initial condition of n cells, this then takes roughly (100 + 35 n) t + 33 t 2 steps of combinator evolution.

Sequential substitution systems [from cellular automata] Given a sequential substitution system with rules in the form used on page 893 , the rules for a cellular automaton which emulates it can be obtained from SSSToCA[rules_] := Flatten[{{v[_, _, _], u, _}  u, {_, v[rn_, x_, _], u}  r[rn + 1, x], {_, v[_, x_, _], _}  x, MapIndexed[ With[{r n = #2 〚 1 〛 , rs = #1 〚 1 〛 , rr = #1 〚 2 〛 }, {If[Length[rs]  1, {u, r[rn, First[rs]], _}  q[0, rr], {u, r[rn, First[rs]], _}  v[rn, First[rs], Take[rs, 1]]], {u, r[rn, x_], _}  v[rn, x, {}], {v[rn, _, Drop[rs, -1]], Last[rs], _}  q[Length[rs] - 1, rr], Table[{v[rn, _, Flatten[{___, Take[rs, i - 1]}]], rs 〚 i 〛 , _}  v[ rn, rs 〚 i 〛 , Take[rs, i]], {i, Length[rs] - 1, 1, -1}], {v[rn, _, _], y_, _}  v[rn, y, {}]}] & , rules /. s  List], {_, q[0, {x__, _}], _}  q[0, {x}], {_, q[0, {x_}], _}  r[1, x], {_, q[0, {}], x_}  r[1, x], {_, q[_, {___, x_}], _}  x, {_, q[_, {}], x_}  x, {_, x_, q[0, _]}  x, {_, _, q[n_, {}]}  q[n - 1, {}], {_, _, q[n_, {x___, _}]}  q[n - 1, {x}], {q[_, {}], _, _}  w, {q[0, {__, x_}], p[y_, _], _}  p[x, y], {q[0, {__, x_}], y_, _}  p[x, y], {p[_, x_], p[y_, _], _}  p[x, y], {p[_, x_], u, _}  x, {p[_, x_], y_, _}  p[x, y], {_, p[x_, _], _}  x, {w, u, _}  u, {w, x_, _}  w, {_, w, x_}  x, {_, r[rn_, x_], _}  x, {_, u, r[_, _]}  u, {_, x_, r[rn_, _]}  r[rn, x], {_, x_, _}  x}] The initial condition is obtained by applying the rule s[x_, y__]  {r[1, x], y} and then padding with u 's.

The sequence of odd numbers gives the continued fraction for Coth[1] ; the sequence of even numbers for BesselI[0, 1]/BesselI[1, 1] . … As discovered by Jeffrey Shallit in 1979, numbers of the form Sum[1/k 2 i , {i, 0, ∞ }] that have nonzero digits in base k only at positions 2 i turn out to have continued fractions with terms of limited size, and with a nested structure that can be found using a substitution system according to {0, k - 1, k + 2, k, k, k - 2, k, k + 2, k - 2, k} 〚 Nest[Flatten[{{1, 2}, {3, 4}, {5, 6}, {7, 8}, {5, 6}, {3, 4}, {9, 10}, {7, 8}, {9, 10}, {3, 4}} 〚 # 〛 ]&, 1, n] 〛 The continued fractions for square roots are always periodic; for higher roots they never appear to show any significant regularities. … For any irrational number this quantity cannot be less than 2, while for algebraic irrationals Klaus Roth showed in 1955 that it can only have finitely many peaks that reach above any specified level.

Claude Shannon showed in 1956 that 2 colors were sufficient so long as enough states were used. (See page 669 ; conversion of Minsky 's machine using this method yields a {43, 2} machine.) … In the 1980s and 1990s, however, Yurii Rogozhin found examples of universal Turing machines for which the number of states and number of colors were: {24, 2} , {10, 3} , {7, 4} , {5, 5} , {4, 6} , {3, 10} , and {2, 18} .

The program for the register machine on page 99 can then be given as {i[1], d[2, 1], i[2], d[1, 3], d[2, 1]} where i[_] represents an increment instruction, and d[_, _] a decrement jump. With this setup, the evolution of any register machine can be implemented using the functions (a typical initial condition is {1, {0, 0}} ) RMStep[prog_, {n_Integer, list_List}] := If[n > Length[prog], {n, list}, RMExecute[prog 〚 n 〛 , {n, list}]] RMExecute[i[r_], {n_, list_}] := {n + 1, MapAt[(# + 1)&, list, r]} RMExecute[d[r_, m_], {n_, list_}] := If[list 〚 r 〛 > 0, {m, MapAt[(# - 1)&, list, r]}, {n + 1, list}] RMEvolveList[prog_, init:{_Integer, _List}, t_Integer] := NestList[RMStep[prog, #]&, init, t] The total number of possible programs of length n using k registers is (k (1 + n)) n .

Structures [in rule 110] The persistent structures shown can be obtained from the following {n, w} by inserting the sequences IntegerDigits[n, 2, w] between repetitions of the background block b : {{152, 8}, {183, 8}, {18472955, 25}, {732, 10}, {129643, 18}, {0, 5}, {152, 13}, {39672, 21}, {619, 15}, {44, 7}, {334900605644, 39}, {8440, 15}, {248, 9}, {760, 11}, {38, 6}} The repetition periods and distances moved in each period for the structures are respectively {{4, -2}, {12, -6}, {12, -6}, {42, -14}, {42, -14}, {15, -4}, {15, -4}, {15, -4}, {15, -4}, {30, -8}, {92, -18}, {36, -4}, {7, 0}, {10, 2}, {3, 2}} Note that the periodicity of the background forces all rule 110 structures to have periods and distances given by {4, -2} r + {3, 2} s where r and s are non-negative integers. … Extended versions of (b) and (c) can be obtained from Flatten[{IntegerDigits[1468, 2], Table[ IntegerDigits[102524348, 2], {n}], IntegerDigits[v, 2]}] where n is a non-negative integer and v is one of {1784, 801016, 410097400, 13304, 6406392, 3280778648} Note that in most cases multiple copies of the same structure can travel next to each other, as seen on page 290 .

The vertical distance moved at the n th horizontal position is Floor[n h] - Floor[(n - 1) h] , and the sequence obtained from this (which contains only terms Floor[h] and Floor[h] + 1 ) provides a unique representation for h . … Given a sequence of length n , an approximation to h can be reconstructed using Max[MapIndexed[#1/First[#2] &, FoldList[Plus, First[list], Rest[list]]]] The fractional part of the result obtained is always an element of the Farey sequence Union[Flatten[Table[a/b, {b, n}, {a, 0, b}]]] (See also pages 892 , 932 and 1084 .)