Turing’s Zeta Machine & the Riemann Hypothesis

4Sep - by Alan - 0 - In
English: The Riemann zeta-function on the stri...
English: The Riemann zeta-function on the strip 1/2 (Photo credit: Wikipedia)

Alan Turing is well-known for his role in code breaking at Bletchley Park during World War 2. He’s also famous for laying the foundations of computer science and Artificial Intelligence; now eponymously known as the Turing Machine and the Turing Test. Some people even know that he did seminal work on biological pattern formation. But he also had some significant results in “traditional” mathematics. In particular he was very  interested in the famous Riemann Hypothesis : a long-standing conjecture that the zeros of the Riemann zeta function lie on a certain straight line. Bernhard Riemann conjectured this in 1859, and nobody has yet proven it. It is a very celebrated mathematical problem (perhaps even more so than Fermat’s Last Theorem) and as one of the Millenium Prize Problems, is worth $1,000,000 to whoever can prove or disprove it. Alan Turing developed a rigorous method for verifying the hypothesis for the initial zeros. He also invented a machine for calculating the values of the zeta function. In contrast to the famous ‘Turing machines’, he started to implement this machine but never finished because of World War 2.

ζ(s) = 1 + 1/2s + 1/3s + 1/4s + … where s is complex

The Riemann hypothesis is that all nontrivial zeros of the analytical continuation of the Riemann zeta function have a real part of 1/2. A proof or disproof of this would have far-reaching implications in number theory, especially for the distribution of prime numbers. This was Hilbert’s eighth problem, and is still considered an important open problem a century later. It has withstood every attempt to prove it, and some mathematicians believe it may be false, or possible unprovable, as an exemplar of Gödel’s incompleteness theorems – which are paralleled in computer science by Turing’s proof of the undecidability of the halting problem:

In 1928, German mathematician David Hilbert had called attention to the Entscheidungsproblem (decision problem). In his momentous paper “On Computable Numbers, with an Application to the Entscheidungsproblem” (submitted on 28 May 1936 and delivered 12 November), Turing reformulated Kurt Gödel‘s 1931 results on the limits of proof and computation, replacing Gödel’s universal arithmetic-based formal language with the formal and simple hypothetical devices that became known as Turing machines. He proved that some such machine would be capable of performing any conceivable mathematical computation if it were representable as an algorithm. He went on to prove that there was no solution to the Entscheidungsproblem by first showing that the halting problem for Turing machines is undecidable: in general, it is not possible to decide algorithmically, whether a given Turing machine will ever halt. (wikipedia)

Computer calculations have shown that the first 10 trillion zeros do indeed lie on that line. Given that much experimental evidence any scientist would say this is a law, not a hypothesis! However, mathematicians must have a proof, because that would then explain why those zeros are there – and because, while it may seem extremely extremely unlikely the hypothesis is wrong – it cannot just be assumed true, since there are already examples of mathematical formulae that are true up to mind-boggling numbers, and then become false.

Turing’s work on ‘ordinal logics‘ was completed in 1938 and successfully submitted as a Ph.D. thesis. While working on his Ph.D. thesis, Turing was interested in some other subjects as well, such as analytic number theory, and in particular the Riemann Hypothesis, and more precisely the aspect of it that concerns the distribution of prime numbers.

“Turing had ideas for the design of an “analogue” machine for calculating the zeros of the Riemann zeta-function, similar to the one used in Liverpool for calculating the tides.” (Herken, The Universal Turing Machine: A Half-Century Survey, p. 110).

In 1939 Alan Turing applied to the Royal Society for a grant of £40 for the engineering of a special machine to calculate approximate values for the Riemann zeta-function on its critical line. He wrote in it:

“Apparatus would be of little permanent value. It could be added to for the purpose of carrying out similar calculations for a wider range of t* and might be used for some other investigations connected with the zeta-function. I cannot think of any applications that would not be connected with the zeta-function.”

The calculation required summation of a trigonometrical series, and Turing knew of the Liverpool tide predicting machine which performed the summation of a somewhat similar series. Turing was assisted by Donald McPhail, a Canadian student engineer then at King’s College. They prepared a blueprint which can be seen in the Turing Digital archive. So he started construction of a precision-machined gear-driven mechanical calculator – in the spirit of Charles Babbage – which would have helped to make progress in verifying the Riemann Hypothesis. It was to be a very special-purpose device for adding up 30 sine components in the various ratios needed to perform calculations using the Riemann-Siegel theta function. These sines would be generated by a system of 30 meshing gear wheels, 30 weights being attached to the wheels at some distance from their centres, creating moments (turning forces) to be balanced by a single counterweight representing their summation.

Andrew Hodges explains this in more detail:

There would in fact be thirty wave-like terms to be added, each simulated by the rotation of one gear wheel. Thirty weights were to be attached to the corresponding wheels, at a distance from their centres, and then the moment of the weights would vary in a wave-like way as the wheels rotated. The summation would be performed by balancing the combined effect of the weights by a single counterweight.

The frequencies of the thirty waves required ran through the logarithms of the integers up to thirty. … This required four gear wheels … to move each other so that one of them could act as the generator of the ‘wave’. Some of the wheels could be used two or three times over, so that about 80, rather than 120 gear wheels were required in all. These wheels were ingeniously arranged in meshing groups, and mounted on a central axis in such a way that the turning of a large handle would set them in simultaneous motion. The construction of the machine demanded a great deal of highly accurate gear-cutting to make this possible.

Alan made a start on cutting the gear wheels himself, taking the blanks in a rucksack to the engineering department of Cambridge University, and bringing the gears back to his room, where they either lay on the floor or were stored in a suitcase. He never completed the construction (ala Babbage again, but at least his excuse was World War II), but after the war, he used an early electronic computer to calculate some zeros, becoming the first person to do so.

Having worked on the zeta-function since his Ph.D.-thesis but never having published anything directly on the topic, Turing began working as chief cryptanalyst during the Second World War and thus postponed this important work till after the war. Thus, it was not until 1945 that he was actually able to publish his first work on this most important subject, namely the work that he had presented already in 1939, the groundbreaking “A Method for the Calculation of the Zeta-Function”, which constitutes his first printed contribution to the subject.

In June 1950 he used the prototype Manchester University Electronic Computer to do some calculations concerned with the distribution of the zeros of the Riemann zeta-function, specifically whether there are any zeros not on the critical line in certain intervals. The pre-war record for the number of zeros located on the line was held by Ted Titchmarsh, confirming that the first 1041 points were OK. Turing extended this to the first 1104 zeros but then, unfortunately, the computer broke down. He devised what is now called “Turing’s method” for easier computational analysis of the function, detailed in his papers “A method for the calculation of the zeta-function” and “Some calculations of the Riemann zeta-function,” which are both widely referenced in modern mathematical publications.

“After the publication of his paper “On computable Numbers,” Turing had begun investigating the Riemann zeta-function calculation, an aspect of the Riemann hypothesis concerning the distribution of prime numbers… Turing’s work on this problem was interrupted by World War II, but in 1950 he resumed his investigations with the aid of the Manchester University Mark I [one of the earliest general purpose digital computers]…” (Origins of Cyberspace p. 468).

Sources & Further Reading

Books