The bright, late-summer sun beat down on the regal statue of Neptune dominating the Piazza Nettuno in the center of Bologna, Italy, home of the world’s oldest university. Neptune seemed to be casting a skeptical eye on the slight, professorial-looking figure in the floppy panama hat and the spade beard sitting at one of the outdoor cafes bordering the square, nursing the last few drops of his afternoon cappuccino. Neither Neptune nor any of the voluble Italians standing in clusters in the square knew that this little man of no apparent consequence staring off into the distance was David Hilbert, probably the most important mathematician of the day. As he finished his coffee and brushed the crumbs of an almond cake off his vest, Hilbert thought once more

about the address he would give the next morning to open the International Congress of Mathematicians (ICM) at Bologna University. Hilbert wanted to set the tone of the gathering by focusing the attention of the world’s mathematical community on the puzzles he had grappled with for decades and which lay at the very heart of mathematics, puzzles about the logical consistency and completeness of the subject that gives mathematical results the ring of truth found in no other field of intellectual pursuit.

In 1900, at the ICM in Paris that inaugurated the new century, Hilbert, already one of the world’s most famous mathematicians, gave an address in which he presented a list of 23 problems that he felt were important for the development of mathematics in the coming century. Now he thought again about the second problem on his list, the one that dealt with the reliability of mathematical reasoning. The mathematical way of getting at the scheme of things—truth or falsity of statements about numbers or other mathematical objects—is deductive. This mode of argumentation begins with a small number of statements taken to be true without benefit of proof, the so-called “axioms” of the logical system used to prove or disprove statements. The rules of logical inference are then used to deduce new true statements—theorems—from the axioms. In his second problem stated at the ICM meeting in 1900, Hilbert wondered whether it was possible to actually prove that the axioms themselves were free of contradictions. In other words, given a set of axioms, can it be shown that both a statement and its negation can never be derived by logical deduction from these axioms? If that is the case, the axioms are termed consistent. Many years earlier, logicians had shown that if the axioms of a system are inconsistent, any statement can be proved. So for a logical system to be useful in separating true from false statements, the bare minimal requirement is that it be consistent.

“Perhaps the Signor would care for another cappuccino?” said the waiter, gliding up to Hilbert’s table like an apparition out of the blue. Jerked back to the world of the piazza, Hilbert shook his head and the waiter drifted away as ghostly as he’d arrived. Well, thought Hilbert, I can’t sit daydreaming about these matters. I simply must go back to the hotel and go over my notes one more time.

Dropping a few coins on the table for his cappuccino, Hilbert left the cafe and strolled through the lovely arcades surrounding the piazza, reflecting again on the obvious fact that the consistency of a set of axioms is only a special case of the general problem of the provability of any given mathematical statement. Is there a completely mechanical procedure, a kind of mathematical “truth machine” into which any given statement can be inserted, the machine then producing the answer, Yes or No, as to the provability of the statement?

The fast-talking, fast-walking Bolognese who were scurrying through Piazza Nettuno that day could not have guessed that the little man in the strange hat absentmindedly strolling through the piazza was a revolutionary. But by posing the question the next day, Hilbert would throw down a challenge to the mathematical community that would lead to a revolution in our understanding of the limits to human reasoning. Put simply, Hilbert’s manifesto would assert that every possible mathematical statement could be settled, true or false. As he put the matter a few years later at his retirement address, “We must know. We will know.” But the brilliant Hilbert was wrong! Mathematical reasoning, it turns out, is simply incapable of deciding all statements, even in such a restricted domain of discourse as that of the whole numbers.

The four men sat at a corner table in the Café Reichsrat,

tucked away behind Vienna’s City Hall, near the main building of the University of Vienna. The group was talking excitedly and joking among themselves about the upcoming trip to the Second Conference on the Epistemology of the Exact Sciences (EES), which was scheduled to begin in a few days in Königsberg, Germany. The graybeard of the group, 39-year-old logician and philosopher Rudolf Carnap, asked the youngest, 24-year-old Kurt Gödel, about the work he would present at the meeting.

Gödel, slender and shy, looked over at Carnap through thick, round, pebble-style spectacles that gave him the appearance of some type of exotic fish, swimming to look out through the wall of an aquarium. Staring at Carnap, Gödel replied, “I’ll present my work on the existence of undecidable propositions in any logical system that’s at least as strong as the system used by Russell and Whitehead in Principia Mathematica. I’ve discovered that every consistent logical system contains propositions that can be neither proved nor disproved within the framework of that system.”

