It Began with Babbage Page 9
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.
VI
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.
VII
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.25
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”.26 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.27
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.
VIII
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.28 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 an
d otherwise.29 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.30 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,”31 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 Cambridge32; 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),33 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.34
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.
NOTES
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.
16. P. B. Medawar. (1990). Is the scientific paper a fraud? In P. B. Medawar, 1990. The threat and the glory: Reflections on science and scientists (pp. 228–233). Oxford, UK: Oxford University Press.
17. Turing, op cit., p. 2.
18. Ibid.
19. Ibid., pp. 16–18.
20. Ibid., p. 3.
21. M. Minsky. (1967). Computation: Finite and infinite machines (p. 132). Englewood-Cliffs, NJ: Prentice-Hall.
22. Ibid., p. 135.
23. Turing, op cit., p. 11.
24. Minsky, op cit., p. 132 ff.
25. Ibid., p. 108.
26. A. Church. (1936). An unsolvable problem of elementary number theory. American Journal of Mathematics, 58, 345–363.
27. Hodges, op cit., p. 145.
28. Ibid., p. 113.
29. J. G. Crowther. (1974). The Cavendish Laboratory, 1874–1974. New York: Science History Publications.
30. Hodges, op cit., p. 112–113.
31. Casti, op cit.
32. Hodges, op cit., p. 131.
33. Ibid.
34. Ibid.
5
Toward a Holy Grail
I
SOMETIME BETWEEN 1936 and 1946, there was a change in etymology, at least in the English language. The word computer came to mean the machine not the man. Old habits, of course, die hard. And so, such terms as automatic calculating machines and computing machines remained in common use, along with the cautious adoption of computer, until the end of the 1940s.
But at the beginning of that war-ravaged, bomb-splattered decade, George Stibitz (1904–1995), a mathematical physicist working for Bell Telephone Laboratories in New Jersey, wrote a memorandum on a machine he and his colleague Samuel B. Williams had built in which computer unequivocally meant a machine. Indeed, they named their creation the Complex Computer because it was designed to perform arithmetic operations on complex numbers—computations necessary in the design of telephone networks, which was Bell’s forte.1
There was, of course, much more happening in the realm of computing than a change in the meaning of a word. Computers were actually being built, increasingly more complex, more ambitious in scope, more powerful, faster, and physically larger than the punched-card machines that largely dominated automatic calculation. They were being built in at least three countries: America, Germany, and England.2
These machines, developed in different centers of research, formed evolutionary families, in the sense that machine X built at a particular center gave rise to machine X + 1 as its successor. The word “evolution” carries with it much baggage. Here, I am speaking not of biological evolution by natural selection à la Darwin, but cultural evolution. The latter differs from the former in a fundamental way: biological evolution is not driven by goal or purpose; cultural evolution is always goal driven. In the realm of computers—artifacts, therefore part of culture—for example, a goal is established by the designers/engineers or potential client, and a machine is built that (one hopes) satisfies the goal. If it does satisfy the goal, then well and good (at least for a time); otherwise, a new effort will be initiated that strives to correct the flaws and errors of the earlier machine. Thus, a new artifact emerges “out of the ashes” of the old.
Over time, there may emerge new goals, new priorities that the existing machine does not meet. These new goals initiate a new design problem, a new project that usually draws on earlier experience, earlier knowledge, earlier designs. What cultural evolution shares with biological evolution is, first, that
they both are (usually) gradual. Second, they both constantly entail “testing” the organism or artifact against the environment, discarding those that do not meet the environmental conditions and ensuring the “survival” of those that do. The fundamental difference between the two lies in the mechanism by which organisms and artifacts respond to the environment. In the case of organisms, it is natural selection, which is purposeless; in the case of artifacts, it is purposeful adaptation to new environments. In fact, the difference lies in the dichotomy of chance and purpose.3
Let us see what some of these first evolutionary families of computers were.
II
Stibitz’s memorandum of 1940 began with the somewhat obvious observation that an essential mission of Bell Telephone Laboratories was the design of electrical (telephone) networks.4 The implications of this statement for this story were, however, anything but mundane. The design of telephone networks entailed computations involving complex numbers—numbers of the form a + ib or a – ib, where a, b are real numbers (in the mathematical sense) and i = √–1 is an imaginary number (in the mathematical sense). The scientists at Bell Laboratories had long felt the need for machines that could take over the burdensome performance of these complex calculations.5
The machine named Complex Computer, designed by Stibitz and Williams between 1938 and 1940, was a response to this need. Its primary purpose was to perform arithmetic on complex numbers, but it was also useful in another task common in network design, finding roots of polynomials—that is, finding values of x that would satisfy a polynomial equation such as, for example, 2x3 – 5x2 + 3x – 1 = 0.
Thus, the Complex Computer was a relatively special-purpose electromechanical device that used electrical relays (basic switching circuit elements used in telephone networks and, so, a familiar technology in the Bell Laboratories culture). This machine became the first and the progenitor of the Bell Laboratories series of “relay computers” referred to as Model I through ModelVI, but some also given specific names. Thus, Model I was also called the Complex Computer.