I propose to consider
the question, ‘Can machines think?’ Alan Turing, Computing Machinery and Intelligence
Alan Turing’s name will always be associated with the cracking of Germany’s wartime code, Enigma. From the comfort of the country house of Bletchley Park, halfway between Oxford and Cambridge, Churchill’s code-breakers created a machine which could decode the messages sent each day by German intelligence. The story of how Turing’s unique combination of mathematical logic and determination helped save many lives from the threat of the German U-boats is the stuff of novels, plays and movies. Yet the inspiration for the creation of his ‘bombes’, the code-cracking machines, can be traced back to Turing’s mathematical days in Cambridge, when Hardy and Hilbert were still in the ascendancy.
Before the Second World War engulfed Europe, Turing was already planning machines that would blow two of Hilbert’s twenty-three problems out of the water. The first was a theoretical machine, existing only in the mind, which would demolish any hope that the secure basis of the foundations of the mathematical edifice could be checked. The second was very real, made of cogs and dripping with oil, and with this machine Turing intended to challenge another mathematical orthodoxy. He dreamt that this spinning contraption might have the power to disprove the eighth and Hilbert’s favourite of the twenty-three problems: the Riemann Hypothesis.
After years of his colleagues failing to prove the Riemann Hypothesis, Turing believed that perhaps it was time to investigate whether Riemann might have been wrong. Perhaps there actually was a zero off Riemann’s critical line, which would thus force some pattern onto the sequence of primes. Turing could see that machines would become the most powerful tools in a search for the zeros that might disprove Riemann’s conjecture. Thanks to Turing, mathematicians would now have the help of a new, mechanical partner in their investigation of Riemann’s Hypothesis. But it wasn’t just Turing’s physical machines that would have an impact on mathematicians’ exploration of the primes. His machines of the mind, originally created to attack Hilbert’s second problem, would lead in the late twentieth century to the most unexpected offshoot: a formula for generating all the primes.
Turing’s fascination with machines was stimulated by a book that he was given in 1922 when he was ten years old. Natural Wonders Every Child Should Know by Edwin Tenney Brewster was packed with nuggets which fired the young Turing’s imagination. Published in 1912, it explained that there were explanations for natural phenomenon, and it didn’t rely on feeding its young readers with passive observations. Given Turing’s later passion for artificial intelligence, Brewster’s description of living things is particularly enlightening:
For of course the body is a machine. It is a vastly complex machine, many, many times more complicated than any machine ever made with hands; but still after all a machine. It has been likened to a steam machine. But that was before we knew as much about the way it works as we know now. It really is a gas engine; like the engine of an automobile, a motor boat or a flying machine.
Even at school, Turing was obsessed with inventing and building things: a camera, a refillable ink-pen, even a typewriter. It was a passion that he would take with him when he went to Cambridge in 1931 to read mathematics as an undergraduate at King’s College. Although Turing was shy and something of an outsider, like many before him he found reassurance in the absolute certainty that mathematics provided. But his passion for building things stayed with him. He would always be on the lookout for the physical machine that would lay bare the mechanism of some abstract problem.
Turing’s first piece of research as an undergraduate was an attempt to understand one of the borders where abstract mathematics rubs up against the vagaries of nature. His starting point was the practical problem of tossing a coin. The outcome was a sophisticated theoretical analysis of the scores produced by any random experiment. Turing was a little upset when he presented his proof only to find that, like Erdos and Selberg before him, his first piece of research had duplicated what had been achieved some ten years before by a Finnish mathematician, J.W. Lindeberg, and was called the Central Limit Theorem.
Number theorists would later find that the Central Limit Theorem provides new insights into estimating the number of primes. The Riemann Hypothesis would confirm that the deviation between the true number of primes and Gauss’s estimate is the same as the deviation we expect from tossing a fair coin. But the Central Limit Theorem revealed that the distribution of primes cannot be perfectly modelled by the tossing of a coin. The more refined measure of randomness made possible by the Central Limit Theorem is not obeyed by the primes. Statistics is all about the different angles from which to judge collections of data. From the viewpoint of Turing and Lindeberg’s Central Limit Theorem, mathematicians could see that although the primes and the tossing of a coin had much in common, they were not one and the same thing.
Turing’s proof of the Central Limit Theorem, although not original, was proof enough of his potential, and he was elected to a Fellowship at King’s at the precocious age of twenty-two. Turing remained something of a loner in the Cambridge mathematical community. Whilst Hardy and Littlewood battled with classical problems in number theory, Turing preferred to work outside the mathematical canon. Rather than read the mathematical papers of his peers, he preferred to come up with his own conclusions. Like Selberg, he cut himself off from the distractions of a conventional academic life.
Despite this self-imposed isolation, Turing could not fail to be aware of a crisis that was sweeping through mathematics. People in Cambridge were talking about the work of a young Austrian mathematician who had put uncertainty at the heart of the subject that had promised security for Turing.
Gödel and the limitations of the mathematical method
In his second problem, Hilbert had challenged the mathematical community to produce a proof that mathematics did not contain contradictions. It was the ancient Greeks who began the development of mathematics as a subject of theorems and proofs. They started with basic statements about numbers which seemed to be self-evident truths. These statements, the axioms of mathematics, are the seeds from which the rest of the mathematical garden has grown. Since Euclid’s first proofs about the primes, mathematicians have been using deduction to extend our knowledge of numbers beyond these axioms.
But a worrying question had been thrown up by Hilbert’s study of different sorts of geometry. Are we sure that we could never prove that a statement was both true and false? How certain are we that there doesn’t exist one sequence of deductions from the axioms which would prove that the Riemann Hypothesis was true, whilst an alternative sequence would prove it false? Hilbert felt certain that mathematical logic could be used to prove that mathematics contained no such contradictions. In his view, the second of his twenty-three problems was just a matter of putting the mathematical house in order. The question became slightly more urgent after a number of people, including Bertrand Russell, the philosopher friend of Hardy and Littlewood, had produced what appeared to be mathematical paradoxes. Although Russell’s monumental work Principia Mathematica found a way to resolve these paradoxes, it alerted many to the serious nature of Hilbert’s question.
On September 7, 1930, Hilbert was accorded the privilege of being made an honorary citizen of Königsberg, his beloved home town. It was the year of his retirement from Göttingen. He ended his acceptance speech with a clarion call to all mathematicians: ‘Wir müssen wissen. Wir werden wissen.’ (‘We must know, we shall know.’) After making his speech he was whisked off to a recording studio to record the last part of it for a radio broadcast. One can detect in the crackle of the recording Hilbert laughing after he declares, ‘We must know.’ Unknown to Hilbert, though, the last laugh had already been had the day before at a conference held down the road at the University in Königsberg. A twenty-five-year-old Austrian logician, Kurt Gödel, had made an announcement which struck at the heart of Hilbert’s world-view.
As a child, Gödel had been known as ‘Herr Warum’ – Mr Why – because of his incessant stream of questions. A bout of rheumatic fever in his childhood left him with a weak heart and incurable hypochondria.Towards the end of his life, his hypochondria turned to outright paranoia. He became so convinced that people were trying to poison him that he literally starved himself to death. But at twenty-five he was the one poisoning Hilbert’s dream and inducing a rush of paranoia throughout the mathematical community.
For his dissertation, Gödel had turned his inquisitiveness to Hilbert’s question which went to the heart of mathematical endeavour. Gödel proved that mathematicians could never prove that they had the secure foundations Hilbert had craved. It was impossible to use the axioms of mathematics to prove that these axioms would never lead to contradictions. Perhaps the problem could be rectified by changing the axioms or adding more axioms? That wouldn’t work. Gödel showed that whatever axioms one chose for mathematics, they could never be used to prove that contradictions would never arise.
Mathematicians call a collection of axioms consistent if they don’t lead to contradictions. It might be true that the axioms one has chosen never produce contradictions, but one can never prove that by using those same axioms. It might be possible to prove the consistency from some other collection of axioms, but that would be only a partial victory because then the consistency of that other choice of axioms is equally questionable. It is like Hilbert’s attempt to prove that geometry is consistent by turning geometry into a theory of numbers. It only led to the question about the consistency of arithmetic.
Gödel’s realisation is reminiscent of the description of the universe provided by a little old lady at the beginning of Stephen Hawking’s A Brief History of Time. The lady stands up at the end of a popular astronomy lecture and declares, ‘What you have told us is rubbish. The world is really a flat plate supported on the back of a giant tortoise.’ Her reply to the lecturer’s question as to what the tortoise is sitting on would have brought a smile to Gödel’s face: ‘You’re very clever, young man, very clever. But it’s turtles all the way down.’
Gödel had provided mathematics with a proof that the mathematical universe was built on a tower of turtles. One can have a theory without contradictions but one can’t prove that within that theory there won’t be contradictions. All one can do is to prove the consistency within another system whose own consistency could not be proved. It was ironic that mathematics could be used to prove that proof itself is limited in what it can deliver. The French mathematician André Weil summed up the situation post-Gödel with the following nugget: ‘God exists since mathematics is consistent, and the Devil exists since we cannot prove it.’
Hilbert had declared in 1900 that in mathematics there was no ‘unknowable’. Thirty years later, Gödel had proved that ignorance is an integral part of mathematics. Hilbert learnt about Gödel’s bombshell some months after his day in Königsberg. He was apparently ‘somewhat angry’ upon hearing the news. Hilbert’s declaration ‘Wir müssen wissen. Wir werden wissen’, made the day after Gödel’s announcement, found its appropriate resting place. It was inscribed on Hilbert’s gravestone, an idealistic dream from which mathematics had finally awoken.
At a time when physicists were learning from Heisenberg’s Uncertainty Principle that there were limits to what physicists could know, Gödel’s proof meant that mathematicians would always have to live with their own uncertainty: that they might suddenly discover that the whole of mathematics was a mirage. Of course, for most mathematicians the fact that this hasn’t happened yet is the best justification for why it won’t happen. We have a working model that seems to justify the consistency. But since the model is ultimately infinite, we can’t be sure that somewhere along the line the model will not contradict our axioms. And as we have discovered, things as innocent as prime numbers can hide surprises in distant stretches of the universe of numbers, surprises which would never have been stumbled upon by experiment and observation alone.
Gödel did not stop there. His dissertation contained a second bombshell. If the axioms of mathematics are consistent, then there will always be true statements about numbers which cannot formally be proved from the axioms. This went against the whole ethos of what mathematics had meant since the time of the ancient Greeks. Proof had always been considered the pathway to mathematical truth. Now Gödel had blown this faith in the power of proof out of the water. Some hoped that by adding new axioms it might be possible to patch up the mathematical edifice. But Gödel showed that such efforts were in vain. However many new axioms one adds to the mathematical foundations, there will always remain some true statements without proofs.
This was named Gödel’s Incompleteness Theorem – any consistent axiom system is necessarily incomplete in that there will be true statements that can’t be deduced from the axioms. And to assist him in this act of mathematical terrorism he enlisted the help of none other than the prime numbers. Gödel used the primes to give each mathematical statement its own individual code number, called the Gödel number. By analysing these numbers Gödel could show that for any given choice of axioms there would always exist true statements that could not be proved.
Gödel’s result was a major body blow to mathematicians everywhere. There were so many statements about numbers, and especially prime numbers, which appeared to be true but we had no idea how to prove. Goldbach: that every even number is the sum of two prime numbers; Twin Primes: that there are infinitely many primes differing by 2, such as 17 and 19. Were these going to be statements that we couldn’t prove from the existing axiomatic foundations?
There is no denying that it was an unnerving state of affairs. Maybe the Riemann Hypothesis was simply unprovable within our current axiomatic description of what we think we mean by arithmetic. Many mathematicians consoled themselves with the belief that anything that is really important should be provable, that it is only tortuous statements with no valuable mathematical content that will end up being one of Gödel’s unprovable statements.
But Gödel was not so sure. In 1951, he questioned whether our current axioms were sufficient for many of the problems of number theory:
One is faced with an infinite series of axioms which can be extended further and further, without any end being visible … It is true that in the mathematics of today the higher levels of this hierarchy are practically never used … it is not altogether unlikely that this character of present-day mathematics may have something to do with its inability to prove certain fundamental theorems, such as, for example, Riemann’s Hypothesis.
Gödel believed that mathematics had failed to prove the Riemann Hypothesis because its axioms are not sufficient to explain the Hypothesis. We might have to broaden the base of the mathematical edifice to discover a mathematics in which we can solve this problem. Gödel’s Incompleteness Theorem drastically altered people’s mindsets. If problems were so impossible to answer, like Goldbach’s and Riemann’s, maybe they were simply unprovable with the logical tools and axioms that we were bringing to bear on them.
At the same time, we should be careful not to overemphasise the significance of Gödel’s result. This was not the death knell of mathematics. Gödel had not undermined the truth of anything that had been proved. What his theorem showed was that there’s more to mathematical reality than the deduction of theorems from axioms. Mathematics was more than a game of chess. There would be an ongoing evolution of the foundations of mathematics in parallel with the continued construction of the edifice above. In contrast to the formal nature of the construction above the base, the evolution of the foundations would rely on the intuition of mathematicians as to what new axioms they believed best described the world of mathematics. Many were happy to celebrate Gödel’s Theorem as confirmation of the superior nature of the mind over the mechanistic spirit that had emerged from the Industrial Revolution.
Turing’s miraculous machine of the mind
Gödel’s revelation had opened up a whole new question which began to fascinate both Hilbert and the young Turing. Was there some way to tell the difference between true statements which have proofs and those Gödel statements which, although true, had no proofs? Turing, in his pragmatic manner, began to contemplate the possibility of a machine which could rescue mathematicians from the uncertainty of trying to prove an unprovable statement. Was it possible to conceive of a machine that would decide whether any statement fed into it could be deduced from the axioms of mathematics even if it didn’t actually produce the proof? We could use such a machine like some Delphic oracle to reassure ourselves that it is at least worth trying to find a proof of Goldbach’s Conjecture or the Riemann Hypothesis.
The question of the existence of such an oracle was not so dissimilar to the tenth question that Hilbert had posed at the dawn of the century. In that problem, Hilbert had speculated that there might exist a universal method or algorithm which could decide whether any equation had solutions or not. He was getting at the idea of a computer program before the idea of a computer had really been put forward. He envisaged a mechanical procedure which could be applied to the equation and answer ‘yes’ or ‘no’ to the question ‘Does this equation have solutions?’ without the need for any personal intervention by an operator.
All this talk of machines was purely theoretical. No one was yet contemplating an actual physical object. These were machines of the mind – methods or algorithms for producing answers. It was like coming up with the idea of software before there was any hardware on which to implement it. Even if Hilbert’s machine existed it would still be useless in practice, because the amount of time the machine would need to establish whether any equation had solutions would most likely far exceed the lifetime of the universe. For Hilbert, the existence of this machine was of philosophical importance.
The idea of such theoretical machines horrified many mathematicians. They would effectively put the mathematician out of business. No longer would we need to rely on the imagination, on the cunning intuition of the human mind to produce clever arguments. The mathematician could be replaced by a mindless automaton which would bludgeon its way through new problems without the slightest need for subtle new modes of thought. Hardy was adamant that no such machine could exist. The very thought of one threatened his whole existence:
There is of course no such theorem and this is very fortunate, since if there were we should have a mechanical set of rules for the solution of all mathematical problems, and our activities as mathematicians would come to an end. It is only the very unsophisticated outsider who imagines that mathematicians make discoveries by turning the handle of some miraculous machine.
Turing’s fascination with the complexities of Gödel’s ideas stemmed from a series of lectures given in the spring of 1935 by Max Newman, one of the mathematics dons in Cambridge. Newman had been captivated by Hilbert’s questions when he heard the great Göttingen mathematician speaking during the International Congress of Mathematicians in Bologna in 1928. It was the first time since the First World War that a delegation from Germany had been invited to an International Congress. Many German mathematicians refused to attend, still outraged that they had been excluded from the previous Congress in 1924. But Hilbert rose above such political divisions, and headed a delegation of sixty-seven German mathematicians. As he entered the hall to hear the opening session, the audience rose to its feet and applauded him. He responded with a view shared by many mathematicians: ‘It is a complete misunderstanding of our science to construct differences according to peoples and races and the reasons for which this has been done are very shabby ones. Mathematics knows no races … for mathematics, the whole cultural world is a single country.’
As soon as Newman learnt in 1930 that Hilbert’s programme had been comprehensively demolished by Gödel, he was keen to explore some of the complexities of Gödel’s ideas. Five years later he felt confident enough to announce a series of lectures on Gödel’s Incompleteness Theorem. Turing sat in the lectures, transfixed by the twists and turns of Gödel’s proof. Newman ended with the question that would act as a catalyst for both Hilbert and Turing’s imagination. Could one in some way distinguish between statements that had proofs and those that didn’t? Hilbert christened the question ‘the Decision Problem’.
As he listened to Newman lecturing on Gödel’s work, Turing became convinced that it was impossible to construct a miraculous machine that could make these distinctions. But it was going to be difficult to prove there could never be any such machine. After all, how can you know what the limitations of human ingenuity are going to be in the future? You might be able to prove that one particular machine won’t produce answers, but to extend that to all possible machines was to deny the unpredictability of the future. Yet Turing did.
This was Turing’s first great breakthrough. He came up with the idea of special machines that could effectively be made to behave like any person or machine that was doing arithmetic computations. They would later be known as Turing machines. Hilbert had been rather vague about what he meant by a machine that could tell whether statements could be proved. Now, thanks to Turing, Hilbert’s question had been put into focus. If one of Turing’s machines could not distinguish the provable from the unprovable, then no other machine could. So were his machines powerful enough to meet the challenge of Hilbert’s Decision Problem?
While he was out one day, running along the banks of the River Cam, Turing experienced the second flash of enlightenment that told him why none of these Turing machines could be made to distinguish between statements that had proofs and those that didn’t. As he paused for a breather, lying on his back in a meadow near Granchester, he saw that an idea which had been used successfully to answer a question about irrational numbers might be applicable to this question about the existence of a machine to test for provability.
Turing’s idea was based on a startling discovery made in 1873 by Georg Cantor, a mathematician from Halle in Germany. He had found that there were different sorts of infinities. It may seem a strange proposition, but it is actually possible to compare two infinite sets and say that one is bigger than the other. When Cantor announced his discovery, in the 1870s, it was considered almost heretical or at best the ramblings of a madman. To compare two infinities, imagine a tribe that has a counting system that goes ‘one, two, three, lots’. They can still judge who is the richest member of the tribe, even though the exact numerical value of that wealth cannot be discerned. If chickens are the sign of a person’s wealth, then two people just need to pair up each other’s chickens. Whoever runs out of chickens first is clearly the poorer of the two. They don’t need to be able to count their chickens to see that one collection outstrips another.
Using this idea of pairing objects, Cantor showed that if you compare all the whole numbers against all the fractions (such as 
) the members of the two sets can be paired off exactly. This seems counterintuitive, since there would appear to be many more fractions than whole numbers. Yet Cantor found a way to establish a perfect match, with no fractions left without partners. He also produced a cunning argument to show that, in contrast, there was no way to match all fractions with all real numbers, which include irrational numbers such as π and 
, and numbers with a non-repeating decimal expansion. Cantor showed that any attempt to pair the fractions with the real numbers would necessarily miss some number with an infinite decimal expansion. Here, then, were two infinite sets which Cantor could show were of different sizes.
Hilbert recognised that Cantor was creating a genuinely new mathematics. He declared Cantor’s ideas on infinities to be ‘the most astonishing product of mathematical thought, one of the most beautiful realisations of human activity in the domain of the purely intelligible … no one shall expel us from the paradise which Cantor has created for us.’ In recognition of Cantor’s pioneering ideas he dedicated the first problem on his list of twenty-three to a question posed by Cantor: Is there an infinite set of numbers bigger than the set of fractions but smaller than the set of all real numbers?
It was Cantor’s demonstration that infinite decimals outnumber fractions that had raced through Turing’s mind as he lay soaking up the Cambridge sun. He suddenly realised why this fact could be used to show that Hilbert’s dream of a machine that could check whether a statement had a proof was pure fantasy.
Turing started by supposing that one of his machines could decide whether any true statement had a proof. By an elegant method, Cantor had shown that some decimal numbers would always be left over, however the fractions were matched with the real numbers. Turing took this technique and used it to produce a ‘left-over’ true statement for which the Turing machine could not possibly decide whether a proof existed. The beauty of Cantor’s argument was that if you tried to adapt the machine to include this missing statement, there would always be another statement that had been missed, just as Gödel’s proof of the Incompleteness Theorem showed that adding another axiom would only lead to some new unprovable statement.
Turing could see that it was rather a slippery argument that he was proposing. As he ran back to his rooms in King’s College, he turned it over in his mind, probing for any weaknesses. There was one point that worried him. He had shown that none of his Turing machines could answer Hilbert’s Decision Problem. But how could he convince people that there wasn’t some other machine that could answer Hilbert’s problem? This was his third breakthrough: the idea of a universal machine. He drew up a blueprint for a single machine that could be taught to behave like all of his Turing machines or like any other machine that might answer Hilbert’s problem. He was already beginning to understand the power of a program that could teach this universal machine to behave like any other machine capable of answering Hilbert’s question. The brain was also a machine that might be able to decide between the provable and unprovable, and this stimulated Turing’s later investigations into whether a machine was capable of thinking. For now, he focused on checking all the details of his proposed solution to Hilbert’s question.
For a year Turing laboured away, making sure his argument held water. He knew that, when he presented it, it would be subjected to the utmost scrutiny. He decided that the best person to try it out on was the man who had explained the problem to him in the first place: Newman. At first, Newman felt rather uneasy about the argument. It looked as though there was the potential for tricking oneself into thinking something was true when it wasn’t. But as Newman turned and turned the argument he became more convinced that Turing had got it. But they were to discover that Turing wasn’t the only one to have got it.
Turing learned that he had been pipped at the post by one of the mathematicians in Princeton. Alonzo Church had reached the same conclusion at almost the same time as Turing, but had been fastest to publicise his discovery. Turing was naturally concerned that his bid for recognition in the tough academic jungle was going to be thwarted by Church’s announcement. But with the support of Newman, his mentor in Cambridge, Turing’s own proof was accepted for publication. To Turing’s dismay, it received little recognition at the time it was published. However, his idea of a universal machine was more tangible than Church’s method, and much more far-reaching in its consequences. Turing’s addiction for real-life inventions had infused his theoretical considerations. Although the universal machine was only a machine of the mind, his description of it sounded like the plan for an actual contraption. A friend of his joked that if it were ever built it would probably fill the Albert Hall.
The universal machine marked the dawn of the computer age, which would equip mathematicians with a new tool in their exploration of the universe of numbers. Even during his lifetime, Turing appreciated the impact that real computing machines might have on investigating the primes. What he could not have foreseen was the role that his theoretical machine would later play in unearthing one of the Holy Grails of mathematics. Turing’s very abstract analysis of Hilbert’s Decision Problem would become the key, decades later, to the serendipitous discovery of an equation that generates all the primes.
Cogs and pulleys and oil
The next step for Turing was a trip across the Atlantic to visit Church. He hoped he might also get the chance to meet Gödel, who was visiting the Institute for Advanced Study in Princeton. Although theoretical machines were on his mind as he crossed the Atlantic, he hadn’t lost his passion for real equipment. He whiled away the week on the ship by using a sextant to chart its progress.
Turing was disappointed when he arrived in Princeton to find that Gödel had gone back to Austria. Gödel would return two years later to take up a permanent position at the Institute, having fled persecution in Europe. One person Turing did meet in Princeton was Hardy, who happened to be visiting at the same time. Turing wrote to his mother about his encounter with Hardy, ‘At first he was very stand-offish or possibly shy. I met him in Maurice Pryce’s rooms the day I arrived, and he didn’t say a word to me. But he is getting much more friendly now.’
Once he had written up his proof of Hilbert’s Decision Problem for publication, Turing looked around for another big problem to attack. Cracking the Decision Problem would be a hard act to follow. But if you were going to go for another big problem, why not go for the ultimate prize, the Riemann Hypothesis? Turing got his colleague in Cambridge, Albert Ingham, to send him the most recent papers on the Hypothesis. He also began talking to Hardy to see what he thought about it.
By 1937 Hardy was getting more pessimistic about the validity of the Riemann Hypothesis. He’d spent so long trying to prove it, only to keep failing, that he was beginning to think it might actually be false. Turing, influenced by Hardy’s mood in Princeton, believed he could build a machine to prove that Riemann was wrong. He had also heard about Siegel’s discovery of Riemann’s fantastic method for calculating zeros. The formula that Siegel had discovered had made clever use of adding up sines and cosines to efficiently estimate the height of the Riemann landscape. In Cambridge, Turing’s approach to Hilbert’s Decision Problem was regarded as positively industrial in its proposal to create a machine to solve the problem. But Turing realised that machines might also shed light on Riemann’s secret formula. He recognised that there were strong similarities between Riemann’s formula and the ones that were used to predict periodic physical phenomena such as the orbits of planets. In 1936, Ted Titchmarsh, an Oxford mathematician, had already adapted a machine, built originally to calculate celestial motions, to prove that the first 1,041 zeros in the zeta landscape were indeed on Riemann’s ley line. But Turing had seen an even more sophisticated piece of machinery for predicting another periodic natural phenomenon: the tides.
The tides posed a complicated mathematical problem because they depended on calculating the daily cycle of the Earth’s rotation, the monthly cycle of the Moon’s orbit around the Earth, and the yearly cycle of the Earth’s orbit around the Sun. Turing had seen a machine in Liverpool that carried out these calculations automatically. Adding up all the periodic sine waves was replaced by manipulating a system of strings and pulleys, and the answer was indicated by the length of certain sections of the string in the contraption. Turing wrote to Titchmarsh, admitting that when he had first seen the Liverpool machine he had no inkling that it could be used for investigating prime numbers. His mind was now racing. He would build a machine that would calculate the height of the Riemann landscape. This way he might be able to find a point at sea level off Riemann’s critical line and prove the Riemann Hypothesis false.
Turing was not the first to contemplate the use of machinery to speed up tedious computations. The grandfather of the idea of computing machines was another Cambridge graduate, Charles Babbage. Babbage was an undergraduate at Trinity in 1810 and had been as fascinated as Turing with mechanical devices. In his autobiography he recalls the genesis of his idea for a machine to calculate the mathematical tables which were central to England’s abilities to navigate the sea so skilfully:
One evening I was sitting in the rooms of the Analytical Society, at Cambridge, my head leaning forward on the Table in a kind of dreamy mood, with a Table of logarithms lying open before me. Another member, coming into the room, and seeing me half asleep, called out. ‘Well Babbage. what are you dreaming about?’ to which I replied ‘I am thinking about how all these Tables (pointing to the logarithms) might be calculated by machinery.’
It was not until 1823 that Babbage was able to begin to realise his dream of building his ‘Difference Engine’. But the project foundered in 1833 when he fell out with his chief engineer over money. Part of the machine was eventually completed, but it took until 1991, the bicentenary of Babbage’s birth, for his vision to be fully realised. That was when, at a cost of £300,000, a Difference Engine was constructed at the Science Museum in London, where it is still on display.
Turing’s idea for a zeta machine was similar to Babbage’s plan for calculating logarithms with the Difference Engine. The mechanism was specifically tuned to the individual problem it would calculate. This was not one of Turing’s theoretical universal machines that could be made to imitate any computation. The physical properties of the device mirrored the problem, making it useless for attacking other questions. Turing admitted as much in an application he made to the Royal Society for money to start building his zeta machine: ‘Apparatus would be of little permanent value … I cannot think of any application that would not be connected with the zeta-function.’
Babbage himself had appreciated the disadvantages of building a machine that could only calculate logarithms. In the 1830s he was dreaming of a grander machine which could be made to perform a range of tasks. He was inspired by the French Jacquard weaving looms that were being used in mills across Europe. Skilled operators had been replaced by cards punched with holes which, when fed into the loom, controlled the loom’s operation. (Some have grandly referred to these cards as the first computer software.) Babbage was so impressed by Jacquard’s invention that he bought a portrait of the inventor on a silk tapestry woven with the aid of one of these punched cards. ‘The loom is capable of weaving any design which the imagination of man may conceive,’ he marvelled. If this machine could produce any pattern, then why couldn’t he build a machine that could be fed a card to tell it to perform any mathematical computation? His blueprint for the Analytical Engine, as he named it, was a forerunner of Turing’s plan for a universal machine.
It was the poet Lord Byron’s daughter, Ada Lovelace, who recognised the enormous programming potential of Babbage’s machine. While translating into French a copy of Babbage’s paper describing the machine, she couldn’t resist adding some extra notes to extol the machine’s capability. ‘We may say most aptly that the Analytical Engine weaves Algebraic patterns, just as the Jacquard loom weaves flowers and leaves.’ Her notes included many different programs that could be implemented on Babbage’s new machine, even though the machine was purely theoretical and had never been built. By the time she had finished the translation, her additions had become so out of hand that the French version was three times the length of the English edition. Lovelace is generally regarded today as the world’s first computer programmer. She died in great pain of cancer in 1852, aged just thirty-six.
While Babbage was working away on his ideas for machines in England, Riemann was developing his theoretical mathematical concepts in Germany. Eighty years later, Turing hoped to unite these two themes. He had already cut his teeth on the abstract computability of Gödel’s Incompleteness Theorem, which had formed the basis of his thesis. Now he was to turn to the job of cutting physical teeth for the cogs for his zeta machine. He was successful in his application for a grant of £40 from the Royal Society to help build his creation, thanks to Hardy and Titchmarsh’s support.
By the summer of 1939, Turing’s room was ‘a sort of jigsaw puzzle of gear wheels across the floor’, according to Turing’s biographer, Andrew Hodges. But Turing’s dream of a zeta machine that would unite the nineteenth-century English passion for machines with German theory was to be rudely interrupted. The onset of the Second World War saw this burgeoning intellectual unity between the two countries replaced by military conflict. British intellectual forces were rallied at Bletchley Park, and minds turned from finding zeros to cracking codes. Turing’s success in designing machines to crack Enigma owes something to his apprenticeship calculating the zeros of the Riemann zeta function. His complex mesh of interlocking gear wheels hadn’t uncovered the secrets of the primes, but Turing’s new contraptions would prove to be spectacularly successful in revealing the secret movements of the German war machine.
Bletchley Park was a strange mix of the ivory tower and the real world. It was like a Cambridge College, with games of cricket played on the front lawn; for Turing and company, cosseted in their country retreat, the encoded messages that arrived each day were a substitute for doing the Times crossword in a Cambridge common room. A theoretical puzzle – yet they all knew that lives depended on its solution. Given such an atmosphere, it is not surprising that Turing should have continued to think about mathematics while he was helping to win the war.
It was while at Bletchley that Turing came to understand, as Babbage had some hundred years before, that it was better to construct a single machine that could be told to do different tasks rather than build a completely new one for each new problem. Although he already knew this in principle, he was to learn the hard way that this should be implemented in practice too. When the Germans changed the designs of the Enigma machines being used in the field, Bletchley Park was plunged into weeks of silence. Turing realised that the code-breakers needed a machine that could be adapted to cope with any change the Germans might make to their machines.
After the war had finished, Turing began to explore the possibility of building a universal computing machine that could be programmed to perform a multitude of tasks. After several years at Britain’s National Physics Laboratory, he went to work with Max Newman in Manchester at the newly created Royal Society Computing Laboratory. Newman had been alongside Turing in Cambridge during the development of the theoretical machine that had smashed Hilbert’s hope of devising an algorithm to tell whether a true statement had a proof. Now they were to work together to design and build a real machine.
In Manchester, Turing had the time to exploit the technical expertise he had developed cracking codes in Bletchley, even though his wartime activities would remain classified for decades. He returned to the idea that had obsessed him in the days before the war: using machines to explore Riemann’s landscape in the search for counter-examples to the Riemann Hypothesis – zeros off the critical line. But this time, rather than build a machine whose physical properties reflected the problem he was trying to solve, Turing sought to create a program that could be implemented on the universal computer he and Newman were constructing from cathode ray tubes and magnetic drums.
Naturally, theoretical machines run smoothly and effortlessly. Real machines, as Turing had discovered at Bletchley Park, are far more temperamental. But by 1950 he had his new machine up and running and ready to start navigating the zeta landscape. The pre-war record for the number of zeros located on Riemann’s line was held by Hardy’s former student, Ted Titchmarsh. Titchmarsh had confirmed that the first 1,041 points at sea level fulfilled the Riemann Hypothesis. Turing went further and managed to make his machine check as far as the first 1,104 zeros and then, as he wrote, ‘unfortunately at this point the machine broke down’. But it wasn’t only his machines that were breaking down.
Turing’s personal life was beginning to collapse around him. In 1952 he was arrested when the police investigated his homosexuality. He had been burgled and had called the police; the burglar turned out to be an acquaintance of one of Turing’s lovers. The police, as well as chasing the burglar, homed in on Turing’s admission of (as the law then described it) an ‘act of gross indecency’. He was distraught. This could mean jail. Newman testified on his behalf that Turing was ‘completely involved in his work and is one of the most profound and original mathematical minds of his generation’. Turing was spared a prison sentence, on condition that he voluntarily subject himself to treatment by drugs to control his sexual behaviour. He wrote to one of his old tutors in Cambridge, ‘It is supposed to reduce sexual urge whilst it goes on, but one is supposed to return to normal when it is over. I hope they are right.’
On June 8, 1954, Turing was found dead in his room from cyanide poisoning. His mother could not come to terms with the possibility that he had committed suicide. Her son had experimented with chemicals ever since he was a boy, and never washed his hands. She insisted it had been an accident. But by Turing’s bedside lay an apple, with several bites out of it. Although the apple was never analysed, there is little doubt that it was steeped in cyanide. One of Turing’s favourite film scenes was when the witch in Disney’s Snow White and the Seven Dwarfs creates the apple that will put Snow White to sleep: ‘Dip the apple in the brew, let the Sleeping Death seep through.’
Forty-six years after his death, at the dawn of the twenty-first century, rumours began to spread through the mathematical community that Turing’s machines had indeed turned up a counter-example to the Riemann Hypothesis. Yet because the discovery had been made at Bletchley Park during the Second World War on the same machines that had cracked Enigma, British Intelligence had insisted it remain classified. Mathematicians clamoured for the records to be declassified so they could locate Turing’s discovery of a zero off the line. It turned out that the rumour was no more than that, and had been started by one of Bombieri’s friends who shared the Italian’s taste for wicked April Fool’s jokes.
Turing’s machine may have broken down only a short way beyond the pre-war record for zeros, but it had taken the first step into an era in which the computer would take over from the human mind in the exploration of Riemann’s landscape. It would take some time to develop efficient ‘Riemann rovers’, but soon these unmanned explorers would travel farther and farther north along Riemann’s ley line, sending us back more and more evidence – if not final proof – that, contrary to Turing’s belief, Riemann was right.
Although Turing’s real machines had yet to make an impact on the Riemann Hypothesis, his theoretical ideas were to contribute to a strange twist in the story of the primes: the discovery of an equation for generating all the prime numbers. He could never have guessed that this equation would emerge from the devastation that he and Gödel had wrought on Hilbert’s programme to provide mathematics with solid foundations.
From the chaos of uncertainty to an equation for the primes
Turing had proved that his universal machine could not answer all the questions of mathematics. But what about something less ambitious: could it say anything about the existence of solutions to equations? This was the heart of Hilbert’s tenth problem, which in 1948 was beginning to obsess Julia Robinson, a talented mathematician based in Berkeley.
With very few notable exceptions, women have made very few appearances in mathematical history until the last few decades. The French mathematician Sophie Germain corresponded with Gauss, but she pretended to be a man, fearing that if she did not, her ideas would be dismissed out of hand. She had discovered special kinds of prime numbers related to Fermat’s Last Theorem now called Germain primes. Gauss was very impressed with the letters he received from ‘Monsieur le Blanc’ and was amazed when after a lengthy correspondence he discovered that monsieur was a mademoiselle. He wrote back to her:
The taste for the mysteries of numbers is rare … the charms of this sublime science in all their beauty reveal themselves only to those who have the courage to fathom them. But when a woman, because of her sex, our customs, and prejudices … overcomes these fetters and penetrates that which is most hidden, she doubtless had the most noble courage, extraordinary talent and superior genius.
Gauss tried to persuade Göttingen to award her an honorary degree, but Germain died before he could succeed.
In Hilbert’s Göttingen, Emmy Noether was an exceptionally talented algebraist. Hilbert fought on her behalf to overturn archaic rules that denied women positions in German academic institutions. ‘I do not see that the sex of the candidate is an argument against her admission,’ he objected. The University, he declared, was not ‘a bath-house’. Noether, who was Jewish, eventually had to flee Göttingen for the USA. Certain algebraic structures which permeate mathematics are named in her honour.
Julia Robinson was always seen as more than just a gifted mathematician. She was also a woman in the 1960s, and her success encouraged more women to pursue careers into mathematics. Later she recalled how, because she was one of very few women in academia, she would always get asked to complete surveys. ‘I am in everyone’s scientifically selected sample.’
Robinson’s childhood was spent in the Arizona desert. It was a solitary life, with little but a sister and the land for company. Even at an early age she found patterns hidden in the desert. She recalled: ‘One of my earliest memories is of arranging pebbles in the shadow of a giant saguaro, squinting because the sun was so bright. I think I have always had a basic liking for the natural numbers. To me they are the only real thing.’ At the age of nine she fell ill with rheumatic fever and was bedridden for a couple of years.
Such isolation can be a source of inspiration for budding young scientists. Cauchy and Riemann had both escaped into the mathematical world from their real-world physical and emotional problems. Although Robinson didn’t spend her hours confined to bed concocting theorems, she did learn skills that prepared her well for the mathematical battles that lay ahead. ‘I am inclined to think that what I learned during that year in bed was patience. My mother said that I was the stubbornest child she had ever known. I would say that my stubbornness has been to a great extent responsible for whatever success I have had in mathematics. But then, it is a common trait among mathematicians.’
By the time she had recovered from her illness, Robinson had missed two years of school. After a year of private tuition, however, she found herself way ahead of her classmates. On one occasion her tutor explained that the ancient Greeks of two thousand years ago knew that the square root of 2 could not be written exactly as a fraction. Unlike the decimal expansion of a fraction, the decimal expansion of the square root of 2 did not have a pattern which repeated itself. It seemed remarkable to Robinson that someone could prove such a thing. How could you be sure that after millions of decimal places a pattern didn’t emerge? ‘I went home and utilized my newly acquired skills at extracting square roots to check it but finally, late in the afternoon, gave up.’ Despite her failure, she began to appreciate the power of mathematical argument to show convincingly that, however far you calculated the decimal expansion of the square root of 2, no pattern would ever emerge.
It is this power of simple argument that captivates many who turn to mathematics. Here is a problem that brute-force calculation can never solve, even with the aid of the most powerful computer, yet stringing together a few cleverly chosen mathematical ideas will open up the mystery of this infinite decimal expansion. Instead of the impossible task of checking an infinite number of decimals, the task is reduced to a cunning little argument.
When she was fourteen, Robinson started to look for anything about mathematics that might relieve the dry tedium of school arithmetic. She listened eagerly to a radio programme called the University Explorer. She was particularly intrigued by one broadcast which told the story of the mathematician D.N. Lehmer and his son, D.H. Lehmer. The broadcast explained how this mathematical team were attacking mathematical problems with computing machines they were building from bicycle sprockets and chains. The younger Lehmer would be the first to snatch the baton from Turing’s hand, using modern computing machines to show in 1956 that the first 25,000 zeros satisfy Riemann’s Hypothesis. The elder Lehmer described how their pre-war machine ‘would run happily and sweetly for a few minutes and then suddenly become incoherent. Then it would suddenly pull itself together before having another tantrum.’ They eventually traced the cause of the tantrums – a neighbour listening to the radio. Their favourite mathematical problem was finding the prime building blocks of large numbers. Robinson was so excited by the description of these machines that she sent for the transcript of the broadcast.
She found a small item in a newspaper about the supposed discovery of a record prime number which she eagerly cut out. Under the headline FINDS LARGEST NUMBER BUT NOBODY CARES, it reported:
Dr Samuel I. Krieger wore out six pencils, used 72 sheets of legal size note paper and frazzled his nerves quite badly but he was able to announce today that 231,584,178,474,632,390,847,141,970,017,375,815,706,539,969, 331,281,128,078,915,826,259,279,871 is the largest known prime number. He was unable to say offhand who cared.
Perhaps the lack of interest reflects the fact that this number is actually divisible by 47 (as the newspaper would have discovered, had it checked). Robinson kept the clipping for the rest of her life, along with the script about the Lehmers’ calculating machine and a pamphlet she acquired about the mysteries of the fourth dimension.
The groundwork had been laid for Robinson’s mathematical career. She took her degree in mathematics at San Diego State College, then made her way to the University of California at Berkeley where her passion for number theory was awakened by a lecturer whom she would later marry, Raphael Robinson. Whilst they were still dating, Raphael found that mathematics was the way to Julia’s heart. He started bombarding her with explanations of all the latest mathematical breakthroughs.
One discovery that particularly intrigued Julia was Raphael’s description of Gödel and Turing’s results. ‘I was very impressed and excited by the fact that things about numbers could be proved by symbolic logic,’ she said. Despite the unsettling nature of Gödel’s results, she still held firm to the sense of reality of numbers that she had acquired as a child playing with pebbles in the desert. ‘We can conceive of a chemistry that is different from ours, or a biology, but we cannot conceive of a different mathematics of numbers. What is proved about numbers will be a fact in any universe.’
Although she was blessed with a great mathematical ability, she admitted that without the support of her husband she would have found it hard to continue doing mathematics at a time when most women found it difficult to sustain an academic career. University rules at Berkeley meant that husband and wife could not be members of the same department. In recognition of her research ability, a position was created for her in statistics. The job description she submitted to personnel to accompany her application is a classic description of most mathematicians’ working week: ‘Monday – tried to prove theorem, Tuesday – tried to prove theorem, Wednesday – tried to prove theorem, Thursday – tried to prove theorem, Friday – theorem false.’
Her interest in Gödel and Turing’s work was fuelled by the chance to study with one of the great logicians of the twentieth century, Alfred Tarski, a Pole who had found himself stranded by the onset of war during a visit in 1939 to Harvard. Robinson, however, didn’t want to lose sight of her passion for number theory. The tenth of Hilbert’s problems presented the perfect blend of both subjects: Is there an algorithm – in computing terms, a program – that could be used to show whether any equation has a solution?
In the light of Gödel and Turing’s work, it was becoming clear that, contrary to Hilbert’s initial belief, there probably wasn’t such a program. Robinson felt sure that there should be a way to exploit the groundwork laid by Turing. She understood that each Turing machine gives rise to a sequence of numbers. For example, one of the Turing machines could be made to produce a list of the square numbers 1, 4, 9, 16, …, whilst another generated the primes. One of the steps in Turing’s solution of Hilbert’s Decision Problem had been to prove that no program existed that could decide whether, given a Turing machine and a number, that number is the output of the machine. Robinson was looking for a connection between equations and Turing machines. Each Turing machine, she believed, would correspond to a particular equation.
If there were such a connection, Robinson hoped that asking whether a number was the output of a particular Turing machine would translate into asking whether the equation corresponding to that machine had a solution. So if she could establish such a connection, she would be home. If there existed a program to test equations for solutions, as Hilbert was hoping for when he posed his tenth problem, then the same program could be used, via Robinson’s as yet hypothetical connection between equations and Turing machines, to check which numbers were outputs of Turing machines. But Turing had shown that no such program – one that could decide about the outputs of Turing machines – existed. Therefore there could be no program that could decide whether equations had solutions. The answer to Hilbert’s tenth problem would be ‘no’.
Robinson set about understanding why each Turing machine might have its own equation. She wanted an equation whose solutions were connected to the sequence of numbers output by the Turing machine. She was rather amused by the question she had set herself. ‘Usually in mathematics you have an equation and you want to find a solution. Here you were given a solution and you had to find the equation. I liked that.’ As Robinson grew older, the interest that had been sparked in 1948 turned to obsession. After her illness at the age of nine, doctors predicted that her heart had been weakened to such an extent that she might not live beyond forty. Every birthday, ‘when it came time for me to blow out the candles on my cake, I always wished, year after year, that the Tenth Problem would be solved – not that I would solve it, but just that it would be solved. I felt that I couldn’t bear to die without knowing the answer.’
As each year passed she made more progress. She was joined in her quest by two other mathematicians, Martin Davis and Hilary Putnam. By the end of the 1960s they had reduced the problem to something simpler. Rather than having to find all equations for all outputs of Turing machines, they discovered that if they found an equation for one particular sequence of numbers, they would have proved Robinson’s hunch. It was a remarkable achievement. Everything came down to finding the equation for this one sequence of numbers. Their whole theory now relied on them being able to confirm the existence of a single brick in their mathematical wall. If it turned out that this sequence didn’t have its own Robinson equation, then the whole wall they had spent so long building would collapse.
There was growing scepticism that Robinson’s approach was the right way to attack Hilbert’s tenth problem. A number of mathematicians were complaining that it was misguided. Then suddenly, on February 15, 1970, Robinson got a phone call from a colleague who had just returned from a conference in Siberia. There had been a very exciting talk which he thought Robinson would be interested in. A twenty-two-year-old Russian mathematician called Yuri Matijasevich had found the last piece of the jigsaw and solved Hilbert’s tenth problem. He had shown that there was an equation that would produce the sequence as Robinson had predicted. That was the brick upon which the whole of Robinson’s approach relied. The solution to Hilbert’s tenth problem was complete: a program that could decide whether equations had solutions did not exist.
‘That year when I went to blow out the candles on my cake, I stopped in mid-breath, suddenly realizing that the wish I had made for so many years had actually come true.’ Robinson saw that the solution had been under her nose all the time, but it had taken Matijasevich to spot it. ‘There are lots of things, just lying on the beach as it were, that we don’t see until someone else picks one of them up. Then we all see that one,’ she explained. She wrote to congratulate Matijasevich: ‘I am especially pleased to think that when I first made the conjecture you were a baby and I just had to wait for you to grow up.’
It is striking how mathematics has the ability to unite people across political and historical boundaries. Despite the difficulties posed by the Cold War, these American and Russian mathematicians would forge a strong friendship upon their obsession with Hilbert’s inspirational problem. Robinson described this strange bond between mathematicians as being like ‘a nation of our own without distinction of geographical origins, race, creed, sex, age or even time (the mathematicians of the past and of the future are our colleagues too) – all dedicated to the most beautiful of the arts and sciences’.
Matijasevich and Robinson would fight over credit for the proof, but not for self-aggrandisement – rather, each insisted that the other had done the hardest bit. It is true that, because Matijasevich ended up putting in the last piece of the jigsaw, the solution of Hilbert’s tenth problem is often attributed to him. The reality of course is that many mathematicians contributed to the long journey from Hilbert’s announcement in 1900 to the final solution seventy years later.
Although the problem had been solved in the negative – namely, there was no program that could be used to tell whether any equations had solutions – there was a silver lining. Robinson had been proved right in her belief that lists of numbers produced by Turing machines could be described by equations. Mathematicians knew that there was one Turing machine that could reproduce the list of prime numbers. So, thanks to the work of Robinson and Matijasevich, in theory there had to be a formula that could output all the primes.
But could mathematicians find such a formula? In 1971, Matijasevich devised an explicit method for arriving at such a formula, but he did not follow it through to produce an answer. The first explicit formula to be written out in detail used 26 variables, from A to Z, and was discovered in 1976:
This formula works like a computer program. You randomly change the letters A, …, Z into numbers and then use the formula to perform a calculation on those numbers; for example, you might choose A = 1, B = 2, …, Z = 26. If the answer is bigger than zero, then the result of the calculation is prime. You can go on repeating the process, assigning different choices of numbers to the letters and redoing the calculation. By systematically going through every possible choice of numbers for the letters A, …, Z, you will be guaranteed to produce all prime numbers. No prime number is missed by the formula: there is always some way to choose the numbers A, …, Z so that the equation will produce the prime in question. There is one piece of small print: some choices of A, …, Z give a negative answer, and we just have to ignore them. Our choice of A = 1, B = 2, …, Z = 26, for example, is one such choice that we must sweep under the carpet.
Wasn’t this the Holy Grail at the end of the quest – the discovery that this extraordinary polynomial will generate the primes? Had this equation been found in Euler’s day, it would certainly have been great news. Euler had discovered an equation which had successfully produced lots of primes, but he had been quite pessimistic about the chance of finding an equation which could produce all the primes. But since Euler’s day, mathematics had moved on from the mere study of equations and formulas to embrace Riemann’s belief in the importance of the underlying structures and themes running through the mathematical world. Mathematical explorers were now busy charting passageways to new worlds. The discovery of this prime number equation was a result born into the wrong age. To the new generation of mathematicians, the equation was like a very technical survey of a land explored years ago and now abandoned. Mathematicians were rather surprised that such an equation existed, but Riemann had moved the study of the primes onto a different plane. A classical symphony in the style of Mozart written and performed in the time of Shostakovich would not have impressed audiences, even if it had attained some perfection of style.
But it wasn’t just the new mathematical aesthetic that muted the reception given to this miraculous equation. The truth is, it was practically useless. Most of the values of this equation are negative. Even theoretically it is somewhat lacking in significance. Robinson and Matijasevich had shown that any list of numbers that can be produced by a Turing machine will have such an equation, so in that sense there is nothing special about the primes as opposed to any other list of numbers. This was a view shared by many at the time. When someone told the Russian mathematician Yu. V. Linnik about Matijasevich’s result on primes, he replied, ‘That’s wonderful. Most likely we soon shall learn a lot of new things about primes.’ When it was explained to him how the result had been proved and that it applied to many sequences of numbers, he retracted his earlier enthusiasm. ‘It’s a pity. Most likely we shall not learn anything new about primes.’
If the existence of such an equation is universally true for any sequence of numbers, it tells us nothing specific about the primes. This is what makes Riemann’s interpretation so much more intriguing. The existence of Riemann’s landscape and the notes he created from each point at sea level is music utterly unique to the primes. You won’t find this harmonic structure underlying just any sequence of numbers.
While Robinson was putting paid to the tenth of Hilbert’s problems, a friend of hers in Stanford was demolishing Hilbert’s belief that in mathematics there is no unknowable. As a student in 1962, Paul Cohen had rather arrogantly asked his professors in Stanford which of Hilbert’s problems would make him famous if he could solve it. They thought for while, then told him that the first was one of the most important. In crude terms, it was asking how many numbers there are. To head his list, Hilbert had chosen Cantor’s question about different infinities. Is there an infinite collection of numbers which is bigger in size than the set of all fractional numbers, yet small enough that they can’t be paired with all the real numbers – including irrational numbers such as π, √2 or any number with an infinite decimal expansion?
Hilbert probably turned in his grave when Cohen returned a year later with the solution: both answers are possible! Cohen proved that this most basic of questions was one of Gödel’s unprovable sentences. Gone, then, was any hope that only obscure problems were undecidable. What Cohen had proved was this: it was impossible to prove, on the basis of the axioms we currently use for mathematics, that there is a set of numbers whose size is strictly between the number of fractions and the number of all real numbers; equally, it can’t be proved that there isn’t such a set. Indeed, he had managed to build two different mathematical worlds which satisfied the axioms we are using for mathematics. In one of those worlds the answer to Cantor’s question was ‘yes’; in the other world it was ‘no’.
Some people compare Cohen’s result to Gauss’s realisation that there are different geometries, not just the geometry of the physical world around us. In some sense this is true. But the point is that mathematicians have a strong sense of what they mean by numbers. Sure, the axioms used for proving things about these numbers might also be satisfied by other ‘supernatural’ numbers. Nevertheless, most mathematicians still believe that Cantor’s question has just one answer that is true for the numbers with which we construct our mathematical edifice. Robinson summed up the response of most mathematicians to Cohen’s proof when she exclaimed in a letter she was writing to him, ‘For heaven’s sake there is only one true number theory! It’s my religion.’ But she crossed out the last sentence before sending the letter to Cohen.
Cohen’s groundbreaking work, unsettling as it was to the mathematical orthodoxy, earned him a Fields Medal. After his remarkable discovery that we can’t decide the answer to Cantor’s question from the classical axioms of mathematics he decided that he would move on to what he considered to be the next most challenging problem on Hilbert’s list: the Riemann Hypothesis. Cohen has been one of the few mathematicians to admit that he was actively working on this notoriously difficult problem. So far, though, it has held firm against his attack.
Intriguingly, the Riemann Hypothesis is in a different category to Cantor’s question. If Cohen has the same success and proves that the Riemann Hypothesis is undecidable from the axioms of mathematics, he will have shown that the Hypothesis is in fact true! If it is undecidable, then either it is false and we can’t prove it, or it is true and we can’t prove it. But if it is false then there is a zero off the critical line which we can use to prove it is false. It can’t be false without us being able to prove it is false. So, the only way the Riemann Hypothesis can be undecidable is if it is true but we still can’t find a proof that all the zeros are on the critical line. Turing was one of the first to see the possibility of such a strange confirmation of Riemann’s Hypothesis. But few believe that logistic trickery of this nature will be successful in answering Hilbert’s eighth problem.
Computers of the mind had played a critical role in our understanding of the mathematical world, thanks to Turing’s universal machine. But it was the physical machines he had tried to build that would be in the ascendancy in the second half of the twentieth century. The tide changed in favour of computers made of valves, wires and ultimately silicon, not of neurones and infinite memories. All around the world, machines were built that would allow mathematicians to stare deep into the universe of numbers.