History of Mathematics Project | Turing's Zeta Function Machine

History of
Mathematics

Project

1939

Turing's Zeta Function Machine

Riemann zeta cogs

This blueprint for an elaborate gear-driven mechanical calculator to compute approximate values for the Riemann zeta function on the critical line was drawn up by Alan Turing's friend and student engineer Donald MacPhail in 1939.

In 1937, Alan Turing became interested in the Riemann hypothesis. In March 1939, he both submitted a paper to the London Mathematical Society (which was not published until 1943) and applied to the Royal Society for a grant for the construction of an elaborate gear-driven mechanical calculator to compute approximate values for the Riemann zeta function on the critical line. A £40 grant was awarded, and Turing's Canadian student engineer and friend Donald MacPhail drew up an actual blueprint on July 17, 1939. A table in the blueprint contains the ratios needed for mechanical linkages, though as prepared, the table contains a number of calculation errors. In any case, the Second World War intervened and the machine was never built. No parts survive.

Artifact format

1 item

Artifact origin

University of Cambridge

Current artifact location

University of Cambridge

Timeline

Interactive Content

Computational Explanation

Blueprints and Modeling of the Zeta Function Machine

The blueprint containing specifications to construct Turing's zeta function machine was drafted in 1939.

Blueprints had been originally introduced by Sir John Herschel in 1842 and were widely used for more than a century for the reproduction of specification drawings used in construction and industry. This technology allowed rapid and reproducible production of an unlimited number of copies.

The Turing zeta function machine blueprint is currently part of the Turing Archive of King's College at Cambridge University:

Out[]=

Although a physical machine was never finished due to the arrival of World War II, a realistic 3D rendering has been created by product design engineer Doga Emirdag in collaboration with Dr. K. I. Ikeda from the Yeditepe University Mathematics Department in Turkey:

However, rather than actually modeling or investigating the detailed mechanical operation of the machine, the remainder of this discussion will instead focus on historical and mathematical context and investigate the details appearing on the blueprint itself.

Turing's Machines

As discussed in a note by Casselman (2006) appearing in a journal issue whose cover image depicted the blueprint of the zeta function machine:

… Alan Turing invented the abstract Turing machine in the mid-1930s. A bit later in the same decade, he designed two concrete machines, the first of which was built and actually functioned.

Turing built his first machine while at Princeton in 1937, assembling it from relays that he built himself in the workshop of the physics department. The construction of this machine was to some extent a collaboration with a Canadian graduate student in physics named Malcolm MacPhail. In a letter to Turing's biographer Andrew Hodges, MacPhail related his experience:

"My small contribution to the project was to lend Turing the key to the shop, which was probably against all the regulations, and to show him how to use the lathe, drill press, … without chopping off his fingers. And so, he wound the relays; and to our surprise and delight the calculator worked."

The machine performed the single task of multiplying two integers in binary format. For example, using the base-2 representation of integers in which only the digits 0 and 1 are used, consider the multiplication of 11 by 5. The number 11 is written in binary as

11

In[]:=

BaseForm[11,2]

Out[]//BaseForm=

1011

… while 5 is written

5

In[]:=

BaseForm[5,2]

Out[]//BaseForm=

101

The product of these two numbers is then:

In[]:=

BaseForm[115,2]

Out[]//BaseForm=

110111

In[]:=

FromDigits[{1,1,0,1,1,1},2]

Out[]=

While commonplace in modern electronic computers, the automation of binary arithmetic was an innovation at the time.

Turing's second machine was the zeta function machine, which was conceived to perform computations that would assist in verifying the Riemann hypothesis. It was designed at Cambridge in 1939 with the assistance of Malcolm MacPhail's brother Donald, then a graduate student in engineering. Turing applied for and received a grant from the Royal Society to cover the (very modest) cost of construction, even after honestly conceding that the apparatus would be "of little permanent value." While the machine was intended to compute values that were only approximations, it was envisioned that its calculations would identify likely locations for zeros, which could then be checked by more traditional methods.