Astonished at what Gödel had just told him, Carnap gasped, “The consequence of this result for Hilbert’s program for proving the reliability of mathematics are devastating! You’ve shown that the entire program outlined by Hilbert was misconceived at the very outset.” So, thought Carnap, mathematics is riddled with just as many logical holes and gaps as any other human intellectual undertaking. He smiled to himself as he imagined the shockwaves that would ripple through the philosophical and mathematical community at this result.

“Hilbert will be speaking at the meeting of the Society of German Scientists and Physicians immediately following our meeting,” noted Friedrich Waismann, a middle-aged philosopher and member of the celebrated Vienna Circle, a group of philosophers and scientists who met weekly in Vienna to discuss the nature of scientific knowledge. A recent talk there had

centered around the logical relationship between mathematics and the natural world. “If Hilbert hears your presentation he’s going to explode.”

“I don’t think Hilbert really has anything new to say about this question of the logical connection between mathematics and nature,” chimed in Herbert Feigl, a younger philosopher who also participated in the deliberations of the Vienna Circle. “This is going to be Hilbert’s retirement speech, and he’s certainly not going to startle the audience with anything new. Königsberg is Hilbert’s hometown, and he’s going to be made an honorary citizen of the town,” noted Feigl. “What kind of revelations can he possibly present, anyway, about nature and logic that he hasn’t already made many times before?”

Squinting through the smoky air inside the café at his colleagues as they argued about these fine points of mathematics and nature, Gödel thought how surprised they would all be when they heard the details underlying the bombshell he was planning to drop at the meeting. He still found it hard to believe that the discovery he had made a few months earlier was completely correct, since its implications would undermine the entire program Hilbert had set forth in Bologna a few years earlier for putting the foundations of mathematics on a firm logical basis.

⋮

The discussion session on the foundations of mathematics in which Gödel’s presentation was scheduled was called to order by the chairman, Professor Hans Hahn, Gödel’s teacher at the University of Vienna. Gödel spoke toward the end of the session, criticizing the belief that every statement that can be labeled “true” (or “false”) can be represented with certainty in some formal logical system. Gödel then lobbed his bombshell into the discussion, going on to state, “Under the assumption

of the consistency of classical mathematics, one can give examples of propositions…that are really true, but are unprovable in the formal system of classical mathematics.” So the cat was out of the bag—and mathematics would never again be able to claim a degree of truth greater somehow than that claimed by the natural sciences.

Strangely, Gödel’s annoucement caused hardly a stir in the audience. Well, the end of a three-day meeting in late summer is hardly the best position on the program to draw anyone’s attention. Or perhaps Gödel’s claim was just so far away from the conventional wisdom, à la Hilbert, that the audience just didn’t hear what Gödel was really saying. And, in fact, the written proceedings of the meeting published sometime later did not even mention Gödel. But John von Neumann, newly appointed lecturer at Princeton University, heard Gödel’s message loud and clear, and instantly saw the writing on the wall for the demolition of Hilbert’s decidability program. Von Neumann buttonholed Gödel immediately after the talk, pressing him for details of the proof for the existence of undecidable propositions. And from that day on, von Neumann knew that his career in mathematical logic had come to a precipitous—but merciful—end.

The short, prematurely bald man strode to the ancient black-board in the St. John’s College lecture hall and began filling it with logical symbols and relations. Turning, Max Newman peered out at the class through his round, wire-framed spectacles and said,

“Here you see one of the big unanswered questions in the foundations of mathematics: Can we find a procedure for deciding the provability of any given proposition? Just recently the Austrian, Kurt Gödel, showed that there must always be

some undecidable propositions. But this still leaves open the question of whether there is some single, overarching, systematic procedure for deciding whether any given proposition is or is not decidable. This Decision Problem is the last element of Hilbert’s program for the foundations of mathematics that has survived Gödel’s onslaught.”

As he completed this presentation of Hilbert’s Entscheidungsproblem (Decision Problem), Newman looked directly at Alan Turing, a shy, dark-haired young man, 15 years his junior, who had already established himself as far and away the sharpest student in the class. The professor thought he would probe Turing just a bit to see how he would react to this puzzle posed by Hilbert.

