Hobbes’s ratiocination, Leibniz’s calculus ratiocinates, Babbage’s mechanical notation, Boole’s laws of thought, and Smee’s conceptual cyphers all attempted to formalize the correspondence among a mechanical system of things, a mathematical system of symbols, and our mental system of thought and ideas. All approaches to formalization from the time of Hobbes until today have been haunted by similar questions: Is the formalization consistent? Is it complete? Does it correspond, in whole or part, to the real world? To the way we think? These questions hinge on the definition of consistency and completeness, available in two different strengths. A formal system is syntactically, or internally, consistent if and only if the system never proves both a statement and its negation and syntactically complete if one or the other is always proved. The system is semantically consistent, under a particular external interpretation, if and only if it proves only true statements and semantically complete if all true statements can be proved.
In 1931, Austrian logician Kurt Gödel (1906–1978) expanded the horizons of mathematics by proving, for both definitions, that no formal system encompassing elementary arithmetic can be at the same time both consistent and complete. Within any sufficiently powerful and noncontradictory system of language, logic, or arithmetic, it is possible to construct true statements that cannot be proved within the boundaries of the system itself.
Gödel achieved this conclusion by a technique now known as Gödel numbering, whereby all expressions within the language of a given formal system are assigned unique identity numbers and thereby forced to obey the manipulations of a strictly arithmetic bureaucracy from which it is impossible to escape. (“Gödel, having grown up in the Austrian Kaiserreich, famous for its bureaucracy, must have been familiar with the process,” says my mother, no stranger to bureaucracy, being Swiss.) The Gödel numbering, like the characteristic numbering of Leibniz, is based on an alphabet of primes. But Gödel, unlike Leibniz, provided an explicit coding mechanism so that translation between compound expressions and their Gödel numbers remains a two-way street.
“Metamathematical concepts (assertions) thereby become concepts (assertions) about natural numbers or sequences of such, and therefore (at least partially) expressible in the symbolism of the system . . . itself,” wrote Gödel in the introduction to his proof.50 By some ingenious twists of logic and number theory. Gödel constructed a formula, the Gödel sentence, “which asserts its own unprovability” even though it can be perceived by reasoning outside the system as being true. The Gödel sentence is loosely equivalent to a self-referential statement that says, “This statement cannot be proved.” But saying this with words and saying it with mathematics are two different things. The Gödel numbering enables the formalization of this self-reference by means of a sentence (G) saying, in effect, “The sentence with Gödel number g cannot be proved,” where the details of the system are manipulated so that the Gödel number of G is g. G cannot be proved within the specified system and so it is true. Since, assuming consistency, its negation cannot be proved, the Gödel sentence is therefore formally undecidable, rendering the system incomplete. Where Leibniz and his followers had dreamed of a universal coding that would allow the calculation of all truths, Gödel showed that even a system as simple as ordinary arithmetic could never be made complete. Thus Gödel brought Leibniz’s dream of a universal, all-encompassing formalization to an end.
This upheaval in the foundations of mathematics, preceded by a similar upheaval in physics, widened our view of the world. The mathematical territory that Gödel expropriated from the stronghold of consistency and proof was distributed to the surrounding mathematical wilderness in the form of intuition and truth. Does a restriction on the powers of formalization curtail the effectiveness of formal systems (or close approximations) functioning within the limitations and inconsistencies of the real world? Physics became no less powerful by discovering that exact knowledge lies beyond any one observer’s reach. Arithmetic became no less useful when shown to be formally incomplete. On the contrary, Gödel demonstrated the ability of even simple arithmetic to construct truths that lie beyond the reach of proof.
This distinction between provability and truth, and a parallel distinction between knowledge and intuition, have been exhibited as evidence to support a distinction between the powers of mechanism and those of mind. Gödel’s second incompleteness theorem—showing that no formal system can prove its own consistency—has been construed as limiting the ability of mechanical processes to comprehend levels of meaning that are accessible to our minds. The argument over where to draw this distinction has been going on for a long time. Can machines calculate? Can machines think? Can machines become conscious? Can machines have souls? Although Leibniz believed that the process of thought could be arithmetized and that mechanism could perform the requisite arithmetic, he disagreed with the “strong AI” of Hobbes that reduced everything to mechanism, even our own consciousness or the existence (and corporeal mortality) of a soul.
“Whatever is performed in the body of man and of every animal is no less mechanical than what is performed in a watch,” wrote Leibniz to Samuel Clarke.51 But, in the Monadology, Leibniz argued that “perception, and that which depends upon it, are inexplicable by mechanical causes,” and he presented a thought experiment to support his views: “Supposing that there were a machine whose structure produced thought, sensation, and perception, we could conceive of it as increased in size with the same proportions until one was able to enter into its interior, as he would into a mill. Now, on going into it he would find only pieces working upon one another, but never would he find anything to explain Perception. It is accordingly in the simple substance, and not in the composite nor in a machine that the Perception is to be sought. Furthermore, there is nothing besides perceptions and their changes to be found in the simple substance. And it is in these alone that all the internal activities of the simple substance can consist.”52
The difference of opinion between Hobbes (mind being a temporary artifact of ordinary matter when suitably arranged) and Leibniz (mind being a fundamental element of the universe, intrinsic to all things but not to be explained by the arrangement of things themselves) has fueled opposing visions over the past three hundred years. Hobbes and Leibniz both believed in the possibility of intelligent machines; it was over the issue of mechanism’s license to a soul, not to an intelligence, that the two philosophers diverged.
Hobbes’s God was composed of substance; Leibniz’s God was composed of mind. Leibniz argued against Hobbesian materialism to the very end; yet one senses that he knew that the case was far from closed. “These gentlemen who strongly debase the idea of God do the same with the idea of the soul,” wrote Leibniz to Princess Caroline in 1716. “One of their sect could easily persuade himself into believing that idea of some of the ancient writers . . . according to which souls are born when the machine is organized to receive it, as organ-pipes are adjusted to receive the general wind.”53
4
ON COMPUTABLE NUMBERS
In attempting to construct such machines we should not be irreverently usurping His power of creating souls, any more than we are in the procreation of children: rather we are, in either case, instruments of His will providing mansions for the souls that He creates.
—ALAN TURING1
In 1936 the English logician Alan Turing (1912–1954) adjusted the natural numbers to receive the general wind.
Turing’s generation grew up in the mathematical shadow of Göttingen’s David Hilbert (1862–1943), whose ambitious program of formalization set the stage for mathematics between World War I and World War II. At the International Congress of Mathematicians in Paris in 1900, Hilbert delivered a list of twenty-three unsolved problems, prefaced by his conviction that if a proposition could be articulated within the language of mathematics then either its proof or its refutation must exist. From the elements of logic and number theory—the common language at the foundations of mathematics—the Hilbert school believ
ed that all mathematical truths could be reached by a sequence of well-defined logical steps. In 1928, Hilbert again addressed the International Congress of Mathematicians. He identified three questions by which to determine whether any finite—or at least finitely describable—set of rules could define a closed mathematical universe: Can the foundations be proved consistent (so that a statement and its contradiction cannot ever both be proved)? Can they be proved complete (so that all true statements can be proved within the system itself)? Does there exist a decision procedure that, given any statement expressed in the given language, will always produce either a finite proof of that statement, or else a definite construction that refutes it, but never both?
Gödel’s incompleteness theorems of 1931 brought Hilbert’s ambitions to a halt. Where the Hilbert school had hoped to construct one complete system encompassing all mathematical truths, Gödel proved that no single mathematical system sufficient for ordinary arithmetic could establish its own consistency without external help. To capture the richness of mathematics would take a multiplicity of systems, nourished by truth from outside as well as proof from within.
The question—known as the Entscheidungsproblem, or decision problem—of whether a precisely mechanical procedure could distinguish provable and disprovable statements within a given system remained unanswered, entangled with fundamental difficulties as to how the intuitive notion of a mechanical procedure should be mathematically defined. Alan Turing was a newly elected fellow of King’s College at Cambridge University, working under the guidance of topologist Maxwell H.A. Newman, when the Entscheidungsproblem first attracted his attention. Hilberf s challenge aroused an instinct, prevalent in the aftermath of Gödel, that mathematical problems resistant to strictly mechanical procedures could be proved to exist. Turing’s strikingly original approach, completed when he was twenty-four, succeeded in formalizing the previously informal correspondence between “mechanical procedure” and “effectively calculable,” linking both concepts to the definition of recursive functions introduced by Gödel in 1931. “By what species of madness,” asked A. K. Dewdney, “might one have supposed that all three notions would turn out to be the same?”2
Turing sought to prove the existence of noncomputable functions, but he had to establish the nature of computability first. A function—in essence a list of questions and their answers—is effectively calculable if it is possible to list all the answers by following a finite set of explicit instructions (an algorithm) that defines exactly what to do from one moment to the next. A computable function is a function whose values can be determined by a mechanical procedure performed by a machine whose behavior can be mathematically predicted from one moment to the next. Effectively calculable and computable appear to be saying the same thing, in a circular sort of way. Proving this equivalence required extending the third leg of the tripod, the concept of recursive functions, to set the whole structure on mathematically solid ground.
Recursive functions are functions that can be defined by the accumulation and strictly regulated substitution of elementary component parts. As multiplication can be reduced to a series of additions, and addition reduced to repeated iterations of the successor function (counting ahead one integer at a time), so can all recursive functions be deconstructed into a finite number of elemental steps. The list of ingredients is short: the existence of 0, the existence of 1, the concept of a successor, the concept of identity, a least number operator, and some clerical substitution rules. Loosely speaking, these elements require no mathematical skills beyond the ability to count. Obviously the ability to compute depends on the ability to count; proving that from the ability to count all recursive, computable, or effectively calculable functions can be constructed by clerical procedures alone was less obvious. Patience is substituted for intelligence, with consequences both practical and profound.
Rather than reviewing the work of his predecessors and approaching the Entscheidungsproblem over established ground, Turing took off from first principles on his own. He began by constructing an imaginary device now known as the Turing machine. Had Turing more diligently followed the work of Alonzo Church or Emil Post, who anticipated his results, his interest in the Entscheidungsproblem might have taken a less original form. “It is almost true to say that Turing succeeded in his analysis because he was not familiar with the work of others,” commented Turing’s colleague Robin Gandy. “Let us praise the uncluttered mind.”3
Turing arrived at his machine by a process of elimination. He began with the idea of a computer—which in 1936 meant not a calculating machine but a human being, equipped with pencil, paper, explicit instructions, and time to devote to the subject at hand. He then substituted unambiguous components until nothing but a formal description of “computable” was left. Turing’s machine thus consisted of a black box (as simple as a typewriter or as complicated as a human being) able to read and write a finite alphabet of symbols to and from a finite but unbounded length of paper tape—and capable of changing its own “m-configuration,” or “state of mind.”
“We may compare a. man in the process of computing a real number to a machine which is only capable of a finite number of conditions . . . which will be called ‘m-configurations,’” wrote Turing. “The machine is supplied with a ‘tape’ (the analogue of paper) running through it, and divided into sections (called ‘squares’) each capable of bearing a ‘symbol.’ At any moment there is just one square . . . which is ‘in the machine.’. . . However, by altering its m-configuration the machine can effectively remember some of the symbols which it has ‘seen.’. . . In some of the configurations in which the scanned square is blank (i.e., bears no symbol) the machine writes down a new symbol on the scanned square; in other configurations it erases the scanned symbol. The machine may also change the square which is being scanned, but only by shifting it one place to right or left. In addition to any of these operations the m-configuration may be changed.”4
Turing introduced two fundamental assumptions: discreteness of time and discreteness of state of mind. From the point of view of the Turing machine (and all digital computers before and since), time consists of distinct, atomistic moments, one followed by the next like the ticking of a clock, the frames of a motion picture, or the one-by-one succession of the natural numbers. This presumption of discrete sequence allows us to make sense of the world. Logic assumes the sequence of cause and effect; physical law assumes a sequence of observable events; mathematical proof assumes a sequence of discrete, logical steps. In the Turing machine these step-by-step processes are represented by a sequence of discrete symbols encoded on an unlimited supply of tape and by discrete, sequential changes in what Turing called the machine’s state of mind. Turing assumed a finite number of possible states. “If we admitted an infinity of states of mind, some of them will be ‘arbitrarily close’ and will be confused,” Turing explained. “The restriction is not one which seriously affects computation, since the use of more complicated states of mind can be avoided by writing more symbols on the tape.”5
The Turing machine thus embodies the relationship between a finite, if arbitrarily large, sequence of symbols in space and a finite, if arbitrarily large, sequence of events in time. Turing was careful to remove all traces of intelligence. The machine can do nothing more complicated or knowledgeable at any given moment than make a mark, erase a mark, and move the tape one square to the right or to the left. Each step in the relationship between tape and Turing machine is determined by an instruction table (now called a program) listing all possible internal states, all possible external symbols, and, for every possible combination, what to do (write or erase a symbol, move right or left, change internal state) in the event that combination comes up. The Turing machine follows instructions and never makes mistakes. Potentially complicated behavior does not require complicated states of mind. By taking copious notes the Turing machine can function well enough, if at an ever more tedious pace, with as few as two internal states. Behavioral co
mplexity is equivalent whether embodied in complex states of mind (m-configurations) or complex symbols (or strings of simple symbols) encoded on the tape.
Turing’s deceptively simple model produced surprising results. He demonstrated the existence of a “Universal Computing Machine,” a single machine that can exactly duplicate the behavior of any other computing machine. The universal machine embodies the concept we now know as software—encoding a description of some other machine as a string of symbols, say, 0s and 1s. When executed by the universal machine, this code produces results equivalent to those of the other machine. All Turing machines, and therefore all computable functions, can be encoded by strings of finite length. Since the number of possible machines is countable but the number of possible functions is not, noncomputable functions (and what Turing referred to as “uncomputable numbers”) must exist. Turing was even able to construct, by a method similar to Gödel’s, functions that could be given a finite description but could not be computed by finite means. The most important of these was the halting function: given the number of a Turing machine and the number of an input tape, it returns either the value 0 or the value 1 depending on whether the computation will ever come to a halt. Turing called the configurations that halt “circular” and the configurations that keep going indefinitely “circle free,” and demonstrated that the unsolvability of the halting problem implies the unsolvability of a broad class of similar problems, including the Entscheidungsproblem. Contrary to Hubert’s expectations, no mechanical procedure can determine, in a finite number of steps, whether any given mathematical statement is provable or not.
Darwin Among the Machines Page 8