PART iii
"Mathematical
Roots"
"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.
The Age of Spiritual Machines