"Wir müssen wissen. Wir werden wissen." (We must know. We shall know.)
David Hilbert, Königsberg, 8 September 1930
The story so far has a shape to it, and the shape is misleading. Babbage dreamed of a calculating engine. Lovelace saw that it could manipulate symbols. Boole reduced logic to algebra. Shannon etched the algebra into circuits. It looks like a staircase: one mind building on the last, each step leading to the next, all of it converging neatly toward the computer.
It was not a staircase. It was two separate paths, built by people who had never heard of each other, converging on the same destination from opposite directions.
One path was engineering. Babbage wanted to build a machine that could calculate. So did Percy Ludgate, an accountant in Dublin who designed a general-purpose computer in his spare time in 1909, working alone at night, initially unaware that Babbage had ever existed. So did Leonardo Torres y Quevedo, a Spanish engineer who built a genuine chess-playing automaton in 1912, proposed floating-point arithmetic in 1914, and demonstrated that every cogwheel in a Babbage-type machine could be replaced with electromechanical parts. So did Konrad Zuse, a German civil engineering graduate so bored by the tedium of hand calculations at an aircraft factory that he built a programmable computer in his parents' living room in Berlin, using punched movie film for instructions, and completed it in 1938. Zuse had never heard of Babbage. He had never heard of Turing. His Z3, finished in 1941, was the first working programmable, fully automatic digital computer on earth, electromechanical rather than electronic, built from two thousand telephone relays, and it was destroyed by Allied bombs in 1943, along with almost everything he had built. He rescued his Z4 by moving it to an Alpine village and hiding it there until the war ended.
These engineers were trying to make machines that calculated faster. They were not asking whether there were things a machine could never calculate. That question came from the other path.
The other path was pure mathematics. It had nothing to do with gears or circuits or switches. It began with a question about the foundations of mathematics itself, asked by a man who was certain the answer was yes.
David Hilbert was the dominant mathematician of his generation, and possibly the most optimistic human being who ever held a professorship. He was born in Konigsberg, Prussia, in 1862, and by the turn of the century he had made Gottingen the mathematical capital of the world. In 1900, at the International Congress of Mathematicians in Paris, he stood before the assembled profession and listed twenty-three unsolved problems that he believed would shape the next century of mathematics. He was right. They did.
But Hilbert wanted more than a list of problems. He wanted a guarantee. His programme, as it came to be known, had three goals: find a complete set of axioms for all of mathematics. Prove that those axioms are consistent, that they can never produce a contradiction. And then find a mechanical procedure, an algorithm (the word that traces back to al-Khwarizmi's ninth-century treatise), to determine the truth or falsehood of any mathematical statement whatsoever.
This last goal was the Entscheidungsproblem, the decision problem, posed formally by Hilbert and Wilhelm Ackermann in 1928. Does there exist an algorithm that can take any statement in formal logic and determine whether it is true? If the answer was yes, then mathematics was a closed, perfect system: every question had an answer, and the answer could be found by following a procedure. Hilbert believed this with something close to religious conviction.
On 8 September 1930, in Konigsberg, the city where he was born, Hilbert delivered his retirement address. It was four minutes long. He declared: "Wir mussen wissen, wir werden wissen." We must know. We shall know. The words were later engraved on his tombstone.