It Began with Babbage (11 page)

Hilbert, of course, believed that the answer to all three questions was yes. For his program to work, certain matters needed to be clarified. In particular, certain key concepts had to understood. These included, in particular, the concepts of absolute proof, formal system, and meta-mathematics.

Intimidating words, especially the last.

By
absolute proof
is meant that the consistency of a mathematical system must be established without assuming the consistency of some other system.
⁵
In other words, a mathematical system must be self-contained, a solipsistic world of its own.

A system that allows for absolute proofs, not admitting anything outside of itself, is what mathematicians and logicians call a
formal system
, and no term, expression, or proposition in the system has any meaning. And because terms or expressions in a formal system have no meaning, they are not even symbols, for a symbol represents something else, it is
about
something else, whereas the terms or propositions in a formal system are just squiggles. For example, the entities 2, +, 4, and = carry no meaning in a formal system of arithmetic; they are squiggles. Likewise, the expression 2 + 2 = 4 is a string of squiggles that is also meaningless, but is derived by putting together the “primitive” squiggles according to certain rules (often called a
calculus
).

Which leads us to meta-mathematics. It is one thing to write

2 + 2 = 4

This is a meaningless squiggle composed out of primitive squiggles. It is another thing to write

“2 + 2 = 4” is a valid proposition in arithmetic.

The former is an expression
within
arithmetic, whereas the latter is a statement
about
that expression and, thus, a statement
about
arithmetic. The one is a mathematical proposition; the other, a meta-mathematical statement.

This distinction was important for Hilbert's program and, as we will see, it plays a significant role in the development of the science of computing. In Hilbert's context, it means that statements such as

“mathematics” is consistent

“mathematics” is complete

mathematical propositions are decidable

are meta-mathematical. They are meaningful assertions about mathematics.

To return to Hilbert's three questions. The answers were provided in 1931 by an Austrian mathematician Kurt Gödel (1906–1978), then at the University of Vienna, who later emigrated to America and became a member of the extraordinary constellation of scientific thinkers that included Albert Einstein (1879–1955) at the Institute of Advanced Study, Princeton, New Jersey,
⁶
(This institution plays a role of its own in
our
story, as we will see.)

Gödel's response to Hilbert, published in a German journal, bears the title, when translated into English, “On Formally Undecidable Propositions of Principia Mathematica
and Related Systems,” and it would have devastating implications for how mathematicians would see the nature of their craft. Gödel showed that axiomatic systems have certain inherent limitations, that the complete axiomatization of even the arithmetic of whole numbers is not possible. He demonstrated that it is impossible to establish the internal consistency of a large range of mathematical systems, including arithmetic—that is, there was no guarantee that a system of mathematics was free from internal contradictions. He showed that there are true propositions in arithmetic (the truth of which could be established by appealing to concepts
outside
arithmetic) that could not be proved
within
the axiom system of arithmetic itself. He established what came to be called the
undecidability problem
in mathematics: that there are certain propositions in a mathematical system that can be neither proved nor disproved.
⁷

All of this meant that a mathematical system (such as arithmetic) is both incomplete and inconsistent. These results came to be called
Gödel's Incompleteness Theorem
. In proclaiming the limits of mathematical reasoning, it has the same status as Heisenberg's celebrated Uncertainty Principle in physics.

We seem to be far removed from the story of computing. The world shared by Hilbert, Russell and Whitehead, and Gödel belongs to the furthest reaches of abstraction, a veritable platonic universe seemingly having nothing to do with computing machines, even those that address the solution of algebraic problems. But let us consider another of Hilbert's famous
fin de siècle
problems: his 10th problem concerning a family of equations of the form

P
(
x
₁
,
x
₂
, …,
x
_n
) = 0

where
P
is a polynomial with integer coefficients, known as “Diophantine equations.”

Hilbert asked whether one could devise a procedure by which it can be decided in a finite number of steps whether a given Diophantine equation is solvable in rational integers (that is, zero, and positive and negative integers, ±1, ±2, and so forth). This is called a
decision problem
or, to use its impressive German term,
Entscheidungsproblem
. As for a “procedure” that can be performed in a “finite number of steps,” what Hilbert was asking was whether there is (using present-centered language) an
algorithm
to decide whether a given Diophantine equation has a solution.

Now, the
Entscheidungsproblem
bears a connection with Gödel, for, although Gödel had shown that certain mathematical propositions are undecidable, the
Entscheidungsproblem
asks whether there is an algorithm that can decide whether any proposition is or is not decidable.

This is where Alan Turing enters this story.

As Lord Byron's estranged daughter and Babbage's interpreter, as a woman uncommonly gifted in mathematics, and as one who more than anyone else (save for Babbage) can claim to have understood something of what it is to program a computer a century before her time, it is not surprising that Augustus Ada, Countess of Lovelace, has drawn a measure of popular attention. However, among all the characters who people the history of computer science, no one has excited more attention of the nonmathematical, nonscientific world than Alan Mathison Turing (1912–1954).

Apart from biographies, two plays about him were written, produced, and performed in London and New York (one even garnering three Tony Award nominations). A television film about his life was shown by the BBC. A novel has been written with Turing as its main character. A musical has been made. In Manchester, England, where he lived and taught in the university's mathematics department in the final years of a short life, and where he died, a bridge and a road were named after him. Statues of the man have been installed in several places in England. Computer laboratories and auditoria and entire buildings have been named after him in universities in Europe, South America, and the United Kingdom. The world's premier prize in computer science is called the Turing Award. And, in 2012, the centenary of his birth, commemorative events, both scientific and cultural, were held in many parts of the world. One wonders what he would have made of this posthumous adulation.

