It Began with Babbage (13 page)

A universal Turing machine
U
can compute any Turing-computable
function
F
(
X
) by specifying the description of the Turing machine
M
that computes
F
(
X
) on the same
tape of
U
as the input argument
X
. When
U
halts, the
value
F
(
X
) will be printed on the tape.

In a universal Turing machine, the tape will contain not only the argument of the function to be computed, but also the program (state table) that would compute that function on a “regular” Turing machine. The state table of the universal Turing machine will “read” the program from the tape and
interpret
this program. The universal Turing machine will
simulate
each Turing machine that is described on its tape. It is programmed to be programmable, so to speak—in the fashion of the Analytical Engine—although it is far more universal than the Analytical Engine, for it is capable of simulating
any
other Turing machine.

Turing's 1936 paper had the clause “with an application to the
Entscheidungsproblem
” in its title. Recall Hilbert's third question: is there a definite method that can decide the provability (or otherwise) of a mathematical problem? This was what had excited Turing in the first place, what had started him on this particular intellectual journey leading to his universal Turing machine. And, in his paper, addressing this question, he would reply that Hilbert's
Entscheidungsproblem
, in fact, had no solution. There can be no computing machine that, provided with a mathematical expression, can determine whether the expression is provable.

His argument was complex and ingenious and dense, and because it drew on the construction and operation of a Turing machine, completely original in style. Heretofore, mathematical (or meta-mathematical) proofs had never relied on the operation of a machine that scanned symbols on a tape. And, of course, it sounded the death knell of Hilbert's third problem, just as Gödel had sounded the death knell of Hilbert's first two problems. Turing's argument also demonstrated the limits of his computing machine. There were problems that were not Turing computable; they were
unsolvable
so far as Turing computability was concerned.

So what had Turing wrought in his paper of 1936? He had created, as we have seen, a symbol processing machine in the sense that its behavior is determined by precise rules. A description of a set of rules of behavior is also called, in the mathematical world, an
effective procedure
, and in the computational world, an
algorithm
. There is a sense in which we speak intuitively or naturally of effective procedures performed by human beings. For example, we talk of a procedure for multiplying two multidigit numbers. That procedure is “effective” because its rules guarantee us a correct solution. What Turing did was to declare that any process that “naturally” or “intuitively” seems to be an effective procedure can be realized by a Turing machine.
²⁵

This claim would come to be known as
Turing's thesis
. Using a very different formalism, American mathematician and logician Alonzo Church (1903–1995) arrived, that same year although earlier, at a similar conclusion, deploying a notion he called “effective calculability” and using a very different formalism called “recursive function theory”.
²⁶
Turing acknowledged this in his paper and demonstrated that Church's concept of effective calculability and his notion of computability were equivalent. Thus, Turing's thesis is also called
Church's thesis
in the context of Church's result, and it was Church who, in a review of Turing's paper, called the latter's result
Turing's thesis
. In 1936, Turing would go to Princeton, where Church was on the mathematics faculty, and write a doctoral dissertation. His dissertation committee included Church.
²⁷

The use of the word “thesis” is noteworthy. Turing's claim was not a theorem. It could not be proved, because the notion of effective procedure or algorithm is intuitive, informal. In fact, the Turing machine is a formalization of this intuitive notion.

The Turing machine is an abstract artifact. No one would think seriously of building a physical model of the Turing machine. Its significance in the history of computing lay in the future: It was
consequential
in a number of ways.

First, per Turing's thesis, the fact that anything “naturally” deemed computable can be realized by a Turing machine meant that for every physical entity that one might call a computer (artificial or human) there exists a Turing machine equivalent. The Turing machine is the great unifier: Babbage's Difference Engine, his Analytical Engine, Ludgate's analytical machine, and all other computing engines that could be conceived and built or are yet to be built have their functional commonality in the Turing machine. Despite its breathtakingly simple architecture, the Turing machine is (to use a mathematical term) a canonical form for digital computers.

Second, Turing's invention of his machine initiated its own intellectual adventure; the mathematical foundations of computing began with Turing's work (along with the work of a handful of other contemporaries such as Church). The term
automaton
(which, as we have seen, has a long pedigree; see
Chapter 3
, Section X) was appropriated to establish a discipline and a field of study called
automata theory
—the systematic study of the structure, behavior, capabilities, and limitations of abstract computing machines—the Turing machine and its variants certainly, but other abstract kinds also (some of which we will encounter later). What Turing launched with his 1936 paper was the founding of
theoretical computer science
, even though it was a time when a “computer” was still a human being! It is because of this that the year 1936 may well be called an
annus mirabilis
, a miracle year in the annals of computing.

The spirit of Alan Turing, like that of Charles Babbage but much more, permeates the history of computer science, as we will see—“now you see him; now you don't,” rather
like the Orson Welles character Harry Lime in Carol Reed's classic film
The Third Man
(1949). And, like Harry Lime, even when not actually visible, Turing's presence is forever palpable, although not menacingly or threateningly, but challengingly.

The conventional wisdom is that Turing's 1936 paper had no influence on the practical development of the digital computer that would take place in the decade or so thereafter. This conventional wisdom seems plausible. After all, both Turing and Church were “pure” mathematicians and logicians. Their respective papers were published in mathematical journals. And even among mathematicians, Turing's approach—creating a machine (albeit an abstract one) that generates a process involving space (the squares on the tape), time (the succession of steps required to perform a computation), and motion (of the read/write head)—must have seemed quite alien. Indeed, according to Turing's biographer, there was no one in England who could referee the paper prior to its acceptability for publication.
²⁸
He had created a new kind of mathematics that would eventually migrate out of mathematics into the new science of computing under the banner of automata theory.