Mathematics of the Riemann Zeta Function

In Turing's application to the Royal Society, he wrote:

"It is proposed to make calculations of the Riemann zeta-function on the critical line for

1450<t<6000

with a view to discovering whether all the zeros of the function in this range of

lie on the critical line. An investigation for

0<t<1464

has already been made by Titchmarsh. The most laborious part of such calculations consists in the evaluation of certain trigonometrical sums

∑

r=1

cos(tlogr-ϑ)m=

2π

In the present calculation it is intended to evaluate these sums approximately in most cases by the use of apparatus somewhat similar to what is used for tide prediction. When this method does not give sufficient accuracy it will be necessary to revert to the straightforward calculation of the trigonometric sums, but this should be only rarely necessary. I am hoping that the use of the tide-predicting machine will reduce the amount of such calculation necessary in a ratio of

50:1

or better. It will not be feasible to use already existing tide predictors because the frequencies occurring in the tide problems are entirely different from those occurring in the zeta function problem. I shall be working in collaboration with D. C. MacPhail, a research student who is an engineer. We propose to do most of the machine shop work ourselves, and are therefore applying only for the cost of materials, and some preliminary computation."

The formula referred to is the Riemann–Siegel theta function, i.e. the function ϑ defined as

ϑ(t)ImlnΓ

lnπ

for real

, which is built into the Wolfram Language as RiemannSiegelTheta:

In[]:=

Plot[RiemannSiegelTheta[t],{t,-30,30},PlotTheme"Detailed"]

Out[]=

ϑ(t)

Using Stirling's approximation to the gamma function

Γ(s)

gives a simple approximation when

is large:

In[]:=

Series[RiemannSiegelTheta[t],{t,∞,5}]//TraditionalForm

Out[]//TraditionalForm=

t(log(t)-1-log(π)-log(2))-

48t

5760

80640

Using Gears to Compute

In a letter to Turing's mother after his death, Malcolm MacPhail wrote:

"Alan's zeta function computer was a device for adding up a large number of sines and cosines of various periods and amplitudes… The gears, of which there were to be hundreds, were to provide an approximation to the required periods… Alan obtained rational approximations to… by the method of continued fractions. A pair of gears having the number of teeth indicated respectively by the numerator and denominator of the fraction would then rotate at speeds having approximately the desired ratio."

The tide-predicting machines referred to by Turing in his grant application were part of a family designed much earlier by Lord Kelvin, one of which he had seen still in use in Liverpool:

As noted by Sir Dermot Turing, the mechanism for generating sinusoidal motion in tide-predicting machines is also present in Alan's zeta function machine (right image):

In correspondence with Andrew Hodges, Donald MacPhail mentioned a variation in the tide-predicting scheme involving balanced weights, but exactly how this would work is not apparent.

The ideas of using fractions to approximate real numbers in calculations involving periodic functions and of using gears to sum such functions is very old. In fact, the blueprint looks not so much like Kelvin's machines as it does the oldest known extant computing device, the Antikythera mechanism, which is a kind of orrery from the first century BCE that was discovered only recently:

Tabulating Logarithms in the Blueprint

In the table included in the upper-left corner of the blueprint, the first column gives the term number

, the second column gives

log

expressed as a ratio of integer products and the third column gives

1

Out[]=

Transcribing the list of ratios given in the second column results in the following list:

In[]:=

RelativeFrequencies=Inactivate0,

144

3431

5735

4473

5083

6134

8329

6497

62107

3462

3557

11361

7583

4967

3973

5897

10744

14064

22732

10289

31123

44103

6058

4955

4346

4429

3427

31133

15148

7167

12726

8933

5934

8349

7238

14464

19132

6123

2527

4473

2583

9788

22724

3493

5735

88107

52113

4782

3470

64101

5232

,Times;

In[]:=

FormattedRelativeFrequencies=RelativeFrequencies/.

;

Using these values, it is possible to rebuild the table and compare its contents with numbers computed from scratch:

