The Age of Intelligent Machines
"Mathematical Roots"
by Ray Kurzweil

In the world of formal mathematics, it is just as bad to be almost right as it is to be absolutely wrong. In a sense, that's just what mathematics is. But that's not good psychology.
Marvin Minsky, The Society of Mind

A mathematician is a machine for turning coffee into theorems.
Paul Erdös

The AI field was founded by mathematicians: John McCarthy, Alan Turing (1912-1954), Norbert Weiner (1894-1964), students of Alonso Church, Claude Shannon, Marvin Minsky, and others. LISP, the primary language for academic research in artificial intelligence, was adapted from a mathematical notation designed by Stephen Kleene and Barkley Rosser, both students of Church.

Mathematics has often been viewed as the ultimate formalization of our thinking process, at least of the rational side of it. The relationship of logic and the analytic process underlying mathematics to cognition has been debated through the ages by philosophers, many of whom were also mathematicians. The actual deployment of mathematical techniques to emulate at least certain aspects of human thought was not feasible until the electronic computer became available after World War II. However, the foundations of computation theory, along with the set theory on which computation theory is based, were established long before the potential of the electron to revolutionize applied mathematics was realized.

Mathematics has often been described as a branch of philosophy, the branch most concerned with logic. It has only been in this century that the fields of mathematics and philosophy have split into largely distinct disciplines with few major figures doing important work in both areas. Bertrand Russell, having been a pivotal figure in the establishment of both modern set theory and logical positivism, was perhaps the last.

In the early part of this century Bertrand Russell, a young and as yet relatively unknown mathematician and philosopher, became increasingly occupied with a certain type of paradox and attempts to understand its implications. The resolution of the paradox had important implications for the subsequent development of the theory of computation. The following story illustrates Russell's class of paradoxes.

A judge is sentencing a man for a crime that he finds reprehensible and for which he wishes to mete out the most severe sentence he can think of. So he tells the convicted man not only that he is sentenced to die but also that because his crime was so offensive, the sentence is to be carried out in a unique way. "The sentence is to be carried out quickly," the judge says. "It must be carried out no later than next Saturday. Furthermore, I want the sentence to be carried out in such a way that on the morning of your execution, you will not know for certain that you are going to be executed on that day. When we come for you, it will be a surprise."

When the judge finished describing his unusual sentence, the condemned man seemed surprisingly pleased and replied, "Well, that's great, judge, I am greatly relieved."

To this the judge said, "I don't understand, how can you be relieved? I have condemned you to be executed, I have asked that the sentence be carried out soon, but you will be unable to prepare yourself because on the morning that your sentence is to be carried out, you will not know for certain that you will die that day."

The convicted man said, "Well, your honor, in order for your sentence to be carried out, I could not be executed on Saturday."
"Why is that?" asked the judge.
"Because since the sentence must be carried out by Saturday, if we actually get to Saturday, I will know for certain that I am to be executed on that day, and thus it would not be a surprise."
"I suppose you are right," replied the judge."You cannot be executed on Saturday. I still do not see why you are relieved."
"Well," said the prisoner, "if we have definitely ruled out Saturday, then I cannot be executed on Friday either."
"Why is that?" asked the judge.
"We have agreed that I definitely cannot be executed on Saturday. Therefore, Friday is the last day I can be executed. Thus, if Friday rolls around, I will definitely know that I am to be executed on that day, and therefore it would not be a surprise. So I cannot be executed on Friday."
"I see," said the judge.
"Thus, the last day I can be executed would be Thursday. But if Thursday rolls around, I would know I had to be executed on that day, and thus it would not be a surprise. So Thursday is out. By the same reasoning we can eliminate Wednesday, Tuesday, Monday, and today."
The judge scratched his head as the confident prisoner was led back to his prison cell.
There is an epilogue to the story. On Thursday the prisoner was taken to be executed. And he was very surprised. So the judge's orders were successfully carried out.

If we analyze the paradox contained in the above story, we see that the conditions that the judge has set up result in a conclusion that none of the days meets, because, as the prisoner so adroitly points out, each one of them in turn would not be a surprise. But the conclusion itself changes the situation, and now surprise is possible again. This brings us back to the original situation in which the prisoner could (in theory) demonstrate that each day in turn would be impossible, and so on. The judge applies Alexander's solution to this Gordian knot.

A simpler example and the one that Russell actually struggled with is the following question about sets: Consider set A, which is defined to contain all sets that are not members of themselves. Does set A contain itself? As we consider this famous problem, our first realization is that there are only two possible answers: yes and no. We can therefore exhaustively consider all of the possible answers (this is not the case for many problems in mathematics). Let us try "yes." If the answer is yes, then set A does contain itself. But if set A contains itself, then according to its defining condition set A would not belong to set A, and thus it does not belong to itself. Since the assumption that A contains itself led to a contradiction, it must have been wrong. If the answer is "no," then set A does not contain itself. But again according to the defining condition, if set A does not belong to itself, then it would belong to set A. As with the story about the prisoner, we have contradictory proposition that imply one another. The assumption of no yields yes, which yields no, and so on.