“How do you think we might go about attacking the Decision Problem, Mr. Turing?”

Plagued by a lifelong hesitancy in speech, a kind of persistent stammer, Turing struggled to formulate his reply. Finally, he gasped out a response to Newman’s challenge.

“I believe it would help to consider the steps a human calculator goes through to move from an axiom to the logical statement that either proves or disproves the given proposition.”

“Yes,” said Newman in his quiet firm manner. “But what do you mean by ‘consider the steps’?”

“Well, I’m not exactly sure,” stammered Turing. “But something like constructing a systematic procedure (what today we would term an algorithm) that represents exactly how a human calculator moves from one configuration of logical symbols, the axioms, to another configuration.”

Newman pondered for a moment, then said, “How would such a procedure help you decide whether a particular statement was provable or not?”

“I think you might be able to analyze the algorithm and see if some configurations would be impossible to obtain from

the possible starting axioms. If that were the case, you could, in principle, characterize all the undecidable propositions that Gödel showed must exist. But I have to admit that at this moment I don’t see clearly how to formulate the informal notion of a ‘computation’ in precise mathematical terms.”

“Perhaps, then, this is an appropriate moment to adjourn for today and contemplate the matter. We’ll take up the discussion of this problem next week.”

⋮

During the following week, Turing puzzled over the Decision Problem and how he might formally represent the idea of a systematic procedure by which a proposition could be decided. Eventually he came up with the simple idea of a kind of mathematical “machine” whose operation mimicked the steps followed by a human carrying out a computation. Turing’s machine (see Figure 1) consists of an infinitely long tape, ruled off into squares, each of which can contain one of a finite number of symbols. It has a reading head that can scan the tape, one square at a time, writing a new symbol on the square or leaving the square unchanged. At any given step the reading head can be in one of a finite number of “states,” representing the “state of mind” of the human computer as he or she proceeds through a calculation. Finally, there is a set of instructions (what later came to be called a “program”), which tells the reading head what symbol to print on the current square being scanned, whether to then move one square, left or right, and what state to enter—including the possibility of entering into a stopping state in which the entire process of reading and writing symbols on the tape halts.

In order to decide a given statement, Turing’s machine starts with a configuration of symbols on the tape representing one of the axioms of the logical system. From that point on

FIGURE 1. A Turing machine.

the machine simply uses the steps in the program to transform the initial configuration into a continuing sequence of new tape configurations, each of which can be interpreted as a theorem that’s been proved by the system. So as the machine carries out its program, the initial pattern of symbols on the tape is transformed, step by step, into a sequence of patterns, each corresponding to a theorem proved by the system. In trying to decide if a particular proposition can or cannot be proved by the program, it’s only necessary to know if the given configuration will ever arise during the course of following the steps of program as they are carried out by the reading head.

Following Turing’s work, researchers saw that it would be important to know if the program will stop after a finite number of steps. If not, it would not be possible ever to know for

sure whether the desired configuration will occur. He wondered if there might be some superprogram that could be used to settle this halting problem for any program and any initial tape configuration (axiom) that the program might start with to generate the sequence of patterns on the tape.

Hilbert’s belief that there must be a procedure that would decide every proposition had been making the rounds in international mathematical circles since its presentation a few years earlier. One skeptic, G.H. Hardy, was the most famous mathematician in Cambridge. He stated, “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.” This time the skeptic turned out to be right!

Using his machine, Turing managed to show that the kind of algorithm Hilbert longed for just did not exist. There could not be any systematic way to show that any given program would or would not stop after a finite number of steps when started with a given tape configuration.

Late again, thought Herman Goldstine, as he paced the railway platform on a sweltering late-summer afternoon in Aberdeen, wondering just how late the train to Philadelphia was going to be today. A slightly built, bespectacled new lieutenant in the U.S. Army, the 31-year-old Goldstine had been stationed at the Aberdeen Proving Ground two years earlier where he employed his mathematical talents to help discover why the proto-computer known as the Electronic Numerical Integrator and Computer (ENIAC), being built at the University of Pennsylvania’s Moore School of Electrical Engineering in nearby Philadelphia, was not working as well as expected. And

