Prime Numbers and Turing


October 2012

In his beautifully written book The Music of the Primes [1], Marcus du Sautoy presented a history of mathematical investigations into the behavior of the prime numbers. Can one predict when the next prime number will occur? Is there a formula that could generate prime numbers? Du Sautoy entertained such questions by discussing the work of several great mathematicians of the past, including Gauss, Riemann, and Turing.

At a 2012 Turing event in Brussels, Leo Corry gave an overview of du Sautoy's book and presented some of his own research results on the history of computing in mathematics. Towards the end of his talk, Corry made some educated guesses about the Turing/von-Neumann controversy.

Understanding the way in which the prime numbers appear along the line of the natural numbers has been a quest for centuries. One major breakthrough was due to Gauss (1777-1855) who chose to investigate the amount of prime numbers that is smaller than a number x, rather than question which numbers precisely are prime. In du Sautoy's words:

By stepping back and asking the broader question of how many primes there are up to [a number x] rather than precisely which numbers are prime, a strong regularity seemed to emerge. [1, p.49]

Gauss defined Π(x) to denote the number of primes smaller than x. For example, Π(8) = 3 because 3, 5, and 7 are the prime numbers smaller than 8. Gauss conjectured that the well-understood function Li(x) — which, loosely speaking, provides the natural logarithm of x — remained in the vicinity of Π(x) for arbitrary values of x. In other words, Gauss believed he had found a pattern in the seemingly chaotic world of the primes.

After Gauss, in the next generation of mathematicians, Riemann defined his zeta-function ζ(s). To grasp the behavior of the Riemann zeta-function, mathematicians searched for the points where the function becomes zero. Well-known points were -2, -4, -6, etc. Far less obvious was Riemann's hypothesis — “the Riemann Hypothesis” — which states that all other zeros are of the form 1/2 + i.z; that is, all other zeros share a real part that is exactly one half.

By 1901, mathematicians had proved a connection between the Riemann zeta-function and the behavior of the prime numbers. Specifically, the Riemann Hypothesis is true if and only if the behavior of Li(x) is very close to that of Π(x). The Riemann Hypothesis thus began to play a significant role in the study of the primes and several mathematicians of standing therefore became actively involved in trying to prove the Riemann Hypothesis. These mathematicians included Landau, Hardy, and Littlewood.