In[]:=

TextGridPrependFlatten/@Transpose[Partition[Table[With[{freq=FormattedRelativeFrequencies[[n]],val=If[n1,0,Log[8,n]]},n,freq,N[ReleaseHold[freq]],val,N[val],NumberForm[

-1/2.

,{4,3}]],{n,30}],15]],

Map[

]

,



Out[]=

log

(n)

tabulated

numeric

log

(n)

computed

numeric

log

(n)

tabulated

numeric

log

(n)

computed

numeric

1.000

1.33333

0.250

144

0.333333

0.707

4955

4346

1.36249

Log[17]

Log[8]

1.36249

0.243

3431

5735

0.528321

Log[3]

Log[8]

0.528321

0.577

4429

3427

1.38998

Log[18]

Log[8]

1.38998

0.236

0.666667

0.500

31133

15148

1.41598

Log[19]

Log[8]

1.41598

0.229

4473

5083

0.773976

Log[5]

Log[8]

0.773976

0.447

7167

12726

1.44064

Log[20]

Log[8]

1.44064

0.224

6134

8329

0.861654

Log[6]

Log[8]

0.861654

0.408

8933

5934

1.46411

Log[21]

Log[8]

1.46411

0.218

6497

62107

0.935785

Log[7]

Log[8]

0.935785

0.378

8349

7238

1.48648

Log[22]

Log[8]

1.48648

0.213

0.354

14464

19132

1.50785

Log[23]

Log[8]

1.50785

0.209

3462

3557

1.05664

Log[9]

Log[8]

1.05664

0.333

6123

2527

2.07852

Log[24]

Log[8]

1.52832

0.204

11361

7583

1.10731

Log[10]

Log[8]

1.10731

0.316

4473

2583

1.54795

Log[25]

Log[8]

1.54795

0.200

4967

3973

1.15314

Log[11]

Log[8]

1.15314

0.302

9788

22724

1.56681

Log[26]

Log[8]

1.56681

0.196

5897

10744

1.19499

Log[12]

Log[8]

1.19499

0.289

3493

5735

1.58496

Log[27]

Log[8]

1.58496

0.192

14064

22732

1.23348

Log[13]

Log[8]

1.23348

0.277

88107

52113

1.60245

Log[28]

Log[8]

1.60245

0.189

10289

31123

1.26912

Log[14]

Log[8]

1.26912

0.267

4782

3470

1.61933

Log[29]

Log[8]

1.61933

0.186

44103

6058

1.3023

Log[15]

Log[8]

1.3023

0.258

64101

5232

3.88462

Log[30]

Log[8]

1.63563

0.183

As highlighted in yellow above and immediately obvious when plotting the tabulated values against

log

(n)

, there are errors in the table:

In[]:=

ShowListPlot{Log[8,Range[30]],Style[Activate@RelativeFrequencies,Red]},

,Plot[Log[8,n],{n,0.,30}]

Out[]=

To explore the discrepancies, first note that the tabulated rationalizations of

log

generally contain fractions expressed as a ratio of numbers with numerator and denominator each written as a product of two factors chosen to be the closest possible to each other. However, approximations with multiples of 12 in the denominator dispense with the factorization altogether and are instead written as a fraction with 48 in the numerators—a practice possibly related to the number of teeth on standardized gears. Furthermore, for cases other than fractions with denominators divisible by 12, the numerators and denominators sometimes contain common multiples, likely to ensure the gears involved had enough teeth to be able to engage one another.

The following algorithm:

In[]:=