The main protagonists in the next chapters of our story were not at all concerned with such issues as computability, unsolvability, decidability, and so on. They were not interested in what could
not
be computed, but rather with what
could
be computed and
how
—in the “real” world. Some of these people had a formal mathematical background, but in “mainstream” mathematics, not where mathematics met logic. Others were trained in physics or engineering. They would have been blissfully unaware of Turing's 1936 paper.

There were, however, two factors that might challenge the conventional wisdom. One was the interaction among scientists, not just within the close-knit community in Cambridge, London, or Oxford in England, or the “other” Cambridge in America, but across the Atlantic. The other was World War II, which made teams out of individuals in a way the scientific world had never experienced before.

The making of “laboratory societies” was not unknown. In Cambridge, not far from King's College, was the Cavendish Laboratory (founded in 1874), arguably the world's most distinguished center for experimental physics between the two World Wars, when first Sir Joseph Thomson (1856–1940) and then Sir (later Lord) Ernest Rutherford (1871–1937) presided over a glittering galaxy of physicists, British and otherwise.
²⁹
But science—even experimental physics—was still done on a relatively small scale. World War II changed all that, as much in Britain as in the United States and in Germany. The “purest” of scientists became “applied scientists”; engineers, mathematicians, physicists, and chemists hobnobbed with one another in pursuit of common goals in a manner never witnessed before. They were forced to mingle with bureaucrats, civil servants, politicians, and the military. The era of
Big Science
had begun.

Turing, with all his eccentricities (sometimes recorded by those who knew him) would also become a participant in Big Science as it emerged in England, especially in Bletchley Park, where scientists and engineers were in the business of building code-breaking machines. Here, he would encounter Max Newman, whose lectures in Cambridge on
Hilbert's program had started him on the path to the Turing machine. Indeed, Newman had been instrumental in ensuring that Turing's paper could be published—despite Church's priority by a few months—arguing that the two approaches were very different and that Turing's was a more direct approach to solving the
Entscheidungsproblem
. He also helped Turing to go to Princeton to work with Church.
³⁰
So at least one person who was heavily involved in the development of real computers during World War II was intimately familiar with Turing's machine.

In Princeton, beside the university where Church taught, there was the fabled Institute of Advanced Study, the “one true Platonic heaven,”
³¹
whose denizens included Albert Einstein (1879–1955) and the prodigious John von Neumann (1903–1957), whose place in this history is among the most profound (as will be seen). Einstein may well have been a distant, ephemeral figure for Turing, but not von Neumann. They had met in 1935 when von Neumann spent a term as a visiting professor in Cambridge
³²
; their acquaintance was renewed in Princeton, and von Neumann even wrote a letter of support on Turing's behalf to obtain a fellowship that would allow him to extend his stay in Princeton for a second year (which he did),
³³
this enabling him to complete a doctoral dissertation under Church. Strangely enough, von Neumann's letter had no mention of Turing's work on computable numbers. It would seem plausible that, at some point during their encounter in Princeton, von Neumann would come to know of this work, but there is no evidence of this.
³⁴

At any rate, let us put aside Turing for the moment. Let us venture into an astonishing chapter in the history of computing that began during the late 1930s but received its most intense stimulus during, and because of, World War II. Its outcome was the emergence, during the course of the 1940s, of the fully operational, general-purpose, programmable, electronic computer.

  
1
. More precisely, in the spoken version of the lecture, for want of time, he presented only 10 of these problems. C. B. Boyer. (1991).
A history of mathematics
(2nd ed., Rev., p. 610). New York: Wiley.

  
2
. Thus, Sir Isaac Netwon's
Philosophae Naturalis Principia Mathematica
(1687) [Mathematical Principles of Natural Philosophy]—called, simply,
Principia
—although a work about physical nature, was couched in a mathematical–axiomatic framework.

  
3
. Boyer, op cit., p. 609.

  
4
. R. Zach. (2003). Hilbert's program.
Stanford encyclopedia of philosophy
[On-line]. Available:
http://www.plato.stanford.edu/entries/hilbert-program/

  
5
. E. Nagel & J. R. Newman. (1959).
Gödel's proof
(p. 26). London: Routledge & Kegan Paul.

  
6
. For a delightful “postmodern” fictional portrait of some of these actual thinkers at this institute circa 1940s and 1950s, see J. L. Casti. (2003).
The one true platonic heaven
. Washington, DC: Joseph Henry Press.

  
7
. For a beautiful and highly understandable (from a nonmathematician's point of view) of Gödel's work, see Nagel & Newman, op cit.

  
8
. In September 2009, the then-British Prime Minster Gordon Brown issued a formal apology to Turing on behalf of the government.

  
9
. A. Hodges. (1983).
Alan Turing: The enigma
(p. 59
ff
). New York: Simon and Schuster.

10
. Ibid., p. 85.

11
. Ibid., p. 87.

12
. Ibid., p. 88.

13
. Ibid., p. 297.

14
. Ibid.

15
. A. M. Turing. (1936). On computable numbers with an application to the
Entscheidungsproblem. Proceedings of the London Mathematical Society, 2
, 230–236. This paper has since been reprinted in M. Davis. (Ed.). (1965).
The undecidable
. New York: Raven Press. It is also available on the Internet at
http://www.abelard.org/turpap2.htm
. The pagination I refer to later in this chapter is based on this retrieved paper.