Darwin Among the Machines (11 page)

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.
⁵¹
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.”
⁵²

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.”
⁵³

I
n 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 believed 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?”
²

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.”
³

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.”
⁴

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.”
⁵

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 complexity 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.