It Began with Babbage Page 7
The word automaton derives from the Latinized Greek word automatos, and the invention of mechanical automata reaches back to antiquity, to such Hellenistic engineers/inventors as Ctesibius (fl. 285–222 BCE), Philo of Byzantium (circa 270–200 BCE), and Hero of Alexandria (fl. first century CE)—all scholars who, along with so many others, found their way to the great Museum at Alexandria, where they taught, studied, and did research. They imagined into existence automata more as amusement for the wealthy than for practical use.46 Still, Hero was credited for the invention of that most useful of artifacts, the water clock.47
Truly spectacular water clocks were made during the early Middle Ages by Chinese, Arabs, and Europeans.48 But, undoubtedly, the most visible, successful, and consequential automaton was the mechanical weight-driven clock—the successor to the water clock. The most reliable evidence to date places the invention of the mechanical clock to some time between 1335 and 1344 in Milan and Padua, Italy.49 The Padua clock of 1344 has been associated fairly firmly with Jacopo di Dondi (1290–1359), a scholar and physician who supervised the construction of this clock and may have contributed to its design.
XI
So mechanical automata have a venerable pedigree. In “Essays,” however, they are not what interested Torres y Quevedo, but rather automata that imitated not human movement but human thought—to the extent that such a machine could, conceivably, replace humans.50
This, of course, is a very different notion of automata from its original roots. Torres y Quevedo was contemplating “thinking” machines. People such as Babbage and Ludgate had designed machines that embodied their respective theories of automatic computation. Torres y Quevedo, however, abstracted still further—machines that imitated the “thoughtful action” of humans. And thought included, certainly, calculation, but went beyond to making judgment, making choices. These are thoughtful actions, and machines that do this are his second type of automata. He called the study of such machines automatics.51
Such automata must have “sense organs”—“thermometers, magnetic compasses, …, etc”; they must have “limbs”—mechanisms that execute the operations demanded of them. However, the essential feature of such automata is that they be “capable of discernment”52—that they have the capacity to use information received immediately from the environment or even information obtained at some prior time to dictate their operations. Such automata must, then, imitate organisms in controlling their behavior according to information received from outside their own physical boundaries. Remarkably, Torres y Quevedo wrote, they must adapt their behavior according to “changing circumstances.”53
Torres y Quevedo’s theory of automata is that such a machine is an adaptive system that can alter its “conduct” according to “changing circumstances.” He does not stop with this general definition. His science of automatics goes deeper. His aim in “Essays” was to try and show, at least theoretically, that such an adaptive automaton can be created according to principles (“rules”) that can be built into the machine itself.54 To illustrate this theoretical possibility, he resorted to real devices (he was, after all, an engineer), using electrical switches, each of which could be in one of a number of positions (“states,” in present-centered language), representing input information to the automaton, and electromagnets that could be “excited,” thus attracting their respective armatures as instances of operations.
He probed further. He referred to the French philosopher René Descartes (1596–1650), who in his most famous work, Discourse on Method (1637), discounted the possibility of automata being rational in the way humans are. In response, Torres y Quevedo imagined a machine in which there are “thousands or millions” of switches, each of which can be in one of as many different positions (states) as there are distinct written characters (such as letters, numbers, punctuation marks).55 He wrote that it is quite possible that these switches could be set to represent any phrase or sentence, short or long. A speech, then, would be represented by the setting of switches. In fact, he was anticipating the possibility of storing symbol structures (a phrase or a speech) electrically, made up of letters, numbers, punctuation marks, and so on—that is, he was imagining the possibility of an automaton that processes symbols of any kind, not just numbers à la Babbage (to whom, incidentally, he refers extensively in his essay). But, Torres y Quevedo stopped short of actually positing machines that reason on their own. Like Lovelace, who cautioned that the Analytical Engine could not originate computational action, so, too, did Torres y Quevedo respond to Descartes somewhat cautiously. Descartes, he wrote, had been mistaken in assuming that for an automaton to provide reasoned responses it must do the reasoning itself. Rather, it is the creator of the automaton who does the reasoning.56
Still, in Torres y Quevedo’s “Essays,” we find the first inkling of a general theory of what a computing device might be. It is an automaton capable of symbol processing and adapting itself to variations in its input.
NOTES
1. A. B. Bromley. (1982). Charles Babbage’s Analytical Engine, 1838. Annals of the History of Computing, 4, 196–217.
2. See, for example, F. B. Artz. (1980). The mind of the Middle Ages (3rd ed., Rev.) Chicago, IL: University of Chicago Press.
3. Natural history was the term commonly used until the end of the 19th century to designate the study of life at the level of the individual organism, especially organisms in their natural habitat. See M. Bates. (1990). The nature of natural history (p. 7). Princeton, NJ: Princeton University Press (original work published 1950). The term still prevails in some contexts such as, for example, in the term natural history museum.
4. A. E. Lovejoy. (1936). The great chain of being (pp. 233–236). Cambridge, MA: Harvard University Press.
5. E. Mayr. (1982). The growth of biological thought (p. 430). Cambridge, MA: Belknap Press of Harvard University Press.
6. H. H. Goldstine. (1972). The computer from Pascal to von Neumann (p. 67). Princeton, NJ: Princeton University Press.
7. Ibid., pp. 67–68.
8. H. Hollerith. (n.d.). “An electric tabulating system”. Reprinted in B. Randell. (Ed.). (1975). The origins of the digital computer (2nd ed., pp. 129–139). New York: Springer-Verlag (see especially p. 129). The original source of this article is not specified by Randell. However, the following article was published with the same title: H. Hollerith. (1889). An electric tabulating system. The Quarterly, Columbia University School of Mines, X, 238–255.
9. Ibid.
10. Goldstine, op cit., p. 8n.
11. F. P. Brooks, Jr. & K. E. Iverson (1969). Automatic data processing: System/360 edition (p. 120). New York: Wiley.
12. Goldstine, op cit., pp. 70–71.
13. Hollerith, op cit., p. 131.
14. Ibid.
15. Ibid., pp. 132–133.
16. D. DeLillo (1994). White noise (p. 203). New York: Penguin (original work published 1985).
17. Hollerith, op cit., p. 133.
18. R. Moreau (1984). The computer comes of age (p. 24). Cambridge, MA: MIT Press.
19. P. E. Ludgate. (1909). On a proposed analytical machine. Proceedings of the Royal Dublin Society, 12, 77–91. Reprinted in Randell (pp. 71–87), op cit., p. 71.
20. Randell, op cit., p. 71.
21. B. Randell. (1971). Ludgate’s Analytical Machine of 1909. The Computer Journal, 14, 317–326.
22. Ibid., p. 319.
23. Ibid.
24. Ibid., 318.
25. Ludgate, op cit., p. 72.
26. Ibid.
27. Ibid.
28. Ibid.
29. Ibid., pp. 72–73.
30. Ibid.
31. Ibid., p. 73.
32. Ibid., p. 74. Perforated paper tape also had a place in looms, reaching back to the 18th century. More prominently, paper tapes were used in electrical telegraphy in the mid 19th century.
33. Ibid.
34. Ibid.
35. Ludgate, op cit., p. 75.
36. Ibid., p. 74.
38. Ibid., p. 81.
39. Ibid.
40. Quoted in Randell, 1971, op cit., p. 320.
41. Ludgate, op cit., p. 85.
42. C. V. Boys. (1909). A new analytical machine. Nature, 81, 14–15.
43. This biographical information was extracted from several websites on the Internet, most notably, http://www.wvegter.hivemind. Last accessed July 19, 2013.
44. L.. Torres y Quevedo. (1975). Essays on automatics (R. Basu, trans.). Randell, 1975, op cit., pp 87–106. (Original work published in Spanish as “Essais sur l’automatique. Sa definition. Étendue théoritique de ses applications,” Revue Générale des Sciences Pures et Appliquées, 601–611 (15 Nov. 1915).
45. Torres y Quevedo, op cit., p. 87.
46. A. P. Usher. (1985). A history of mechanical inventions (Rev., pp. 162–163). New York: Dover Publications (original work published 1954).
47. H. Hodges. (1971). Technology in the ancient world (pp. 180–181). Harmondsworth, UK: Penguin Books.
48. D. L. Landes. (1983). Revolution in time (pp. 18–20). Cambridge, MA: Harvard University Press.
49. Usher, op cit., p. 196.
50. Torres y Quevedo, op cit., p. 87.
51. Ibid., p. 88.
52. Ibid.
53. Ibid.
54. Ibid., p. 89.
55. Ibid., p. 90.
56. Ibid., p. 91.
4
Entscheidungsproblem: What’s in a Word?
I
IN 1900, THE celebrated German mathematician David Hilbert (1862–1943), professor of mathematics in the University of Göttingen, delivered a lecture at the International Mathematics Congress in Paris in which he listed 23 significant “open” (mathematicians’ jargon for “unsolved”) problems in mathematics.1
Hilbert’s second problem was: Can it be proved that the axioms of arithmetic are consistent? That is, that theorems in arithmetic, derived from these axioms, can never lead to contradictory results?
To appreciate what Hilbert was asking, we must understand that in the fin de siècle world of mathematics, the “axiomatic approach” held sway over mathematical thinking. This is the idea that any branch of mathematics must begin with a small set of assumptions, propositions, or axioms that are accepted as true without proof. Armed with these axioms and using certain rules of deduction, all the propositions concerning that branch of mathematics can be derived as theorems. The sequence of logically derived steps leading from axioms to theorems is, of course, a proof of that theorem. The axioms form the foundation of that mathematical system.
The axiomatic development of plane geometry, going back to Euclid of Alexandria (fl. 300 BCE) is the oldest and most impressive instance of the axiomatic method, and it became a model of not only how mathematics should be done, but also of science itself.2
Hilbert himself, in 1898 to 1899, wrote a small volume titled Grundlagen der Geometrie (Foundations of Geometry) that would exert a major influence on 20th-century mathematics. Euclid’s great work on plane geometry, Elements, was axiomatic no doubt, but was not axiomatic enough. There were hidden assumptions, logical problems, meaningless definitions, and so on. Hilbert’s treatment of geometry began with three undefined objects—point, line, and plane—and six undefined relations, such as being parallel and being between. In place of Euclid’s five axioms, Hilbert postulated a set of 21 axioms.3
In fact, by Hilbert’s time, mathematicians were applying the axiomatic approach to entire branches of mathematics. For example, the axiomatization of the arithmetic of cardinal (whole) numbers formulated by the Italian Giuseppe Peano (1858–1932), professor of mathematics in the University of Turin, begins with three terms—“number”, “zero”, and “immediate successor”—and are assumed to be understood. The axioms themselves are just five in number:
1. Zero is a number.
2. The immediate successor to a number is a number.
3. Zero is not the immediate successor of a number.
4. No two numbers have the same immediate successor.
5. The principle of mathematical induction: Any property belonging to zero, and also to the immediate successor of every number that has the property, belongs to all numbers.
Exactly a decade after Hilbert’s Paris lecture, British logician and philosopher Bertrand Russell (1872–1970), in collaboration with his Cambridge teacher Alfred North Whitehead (1861–1947), published the first of the three-volume Principia Mathematica (1910–1913)—not to be confused with Newton’s Principia—which attempted to develop the notions of arithmetic from a precise set of logical axioms, and which was intended to demonstrate that mathematical knowledge can be reduced to (or, equivalently, derived from) a small set of logical principles. However, Russell and Whitehead did not address Hilbert’s second problem.
Hilbert returned to the foundations of mathematics repeatedly throughout the course of the first three decades of the 20th century, establishing what came to be known as “Hilbert’s program”.4 In 1928, in an address delivered at the International Congress of Mathematicians in Bologna, Italy (the home, incidentally, of the world’s first university), and in a monograph titled “Die Grundlagen der Mathematik” (“The Foundations of Mathematics), he asked: (a) Is mathematics complete, in the sense that every mathematical statement could be either proved or disproved? (b) Is mathematics consistent, in the sense that a statement such as 2 + 2 = 5 could never be arrived at by a valid proof, or in the sense that two contradictory propositions a = b and a ≠ b could both be derived? (c) Is mathematics decidable, in the sense that there exists a definite method that can be followed to demonstrate that a mathematical statement is true or not?
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.5 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), the
n 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,6 (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.7
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.
II
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 (x1, x2, …, xn) = 0