Contrary to the prevailing opinion of the time, Hardy and Littlewood eventually began to suspect that the Riemann Hypothesis was false [1, p.150]. Disproving the hypothesis meant finding a counter example. Oversimplifying matters a bit, it is in this connection that Hardy's student Titchmarsch wrote his famous 1936 article `The zeros of the Riemann zeta-function' in which he confirmed that the first 1,041 points did fulfill the Riemann Hypothesis. Titchmarsch had calculated those zeros with a calculating machine, based in no small part on the help of Comrie “who had a tremendous influence in helping establish institutions in order to apply methods of intensive calculations of all kinds” [2]. Before Titchmarsch, Corry said, almost no one dealt with mechanical calculations. One exception is Hutchinson and his 1925 article `On the Roots of the Riemann Zeta Function'. Corry continued:

[Hutchinson] was a rather marginal American mathematician of whom we don't even have a picture. This is more representative of the kind of people who would undertake calculations of this kind in 1924.

Before World War II, only two people had dealt with the calculational problem. After the war, some people including Turing joined. [2] 

In Corry's talk, a vivid picture emerged of Titchmarsch, Turing and some others trying to calculate the zeroes of the Riemann zeta-function by means of special machinery. The Lehmers did similar work in connection with Fermat's Last Theorem.

Turing and the Lehmers were using these new [post-war] instruments on the weekends when no one was using them. No one would think of putting all this money into calculating the zeroes of the Riemann zeta-function or the validity of Fermat's Last Theorem. [2]

This calculational perspective helps us, historians, understand how the Lehmers, Turing, and von Neumann viewed machinery. On the one hand, Corry said, most mathematicians still followed the Hilbert tradition in not wanting to compute, much preferring abstract reasoning over calculating particular cases. On the other hand, “the people with the computers didn't want to let [these few] mathematicians compute these exotic results [either]”. The computational trend only took off gradually and in no small part due to the Lehmers, Turing, and von Neumann. These researchers, Corry said, “belonged to both camps”; that is, they were both applied and pure mathematicians.

They had been involved in calculations on computing machinery because of the war effort, but their background had been in number theory and things like that. [2]

Before the war, Corry observed, Turing had planned to use a special analog machine with the purpose of performing some calculations of the Riemann zeta-function. By the early 1950s, Corry continued, Turing was using a general-purpose machine; that is, a digital, electronic machine.

Coming then to the Turing/von-Neumann story, Corry noted that it “has been represented quite differently in the literature”. Corry expounded by first citing Max Newman.

[Newman in 1954:] Right from the start Turing was interested in the possibility of actually building such a machine.

With “Right from the start” and “such a machine”, Corry elaborated, Newman meant “1936” and “an embodiment of a universal Turing machine”, respectively. Furthermore, Corry remarked, most of Turing's contemporaries who spoke about 1936 did this twenty to forty years later. These comments, including Newman's comment presented above, should thus be taken with large grains of salt.

[Corry:] Just to give you two further examples. In the biographies they always mention that in 1937--1938 Turing was in Princeton and he met von Neumann and that they had an important interaction. This is of course true, but what did they speak about? That is the interesting question. Many people today assume that they spoke about the machine: obviously, Turing in 1936 wrote about machines and von Neumann in 1945 helped make a machine, so surely they must have been speaking about a machine when they were both in Princeton. I say no, we have no evidence of that. We have evidence that they had a lot of topics in common. First of all, Turing’s 1936 article about computable numbers is a reaction to Hilbert, and in the 1930s von Neumann was in Göttingen working on that. Surely they spoke about that [i.e. mathematical logic], and not in terms of building machines. That’s one point.

The second point is that at that time both of them were working on continuous groups. That was the topic of common interest for both of them. [...] [I]n my view it is much more likely that these were the topics they were talking about and not about the possibility of building a computing machine. [2]

By putting Turing's work on the Riemann Hypothesis in context, Corry tentatively explained why today we don't have any primary sources backing up the common belief that Turing and von Neumann wanted to build universal Turing machines from the very beginning. Turing wanted to calculate zeroes of the Riemann zeta-function. That's why he almost single-handedly constructed an analog machine in 1939. This feat, in turn, is similar to the Lehmers'.

[Corry:] Analog machines were important at the time. Of course, when we look at history, we have the digital general-purpose, stored-program computer, and it looks as if everything before that converged. But history was not like that. People were doing a lot of different things. For example, the Lehmers [...] constructed at least three different analog machines with physical chains and all kinds of mechanical and electro-mechanical parts.

So Turing, when he was working on the problem of the zeroes of the Riemann zeta-function, perhaps the most natural thing was to go to the analog machines. Those were the machines that led to practical results. There was also the differential analyzer of Vandiver Bush and things like that. Everything about building a general-purpose machine belonged to the future. It was not there in 1939. [2]

Corry warned his audience not to view the history of computing as a straight line from Turing's 1936 paper to the stored-program computer; that is, from theory to practice. Newman's 1954 comment, presented above, is most likely a false memory, as Corry elaborated in the Q&A session of his talk.

[1] M. du Sautoy. The Music of the Primes: Why an Unsolved Problem in Mathematics Matters. Harper Perennial, 2004.

[2] L. Corry. Turing and the Computational Tradition in Pure Mathematics: The Case of the Riemann Zeta-Function. Video recorded and transcribed by E.G. Daylight. (The text above is approved by Corry.) Presentation at Turing in Context II, Brussels, 10-12 October 2012.