ClosestFactorProduct[0]:=0ClosestFactorProduct[1]:=1ClosestFactorProduct[n_Integer]:=Module[{p={#,n/#}&/@Divisors[n],diffs},diffs={Abs[Subtract@@#],#}&/@p;Sort[diffs][[1,2]]]ClosestFactorProduct[r_Rational]:=Module[{n=Numerator[r],d=Denominator[r],products,min,mult},If[IntegerQ[48/n],HoldForm[48]/(48d/n),(*Else*)products=ClosestFactorProduct/@{n,d};mult=If[(min=Min@@Flatten[products])<23,Ceiling[33/min],1];Divide[CenterDot@@ClosestFactorProduct[multTimes@@products[[1]]],CenterDot@@ClosestFactorProduct[multTimes@@products[[2]]]]]]

… generally reproduces the form of the fractions given in the blueprint:

In[]:=

TextGridPrependFlatten/@Transpose[Partition[MapIndexed[{#2[[1]],#,ClosestFactorProduct[ReleaseHold@#]}&,FormattedRelativeFrequencies],15]],

Map[

]

,

Rule[

]



Out[]=

n	tabulated	computed	n	tabulated	computed
1	0	0	16	48 36	48 36
2	48 144	48 144	17	4955 4346	49·55 43·46
3	3431 5735	31·34 35·57	18	4429 3427	29·44 27·34
4	48 72	48 72	19	31133 15148	33·311 48·151
5	4473 5083	44·73 50·83	20	7167 12726	67·71 26·127
6	6134 8329	34·61 29·83	21	8933 5934	33·89 34·59
7	6497 62107	32·97 31·107	22	8349 7238	49·83 48·57
8	1	1	23	14464 19132	96·99 33·191
9	3462 3557	34·62 35·57	24	6123 2527	23·61 25·27
10	11361 7583	61·113 75·83	25	4473 2583	44·73 25·83
11	4967 3973	49·67 39·73	26	9788 22724	97·121 33·227
12	5897 10744	58·97 44·107	27	3493 5735	34·62 35·38
13	14064 22732	88·105 33·227	28	88107 52113	66·107 39·113
14	10289 31123	89·102 23·311	29	4782 3470	41·47 34·35
15	44103 6058	33·103 45·58	30	64101 5232	33·101 26·33

When it does not, it usually seems to be because terms involving 64 are preferred in the blueprint, meaning special treatment is probably needed to accommodate that preference.

For example, the third term in the table is

3431/(5735)1054/1995

, which the above algorithm gives:

In[]:=

ClosestFactorProduct

1054

1995



Out[]=

31·34

35·57

Also, this fraction indeed gives a good approximation to

log

In[]:=

With[{val=FormattedRelativeFrequencies[[3]]},{val,val//ReleaseHold,val//ReleaseHold//N,Log[8,3]//N}]

Out[]=



3431

5735

1054

1995

,0.528321,0.528321

Finally, as expected based on MacPhail's comments, this approximation corresponds to the seventh continued fraction convergent of

log

In[]:=

Convergents[Log[8,3],7]

Out[]=

0,1,

513

971

1054

1995



Correcting Term 24

Now investigate the error in the fraction given for term number 24:

With[{val=FormattedRelativeFrequencies[[24]]},{val,val//ReleaseHold,val//ReleaseHold//N,Log[8,24]//N}]

Out[]=



6123

2527

1403

675

,2.07852,1.52832

The disagreement between the final two numbers clearly shows that the tabulated approximation is invalid. Interestingly, attempting to find the correct value using continued fractions does not provide a convergent with factors corresponding to those given in the erroneous value:

In[]:=

convergents8=Convergents[Log[8,24],8]

Out[]=

1,2,

1484

971

3049

1995

22827

14936



In[]:=

ClosestFactorProduct/@convergents8

Out[]=

1,2,

2·13

9·9

28·53

971

3049

35·57

21·1087

8·1867



This fact suggests that not all tabulated rational approximations were computed using continued fractions. Therefore, attempt to reconstruct the intended value via rational approximation using the Wolfram Language function Rationalize for a smallest denominator that lies within

for various values of

In[]:=

RationalizeApproximation[x_?NumericQ,dx_]:=ClosestFactorProduct[Rationalize[x,dx]]

In[]:=

TextGrid[Transpose@Table[{NumberForm[x,{2,1}],RationalizeApproximation[Log[8,24],10^-x]},{x,5,7,.2}],DividersAll]

Out[]=

5.0	5.2	5.4	5.6	5.8	6.0	6.2	6.4	6.6	6.8	7.0
2·499 653	29·40 23·33	2·661 5·173	23·61 27·34	28·53 971	28·53 971	28·53 971	3049 35·57	3049 35·57	3049 35·57	3049 35·57

The value for

 5.6 provides the correction; 25 has been inadvertently written for 34, so the value should be:

In[]:=

Withval=

6123

2734

,{val,val//ReleaseHold,val//ReleaseHold//N,Log[8,24]//N}

Out[]=



6123

2734

1403

918

,1.52832,1.52832

Correcting Term 30

Similarly, investigating 30:

In[]:=

With[{val=FormattedRelativeFrequencies[[30]]},{val,val//ReleaseHold,val//ReleaseHold//N,Log[8,30]//N}]

Out[]=



64101

5232

101

,3.88462,1.63563

Attempting to reconstruct the tabulated fraction via continued fractions:

In[]:=

convergents30=Convergents[Log[8,30],9]

Out[]=

1,2,

193

118

211

129

404

247



In[]:=

ClosestFactorProduct/@convergents30

Out[]=

1,2,

2·4

3·6

193

2·59

211

3·43

4·101

13·19



… this time yields an obvious match in the form of the ninth convergent. In particular, scaling each of the numbers in the denominator of

4101/(1319)

by 4 and correspondingly multiplying the first factor in the numerator by a corresponding factor of 16 gives:

In[]:=

Withval=

64101

5276

,{val,val//ReleaseHold,val//ReleaseHold//N,Log[8,30]//N}

Out[]=



64101

5276

404

247

,1.63563,1.63563

Therefore, the blueprint inadvertently wrote 32 where 76 was intended.

Other Resources

Wolfram MathWorld
Riemann–Siegel Functions

Wolfram Demonstration
Antikythera Mechanism

Wolfram Demonstration
Contour Plots of the Zeta Function

Wolfram Demonstration
Riemann Hypothesis

Wolfram Demonstration
Riemann Zeta Function

Wolfram Demonstration
Riemann Zeta Function near the Critical Line

Additional Reading

Casselman, B. "Blueprint for a Turing Machine: About the Cover...and a Bit More." Notices of the American Mathematical Society, Vol. 53, No. 10, cover and pp. 1186–1189, 2006.
Hejhala, D. A. and Odlyzko, A. M. "Alan Turing and the Riemann Zeta Function." Unpublished (?) manuscript, 2011. [link].
Hodges, A. Alan Turing: The Enigma, rev ed. Princeton, NJ: Princeton University Press, pp. 196–199, 2014.
Turing, A. M. "A Method for calculation of the Zeta function." Proceedings of the London Mathematical Society, Vol. 48, pp. 180–197, 1943.
Welch, P. D. "Turing’s Mathematical Work." In Proceedings of the 6th Congress (6 ECM) held at the Jagiellonian University, Kraków, July 2–7, 2012 (Ed. R. Latała, A. Ruciński, P. Strzelecki, J. Świątkowski, D. Wrzosek and P. Zakrzewski). Zürich, Switzerland: European Mathematical Society, pp. 763–777, 2013.

Additional Links

Image Credits

King's College Library, Cambridge. AMT/C 2 Blueprint of the zeta function machine

Turing's Zeta Function Machine

Timeline

Interactive Content

Computational Explanation

Blueprints and Modeling of the Zeta Function Machine

Turing's Machines

Mathematics of the Riemann Zeta Function

Using Gears to Compute

Tabulating Logarithms in the Blueprint

Correcting Term 24

Correcting Term 30

Other Resources

Wolfram MathWorld

Wolfram MathWorld

Wolfram Demonstration

Wolfram Demonstration

Wolfram Demonstration

Wolfram Demonstration

Wolfram Demonstration

Additional Reading

Additional Links

Image Credits