This type of paradox may seem amusing, but to Russell it threatened the very foundations of mathematics. The definition of set A appears to be a perfectly reasonable one, and the question of whether set A belongs to itself also appears perfectly reasonable. Yet it cannot be answered. Without a resolution to this paradox the basic theory of mathematics was in question.

To solve the problem, Russell invented a concept of a logical transformation as an operation that requires the equivalent of a quantum of time. Russell designed a set of logical operations in which a particular problem would be expressed as a "program" of operations to follow. We then turn the program on and let it run. Each logical inference or other transformation is implemented in turn, and when the process is completed, we get our answer. If we apply this theoretical machine to the problem of set A, the logical operations are "executed" in turn. At a certain point the answer will be yes, but the program keeps running, and at a later point the answer becomes no. The program runs in an infinite loop, constantly alternating between yes and no.

Russell then provides narrow and broad definitions of a set. In the narrow sense, a set has a definition that allows the construction of a program that can determine whether a given entity is a member of the set in a finite amount of time. According to this definition, set A (whose program produces an infinite loop) is not a true set, so the paradox is eliminated.

In the broad sense, the program defining the logical rules of set membership need not come to a halt in a finite amount of time, it just needs to come to an answer in a finite amount of time; it is allowed to change that answer as the program continues to run. According to this definition, set A is a proper set. The question of whether set A belongs to itself will be yes at one point in time and no at another point, and the program will alternate between the two. Thus, logical inferences are not implemented instantly, but rather one at a time with an orderly change of state between each. In our case, the answer is never yes and no at the same time. In the broad definition, set A is a particular type of set that is "unstable," just as an electronic circuit can be unstable. Nonetheless, the contradiction is eliminated.

Russell does not explicitly refer to time in his theory of types (of sets). He provides procedures for allowable transformations on propositions that can be considered meaningful within a logical system. This contrasts with the transformations generated by the logical systems itself, which are used to determine the truth or falsity of propositions. Thus, according to Russell, certain propositions are neither true nor false and cannot be addressed by the axioms. In our discussion above, a proposition concerning an "unstable set" would not be meaningful. The theory is interesting in that we have one set of transformations generated by the axioms of a logical system determining truth or falsity ad another set of transformations generated by the metarules of Russell's theory of types determining meaningfulness. Russell's transformations are algorithmic in nature, and the issues raised are similar to certain issues in computation theory that received attention after Turing devised his Turing machine. Though Russell did not explicitly link the theory of types to computation theory (otherwise, we might be referring to a Russell Machine rather than a Turing Machine as a primary model of computation. Russell's theory of types clearly provided a foundation for Turing's later work.

The lecture on logic delivered by the prisoner changed the situation. He has shown quite logically why it is not possible for him to be executed following the judge's instructions. The judge then realizes that the prisoner's belief that he cannot be executed makes it possible once again to execute him. Before the prisoner can formulate another lecture on logic (that is, before the "program" simulating this situation can alternate again to "impossible to execute"), the judge quickly implements his sentence.

Principia Mathematica

Russell expanded his theory to lay a new foundation for logic and the theory of sets in his first major work in mathematics, The Principles of Mathematics, published in 1903. He subsequently felt that all of mathematics should be recast in terms of his new theory of sets, since the concept of sets and their interactions is fundamental to all other mathematical disciplines. With the help of his friend and former tutor Alfred North Whitehead (1861-1947), he labored for nearly ten years to apply his new theory of sets and logic to all realms of mathematics. Russell reported that the effort nearly exhausted him, and even late in his life he felt that this had been the most intense work of his extremely prolific career. It was probably the most influential. As it was, Whitehead and Russell did not manage to complete their reexamination. They nonetheless published their work in three volumes in 1910, 1912, and 1913 under the title Principia Mathematica. The work was truly revolutionary and provided a new methodology for all mathematics that was to follow.

As significant as Principia was to mathematics in general, it was a pivotal development in terms of the foundations of the theory of computation that would be developed two decades later. Russell had created a theoretical model of a logic machine, which we now recognize as similar to a computer, particularly in its execution of logical operations in cycles. Indeed, Turing's subsequent theoretical model of a computer, the Turing Machine, has its roots directly in Russell's theoretical logic engine. Russell also created a concept of a logical programming language that is remarkably similar in many respects to one of the most recent programming languages, PROLOG, developed originally in France and now the basis for the Japanese Fifth Generation Computer project. Principia was also influential on efforts by Allen Newell, Herbert Simon, and J.C. Shaw to develop theorem-proving machines in the 1950s.

Modern set theory, still based on Russell's Principia, provides a foundation for much of mathematics. It is interesting to note that modern set theory is in turn based on Russell's theoretical model of computation. Viewing things in this way, we could argue that mathematics is a branch of computation theory. What is particularly impressive about Russell's achievement is that there were no computers even contemplated at the time he developed his theory. Russell needed to invent a theoretical model of a computer and programming to address a flaw in the foundation of logic itself.

Back


Copyright © 1996, Kurzweil Technologies, Inc.