The formulas we have used so far can be thought of as always consisting of sums of products of variables.

Rational numbers require only division (or solving linear equations), while algebraic numbers require solving polynomial equations. … For rational functions f[x] , Integrate[f[x], {x, 0, 1}] must always be a linear function of Log and ArcTan applied to algebraic numbers ( f[x] = 1/(1 + x 2 ) for example yields π /4 ). Multiple integrals of rational functions can be more complicated, as in Integrate[1/(1 + x 2 + y 2 ), {x, 0, 1}, {y, 0, 1}]  HypergeometricPFQ[{1/2, 1, 1}, {3/2, 3/2}, 1/9]/6 + 1/2 π ArcSinh[1] - Catalan and presumably often cannot be expressed at all in terms of standard mathematical functions.

Successive powers of 3/2, shown in base 2. Multiplication by 3/2 can be thought of as multiplication by 3 combined with division by 2. But division by 2 just does the opposite of multiplication by 2, so in base 2 it simply shifts all digits one position to the right.

[Generating sequences with] unequal probabilities Given a sequence a of n equally probable 0's and 1's, the following generates a single 0 or 1 with probabilities approximating {1 - p, p} to n digits: Fold[({BitAnd, BitOr} 〚 1 + First[#2] 〛 [#1, Last[#2]]) &, 0, Reverse[Transpose[{First[RealDigits[p, 2, n, -1]], a}]]] This can be generalized to allow a whole sequence to be generated with as little as an average of two input digits being used for each output digit.

Finding layouts [for networks] One way to lay out a network g so that network distances in it come as close as possible to ordinary distances in d -dimensional space, is just to search for values of the x[i, k] which minimize a quantity such as With[{n = Length[g]}, Apply[Plus, Flatten[(Table[Distance[g, {i, j}], {i, n}, {j, n}] 2 - Table[ Sum[(x[i, k] - x[j, k]) 2 , {k, d}], {i, n}, {j, n}]) 2 ]]] using for example FindMinimum starting say with x[1, _]  0 and all the other x[_, _]  Random[] . … It turns out that this is almost always possible even in 2D (though not in 1D); the only exception is the tetrahedron network. … (In 3D, for example, this is true only for the tetrahedron.)

For example, rule 90 on page 25 corresponds to f[1, _, 1] = 0; f[0, _, 1] = 1; f[1, _, 0] =1; f[0, _, 0] = 0 One can specify initial conditions for example by a[0, 0] = 1; a[0, _] = 0 (the cell on step 0 at position 0 has value 1, but all other cells on that step have value 0). … But it is also possible to define this function in an algebraic way f[p_, q_, r_] := Mod[p + r, 2] Algebraic definitions can also be given for other rules: • Rule 254 (page 24 ): 1 - (1 - p)(1 - q)(1 - r) • Rule 250 (page 25 ): p + r - p r • Rule 30 (page 27 ): Mod[p + q + r + q r, 2] • Rule 110 (page 32 ): Mod[(1 + p) q r + q + r, 2] In these definitions, we represent the values of cells by the numbers 1 or 0. … And in this case cellular automaton rules become logic expressions: • Rule 254: Or[p, q, r] • Rule 250: Or[p, r] • Rule 90: Xor[p, r] • Rule 30: Xor[p, Or[q, r]] • Rule 110: Xor[Or[p, q], And[p, q, r]] (Note that Not[p] corresponds to 1 - p , And[p, q] to p q , Xor[p, q] to Mod[p + q, 2] and Or[p, q] to Mod[p q + p + q, 2] .)

Numbering scheme [for Turing machines] One can number Turing machines and get their rules using Flatten[MapIndexed[{1, -1} #2 + {0, k}  {1, 1, 2} Mod[Quotient[#1, {2k, 2, 1}], {s, k, 2}] + {1, 0, -1} &, Partition[IntegerDigits[n, 2 s k, s k], k], {2}]] The examples on page 79 have numbers 3024, 982, 925, 1971, 2506 and 1953.

Huffman coding From a list p of probabilities for blocks, the list of codewords can be generated using Map[Drop[Last[#], -1] &, Sort[ Flatten[MapIndexed[Rule, FixedPoint[Replace[Sort[#], {{p0_, i0_}, {p1_, i1_}, pi___}  {{p0 + p1, {i0, i1}}, pi}] & , MapIndexed[List, p]] 〚 1, 2 〛 , {-1}]]]] -1 Given the list of codewords c , the sequence of blocks that occur in encoded data d can be uniquely reconstructed using First[{{}, d} //. MapIndexed[ {{r___}, Flatten[{#1, s___}]}  {{r,#2 〚 1 〛 },{s}} &, c]] Note that the encoded data can consist of any sequence of 0's and 1's. … In an opposite extreme, blocks with probabilities 1/2, 1/4, 1/8, ... will yield codewords of lengths 1, 2, 3, ...

For case (b) on pages 83 and 84 , the rule that gives the color of the next branch in terms of the color of the current branch and the next digit is {{0, 0}  0, {0, 1}  1, {1, 0}  1, {1, 1}  0} . … In base k a number is constructed from a digit sequence a[r] , … , a[1] , a[0] (with 0 ≤ a[i] < k ) according to Sum[a[i] k i , {i, 0, r}] . But given a sequence of digits that are each 0 or 1, it is also possible for example to construct numbers according to Sum[a[i] Fibonacci[i + 2], {i, 0, r}] .

Then, for example, the rule for the Turing machine shown on page 78 can be given as {{1, 0}  {3, 1, -1}, {1, 1}  {2, 0, 1}, {2, 0}  {1, 1, 1}, {2, 1}  {3, 1, 1}, {3, 0}  {2, 1, 1}, {3, 1}  {1, 0, -1}} where the left-hand side in each case gives the state of the head and the value of the cell under the head, and the right-hand side consists of a triple giving the new state of the head, the new value of the cell under the head and the displacement of the head. With a rule given in this form, a single step in the evolution of the Turing machine can be implemented with the function TMStep[rule_List, {s_, a_List, n_}] /; (1 ≤ n ≤ Length[a]) := Apply[{#1, ReplacePart[a, #2, n], n + #3}&, Replace[{s, a 〚 n 〛 }, rule]] The evolution for many steps can then be obtained using TMEvolveList[rule_, init_List, t_Integer] := NestList[TMStep[rule, #]&, init, t] An alternative approach is to represent the complete state of the Turing machine by MapAt[{s, #}&, list, n] , and then to use TMStep[rule_, c_] := Replace[c, {a___, x_, h_List, y_, b___}  Apply[{{a, x, #2, {#1, y}, b}, {a, {#1, x}, #2, y, b}} 〚 #3 〛 &, h /. rule]] The result of t steps of evolution from a blank tape can also be obtained from (see also page 1143 ) s = 1; a[_] = 0; n = 0; Do[{s, a[n], d} = {s, a[n]} /. rule; n += d, {t}]