If the rules for a one-element-dependence tag system are given in the form {2, {{0, 1}, {0, 1, 1}}} (compare page 1114 ), the initial conditions for the Turing machine are TagToMTM[{2, rule_}, init_] := With[{b = FoldList[Plus, 1, Map[Length, rule] + 1]}, Drop[Flatten[{Reverse[Flatten[{1, Map[{Map[ {1, 0, Table[0, {b 〚 # + 1 〛 }]} &, #], 1} &, rule], 1}]], 0, 0, Map[{Table[2, {b 〚 # + 1 〛 }], 3} &, init]}], -1]] surrounded by 0 's, with the head on the leftmost 2 , in state 1 . … Note that although the Turing machine can emulate any number of colors in the tag system, it can only emulate directly rules that delete exactly 2 elements at each step.

The procedure is only slightly more complicated than the one for division discussed above. It involves two numbers r and s , which are initially set to be n and 0, respectively. … And it then turns out that the base 2 digits of s correspond exactly to the base 2 digits of √ n —with one new digit being generated at each step.

Given only an output list NestList[Mod[a #, m]&, x, n] parameters {a, m} that generate the list can be found for sufficiently large n from With[{ α = Apply[(#2 . Rest[list]/#1) &, Apply[ ExtendedGCD, Drop[list, -1]]]}, {Mod[ α , #], #} &[ Fold[GCD[#1, If[#1  0, #2, Mod[#2, #1]]] &, 0, ListCorrelate[{ α , -1}, list]]]] With slightly more effort both x and {a, m} can be found just from First[IntegerDigits[list, 2, p]] .

Zeta function For real s the Riemann zeta function Zeta[s] is given by Sum[1/n s , {n, ∞ }] or Product[1/(1 - Prime[n] s ), {n, ∞ }] . … The picture in the main text shows RiemannSiegelZ[t] , defined as Zeta[1/2 +  t] Exp[  RiemannSiegelTheta[t]] , where RiemannSiegelTheta[t_] = Arg[Gamma[1/4 +  t/2]] - t Log[ π ]/2 The first term in an approximation to RiemannSiegelZ[t] is 2 Cos[RiemannSiegelTheta[t]] ; to get results to a given precision requires summing a number of terms that increases like √ t , making routine computation possible up to t ~ 10 10 . It is known that: • The average spacing between zeros decreases like 1/Log[t] . • The amplitude of wiggles grows with t , but more slowly than t 0.16 . • At least the first 10 billion zeros have Re[s]  1/2 .

by considering digit sequences in which each digit can again have only a discrete set of possible values, typically just 0 and 1. … The picture on the facing page shows what happens with a slightly more complicated rule in which the average gray level is multiplied by 3/2 , and then only the fractional part is kept if the result of this is greater than 1. A continuous cellular automaton in which each cell can have any level of gray between white (0) and black (1).

[Turing] machine 1507 This machine shows in some ways the most complicated behavior of any s = 2 , k = 2 Turing machine. As suggested by picture (k) it fails to halt if and only if its configuration at some step matches {(0) ..., {1, 1}, 1, ___} (in the alternative form of page 888 ). For any input x one can test whether the machine will ever halt using u[{Reverse[IntegerDigits[x, 2]], 0}] u[list_] := v[Split[Flatten[list]]] v[{a_, b_: {}, c_: {}, d_: {}, e_: {}, f_: {}, g___}] := Which[a == {1} || First[a]  0, True, c  {}, False, EvenQ[Length[b]], u[{a, 1 - b, c, d, e, f, g}], EvenQ[Length[c]], u[{a, 1 - b, c, 1, Rest[d], e, f, g, 0}], e  {} || Length[d] ≥ Length[b] + Length[a] - 2, True, EvenQ[Length[e]], u[{a, b , c, d, f, g}], True, u[{a, 1 - b, c, 1 - d, e, 1, Rest[f], g, 0}]] This test takes at most n/3 recursive steps, even though the original machine can take of order n 2 steps to halt.

In fact, rational numbers turn out to be the only kinds of numbers that have repetitive digit sequences. … To find Sqrt[n] one starts by setting r=n and s=0 . Then at each step one applies the rule {r, s} -> If[r >= s+1, {4(r–s–1), 2(s+2)}, {4r, 2s}] .

One-element-dependence tag systems [emulating TMs] Writing the rule {3, {{0, _, _}  {0, 0}, {1, _, _}  {1, 1, 0, 1}}} from page 895 as {3, {0  {0, 0}, 1  {1, 1, 0, 1}}} the evolution of a tag system that depends only on its first element is obtained from TS1EvolveList[rule_, init_, t_] := NestList[TS1Step[rule, #] &, init, t] TS1Step[{n_, subs_}, {}] = {} TS1Step[{n_, subs_}, list_] := Drop[Join[list, First[list] /. subs], n] Given a Turing machine in the form used on page 888 the following will construct a tag system that emulates it: TMToTS1[rules_] := {2, Union[Flatten[rules /. ({i_, u_}  {j_, v_, r_})  {Map[#[i]  {#[i, 1], #[i, 0]} &, {a, b, c, d}], If[r  1, {a[i, u]  {a[j], a[j]}, b[i, u]  Table[b[j], {4}], c[i, u]  Flatten[{Table[b[j], {2v}], Table[c[j], {2 - u}]}], d[i, u]  {d[j]}}, {a[i, u]  Table[a[j], {2 - u}], b[i, u]  {b[j]}, c[i, u]  Flatten[{c[j], c[j], Table[d[j], {2v}]}], d[i, u]  Table[d[j], {4}]}]}]]} A Turing machine in state i with a blank tape corresponds to initial condition {a[i], a[i], c[i]} for the tag system. The configuration of the tape on each side of the head in the Turing machine evolution can be obtained from the tag system evolution using Cases[history, x : {a[_], ___}  Apply[{#1, Reverse[#2]} &, Map[ Drop[IntegerDigits[Count[x, #], 2], -1] &, {_b, _d}]]]

With n = 2 blocks, this means that growth can occur only if the total number of black elements in both blocks is more than 3. … In example (c), the elements are again correlated: the growth is by an average of ( √ 5 - 1)/2 ≃ 0.618 elements at each step, and the first elements on alternate steps form the same nested sequence as obtained from the substitution system {1  {1, 0}, 0  {1}} . In example (d), the frequency of 1's among the first elements of sequence is approximately 3/4; {0, 0} never occurs, and the frequency of {1, 1} is approximately 1/2.

The rule used is of the same kind as on the previous page , but now takes the center cell to become black only if it has exactly 3 black neighbors. If it has 1, 2 or 4 black neighbors then it stays the same color as it was before, and if it has 5 or more black neighbors, then it becomes white on the next step (code number 746). … After t steps, the radius of the approximate circle is about 0.37t .