since the army had a substantial investment in this machine, which they hoped to use for various computational tasks involving the calculation of ballistic trajectories, the military brass thought that Goldstine’s presence in Philadelphia might not only beef up the mathematical talent on hand for the job but also inject a bit of military zip into the slack work attitudes that military men always seem to find in academics.

Upon reaching one end of the platform, Goldstine turned and began to retrace his steps, his head down, deep in reflection on the discussions that day at the Proving Grounds. A noise at the other end of the platform broke into his reverie, and as he glanced up he saw a rather portly figure in a gray, three-piece banker’s suit come onto the platform and begin walking in his direction. Goldstine was startled when he recognized this fellow traveler as the legendary mathematician John von Neumann. He must be on his way to Philadelphia to catch the train back to Princeton, thought Goldstine. Besides the two of them, the platform was deserted. Goldstine wondered if fate had conspired to place von Neumann here at this very moment, since the mathematical problem he had been discussing just an hour ago with his colleagues J. Presper Eckert and John W. Mauchly at the Moore School was the very one he had often wanted to speak to von Neumann about. Goldstine was also curious about the atmosphere at von Neumann’s home institution, the prestigious Institute for Advanced Study in Princeton. Following his graduate work in mathematics in Chicago, Goldstine had been offered a position there as assistant to one of the Institute’s other world-famous mathematicians, Marston Morse, before the army stepped in to commandeer his services for the war effort. I’ll never have a better opportunity to speak to von Neumann than now, thought Goldstine. So he nervously approached the great man.

“Excuse me, sir, but aren’t you Professor von Neumann?” asked Goldstine in a timid voice.

“I am,” replied von Neumann with a questioning look. “May I ask who you are, Lieutenant? Have we met before?”

“Not at all. But I have heard you lecture several times, and wanted to take this opportunity to introduce myself. I am Herman Goldstine. Currently, I’m stationed here at the Aberdeen Proving Grounds.”

“I see,” said von Neumann in his soft Hungarian-accented English, which, together with his warm, friendly personality, always seemed to put people at ease. “Are you doing mathematical work here?”

“Actually, I received my doctoral degree in mathematics at Chicago a couple of years ago and was offered a post at the Institute as assistant to your colleague, Professor Morse. But the army needed me more than the Institute. So here I am.”

“Are you at liberty to say what you’re working on here?” enquired von Neumann.

“In general terms, yes. I’m here to help develop a computing machine that the army is supporting. It’s actually being built at the Moore School down at Penn. But I’m stationed here at Aberdeen, because the army wants to use this machine to calculate various sorts of ballistic trajectories.”

Hearing this, von Neumann’s expression changed from a half-attentive, cocktail-party type of look to a gaze of intense concentration. “Did you say you’re involved in building a computing machine?”

“Yes, it’s going to be based on electronic circuitry using vacuum tubes—if we can ever get it going. A big part of my job here is to put a bit of military discipline into the situation at Penn, so as to move this project forward a bit faster.”

“What type of performance do you expect to get from this machine?” von Neumann shot back, his tone now more typical of an oral examination for a doctoral candidate than the relaxed good humor of a casual conversation.

“Well, the design specs call for the machine to be able to

carry out 333 multiplications per second.”

As he heard this astonishing figure, von Neumann’s eyebrows shot up. As the train approached the station, he said,

“Young man, please sit with me on the train and tell me as much about this project as security considerations allow.”

⋮

And so began von Neumann’s association as a consultant to the ENIAC Project and its successor, the Electronic Discrete Variable Computer (EDVAC). Both machines were being developed by the brilliant electrical engineer, J. Presper Eckert, along with his somewhat less dynamic colleague, John W. Mauchly. At the time von Neumann joined the project, the principal flaw of the ENIAC was its lack of adequate stored memory. Every time the machine was to tackle a new problem, cables had to be rerouted, dials changed, and switches set in new positions to specify the new problem. Von Neumann, following the work of Eckert, hit upon the idea of storing the machine’s program in memory in coded form rather than specifying it by hardware. And so returned the idea, probably first enunciated by Charles Babbage a century earlier, of software dictating the course of a calculation, hardware serving only as a kind of material embodiment of the information being processed by the machine.

At this point von Neumann, with his characteristic flair for jumping several steps ahead of mere ordinary geniuses, was already seeing relations between the computing machine and the human brain, and beginning to think about how he might have a real-life computing machine of his own. And therein lies our tale.