No doubt, a significant part of the popular fascination with Turing stems from the tragic aspect of his later life. A homosexual in England in a time when homosexuality was illegal, under the same law as in Oscar Wilde's time a half-century before, Turing was prosecuted for “gross indecency” in England.
⁸
His death in June 1954 by cyanide poisoning was officially attributed to suicide. His personal eccentricities, as recollected by people who knew him, added to the legend surrounding him. But, all of this would not have meant a thing if he had been an “ordinary” man. This, he most certainly was not. His place in the history of computer science lies in his remarkable contributions to at least three different aspects of this story. Here, we consider the first and, arguably, his most profound contribution.

At the time Gödel published his massively consequential results, Turing was an undergraduate in King's College, Cambridge, reading for a mathematics degree or “tripos” (in Cambridge jargon).
⁹
As an undergraduate, Turing read Bertrand Russell's
Introduction to Mathematical Philosophy
(1919) and was introduced to the problems of the foundations of mathematics.
¹⁰
He read a paper on mathematical philosophy to the Moral Science Club (“moral science” being the term Cambridge used to denote philosophy). At King's College, he came to know, among the college fellows, philosopher of science Richard Braithwaite (1900–1990), and attended a course of lectures on the methodology of science by astrophysicist Arthur Stanley Eddington (1882–1944).
¹¹
Working on his own and responding to Eddington's lectures, some of which touched on probability and statistics,
Turing “discovered” a key result in probability theory called the Central Limit Theorem, only to learn that this theorem had actually been published in 1922.
¹²

He graduated in 1934 and his results in the tripos were good enough for King's College to offer him a research studentship. He began writing a dissertation that, if accepted, would give him a fellowship in King's. Dissertation completed and submitted to the college for their consideration, Turing attended a course of lectures offered by Max Newman (1897–1984), a fellow of St. John's College in Cambridge and distinguished for his contribution to topology, a major branch of mathematics that deals with the properties of spatial objects like curves and surfaces that remain unchanged under such transformations as deformation, twisting, and stretching. Newman will have a later influence on Turing, but in 1935, this particular encounter proved to be fateful. Newman lectured on the foundations of mathematics and the problems Hilbert had laid out in 1928. And he discussed Gödel's incompleteness theorem.

Still, Gödel had not dealt with the third of Hilbert's problems:
Entscheidungsproblem
. Is there a procedure for determining whether a mathematical proposition was provable or unprovable?

That same year, at age 22, on the strength of his dissertation and backed by such senior and illustrious King's College fellows as economists John Maynard Keynes (1883–1946) and Arthur Pigou (1877–1959), Turing was elected a fellow of King's College.

Entscheidungsproblem
: a mechanical process to “do” mathematics. What does it mean to call a process mechanical? Does it entail a machine? A mathematical machine?

Babbage's Analytical Engine was a mathematical machine. Was this the kind of thing Hilbert had in mind when he formulated his
Entscheidungsproblem
? Did he at all know of Babbage's engine? When Turing became interested in Hilbert's third question, did
he
know about Babbage? According to his biographer, he did indeed know of Babbage's work, but probably not until the 1940s.
¹³
At any rate, so his biographer tells us, sometime during the early summer of 1935, in the village of Grantchester, just outside Cambridge—a place immortalized by the poet Rupert Brooke (1887–1915), once a fellow himself of King's College, in his poem “The Old Vicarage, Grantchester” (1912)—lying in the meadow watching the Cambridge sky, as in Brooke's poem, Turing began to think of a machine to deal with the
Entscheidungsproblem
.
¹⁴

However, the mathematical machine about which Turing began thinking that summer in 1935 was a far cry from the world of gears, levers, and Jacquard cards. Babbage's engine was a mathematical machine in that it solved mathematical problems of a certain kind. Turing's idea of a mathematical machine was, to begin with, far larger in scope regarding what such a machine could do. But also,
it was itself a mathematical object
. Turing's vision of a machine belonged not to the world of physical artifacts that obeyed the laws
of physics, it belonged to the world of squiggles or, as we will see, squiggles that represented things—hence, it was a world of symbols and symbol processing. It could process symbols but it was itself also a symbolic object; it belonged to the abstract world. Turing envisioned a purely abstract artifact.

In May 1936, he submitted a long paper bearing the forbidding title “On Computable Numbers with an Application to the
Entscheidungsproblem
” to the London Mathematical Society. The paper was accepted and published in the society's
Proceedings
later that year.
¹⁵
Notice the title of the paper. It is as if “computable numbers” was the main issue “with an application to” the
Entscheidungsproblem
as a secondary concern.

As Nobel laureate biologist and scientific essayist Sir Peter Medawar (1915–1987) memorably wrote, a scientific paper never tells the story of how science
actually
takes shape in a person's mind. A scientific paper rarely represents the actual creative thought process that produced the results described in the paper. All the messiness that enters into thinking, all the false trails, blind alleys, muddle-headedness, short-sightedness, and limited rationality that scientists (or any problem solver) experience during actual thinking are cleaned up or shoved under the carpet. What is communicated is a sanitized “portrait of the scientist as a rational being.” It is for this reason that Medawar claimed that the scientific paper is “a fraud.”
¹⁶

So, also, we should not take the title of Turing's paper and the organization of its contents as a reflection of his actual thought process. Rather, we should accept it as an image of how he probably rationalized his thinking after the fact, an image of how he wanted to present his thoughts to readers.