With the state of a 2-color tag system encoded as an integer according to FromDigits[Reverse[list] + 1, 3] the following takes the rule for any such tag system (in the first form from page 894 ) and yields a primitive recursive function that emulates a single step in its evolution: TSToPR[{n_, rule_}] := Fold[Apply[c, Flatten[{#1, Array[p, # 2], c[r[z, c[r[p[1], s], c[r[z, p[2]], c[r[z, r[c[s, z], c[r[c[s, c[s, z]], z], p[2]]]], p[2]]], p[1]]], p[#2]]}]] & , c[c[r[p[1], s], p[1], c[r[p[1], r[z, c[s, c[s, s]]]], c[c[r[z, c[r[p[1], s], c[r[z, c[s, z]], c[r[p[1], r[z, c[r[p[1], s], c[r[z, p[2]], c[ r[z, r[c[s, z], c[r[c[s, c[s, z]], z], p[2]]]], p[2]]], p[1]]]], p[2], p[3]]], p[1]]], p[1], p[1]], p[1]], p[2]]], p[n + 1], MapIndexed[c[r[z, c[r[p[1], p[4]], p[2], p[3], p[4]]], c[r[z, r[c[s, z], c[r[c[s, c[s, z]], z], p[2]]]], p[Length[#2] + 1]], # 1 〚 1 〛 , #1 〚 2 〛 ] & , Nest[Partition[#1, 2] & , Table[Nest[c[s, #] & z, FromDigits[Reverse[IntegerDigits[i, 2, n] /. rule] + 1, 3]], {i, 0, 2 n - 1}], n - 1], {0, n - 1}]], Range[n, 1, -1]] (For tag system (a) from page 94 this yields a primitive recursive function of size 325.) … Note that the same basic approach can be used to emulate Turing machines with recursive functions; the Turing machine configuration {s, list, n} can be encoded by an integer such as 2^FromDigits[Reverse[Take[list, n - 1]]] 3^FromDigits[Take[list, {n + 1, -1}]] 5^list 〚 n 〛 7 s

Game of Life [cellular automaton] Invented by John Conway around 1970 (see page 877 ), the Life 2D cellular automaton has been much studied in recreational computing, and as described on page 964 many localized structures in it have been identified. Each step in its evolution can be implemented using LifeStep[a_List] := MapThread[If[(#1  1 && #2  4) || #2  3, 1, 0]&, {a, Sum[RotateLeft[a, {i, j}], {i, -1, 1}, {j, -1, 1}]}, 2] A more efficient implementation can be obtained by operating not on a complete array of black and white cells but rather just on a list of positions of black cells.

As an example, the n th digit of Log[2] in base 2 is formally given by Round[FractionalPart[2 n Sum[2 -k /k, {k, ∞ }]]] . And in practice the n th digit can be found just by computing slightly over n terms of the sum, according to Round[FractionalPart[ Sum[FractionalPart[PowerMod[2, n - k, k]/k], {k, n}] + Sum[2 n - k /k, {k, n + 1, n + d}]]] where several values of d can be tried to check that the result does not change. … The same basic approach as for Log[2] can be used to obtain base 16 digits in π from the following formula for π : Sum[16 -k (4/(8k + 1) - 2/(8k + 4) - 1/(8k + 5)-1/(8k + 6)), {k, 0, ∞ }] A similar approach can also be used for many other constants that can be viewed as related to values of PolyLog .

In basic mathematics these might be n , 2n , 3n , ... or n 2 , n 3 , ..., or 2 n , 3 n , ..., or 2 n , 2 2 n , 2 2 n , ... To go further one begins by defining an analog to the Ackermann function of page 906 :  [1][n_] = 2n;  [s_][n_] := Nest[  [s - 1], 1, n]  [2][n] is then 2 n ,  [3] is iterated power, and so on. … In practice, however, it gets more and more difficult to determine that the functions defined in this way actually in a sense halt and yield definite values—and indeed for  [ ε 0 ] this can no longer be proved using the ordinary axioms of arithmetic (see below ).

(See page 103 for a symbolic system with halting times that grow like Nest[2 # &, 0, n] .)

These pictures can be thought of as matrices with 1's at the position of each black dot, and 0's elsewhere. Multiplying these matrices modulo 2 by vectors corresponding to a row of the cellular automaton gives a column, and vice versa. This means that the matrix on the second row of pictures is the inverse modulo 2 of the one on the first row.

And then in the specific case shown one compares corresponding digits in these two sequences, and if these digits are ever respectively 0 and 1, then the square is white; otherwise it is black. … And in the case shown on the next page the rules for this system are such that they replace each square at each step by a 2×2 block of new squares.

Explanations suggested for apparent absence include: • Extraterrestrials are visiting, but we do not detect them; • Extraterrestrials have visited, but not in recorded history; • Extraterrestrials choose to exist in other dimensions; • Interstellar travel is somehow infeasible; • Colonization is somehow ecologically limited; • Physical travel is not worth it; only signals are ever sent. … The result is a product of: rate of formation of suitable stars; fraction with planetary systems; number of Earth-like planets per system; fraction where life develops; fraction where intelligence develops; fraction where technology develops; time communicating civilizations survive. … Out of about 6 billion humans, however, it is notable that only extremely few choose, say, to explore life in the depths of the oceans—though perhaps this is just because technology has not yet made it easy to do.

The third curve shown on page 346 is obtained from Table[Cost[IntegerDigits[i, 2, n]], {i, 0, 2 n - 1}] There is no single ordering that makes all states which can be reached by changing a single square be adjacent.

Defining PM[s_] := IntegerDigits[Range[2 s - 1], 2, s] blocks of data of length m can be encoded with Join[data, Mod[data . Select[PM[s], Count[#, 1] > 1 &], 2]] while blocks of length n (and at most one error) can be decoded with Drop[(If[#  0, data, MapAt[1 - # &, data, #]] &)[ FromDigits[Mod[data . PM[s], 2], 2]], -s] A number of families of linear codes are known, together with a few nonlinear ones.