Newell’s example of a good thesis was
Floyd’s example of a bad one.
The disputed thesis presented an
AI program that would generate parsersh from grammars. Newell considered it good because it demonstrated
that AI could solve practical problems.
Floyd, a pioneer in the field of parsing,
explained that nobody could tell him
what class of grammars the AI parser
generator could handle, and he could
prove that that class was smaller than
the class of languages that could be
handled by previously known mathematical techniques. In short, while
the AI system appeared to be useful, it
was inferior to systems that did not use
heuristic methods. Bob Floyd taught
me that an AI program may seem impressive but come out poorly when
compared to math-based approaches.
An AI System that “Understood”
Drawings and Text
A 1967 AI Ph.D thesis described a program that purportedly “understood”
both natural language text and pictures. Using a light pen and a graphics display,i a user could draw geometric figures. Using the keyboard, users
could ask questions about the drawing.
For example, one could ask “Is there a
triangle inside a rectangle”? When the
author demonstrated it, the program
appeared to “understand” both the pictures and the questions. As a member
of the examining committee, I read the
thesis and asked to try it myself. The
system used heuristics that did not always work. I repeatedly input examples
that caused the system to fail. In production use, the system would have
been completely untrustworthy.
The work had been supervised by
another Turing Award recipient, Herbert Simon, whose reaction to my observing that the system did not work
was, “The system was not designed for
antagonistic users.” Experience has
shown that computer systems must
be prepared for users to be careless
and, sometimes, antagonistic. The
techniques used in that thesis would
not be acceptable in any commercial
h Parsers, an essential component of compilers,
divide a program into its constituent parts.
Before Floyd’s work, parsers were created by
humans. Floyd’s algorithm automatically gen-
erated parsers for a large class of languages.
i Advanced hardware for the time.
professor Joseph Weizenbaum.
3 In the
mid-1960s, he created Eliza, a program
that imitated a practitioner of Rogeri-
an psychotherapy.d Eliza had interest-
ing conversations with users. Some
“patients” believed they were dealing
with a person. Others knew that Eliza
was a machine but still wanted to con-
sult it. Nobody who examined Eliza’s
code would consider the program to
be intelligent. It had no information
about the topics it discussed and did
not deduce anything from facts that
it was given. Some believed Weizen-
baum was seriously attempting to cre-
ate intelligence by creating a program
that could pass Turing’s test. How-
ever, in talks and conversations, Wei-
zenbaum emphasized that was never
his goal. On the contrary, by creating
a program that clearly was not “intel-
ligent” but could pass as human, he
showed that Turing’s test was not an
Robert Dupchak’s Penny-Matcher
Around 1964,e the late Robert Dupchak,
a CMU graduate student, built a small
box that played the game of “penny
matching.”f His box beat us consistently.
Consequently, we thought it must be
It was Dupchak who was intelligent—not his machine. The machine
only remembered past moves by its
opponent and assumed that patterns
would repeat. Like Weizenbaum, Dupchak demonstrated that a computer
could appear smart without actually
being intelligent. He also demonstrated that anyone who knew what was inside his box would defeat it. In a serious application, it would be dangerous
to depend on such software.
A popular topic in early AI research and
courses was the character recognition
problem. The goal was to write pro-
grams that could identify hand-drawn
or printed characters. This task, which
most of us perform effortlessly, is dif-
d Practitioners of Rogerian psychotherapy echo
the patient’s words in their responses.
e Dupchak’s accidental death prevented publi-
cation of his work. I cannot give a precise date.
f Penny-matching is a two-player game. Each
player uses a coin to make a head or tail
choice. One player wins if both pick the same
face; the other wins if the choices are different.
ficult for computers. The optical char-
acter recognition software that I use
to recognize characters on a scanned
printed page frequently errs. The fact
that character recognition is easy for
humans but still difficult for comput-
ers is used to try to keep programs from
logging on to Internet sites. For exam-
ple, the website may displayg a CAPT-
CHA as shown here
and require the user to type “s m w m.”
This technique works well because the
character recognition problem has not
Early AI experts taught us to design
character recognition programs by interviewing human readers. For example,
readers might be asked how they distinguished an “ 8” from a “B.” Consistently,
the rules they proposed failed when implemented and tested. People could do
the job but could not explain how.
Modern software for character recognition is based on restricting the
fonts that will be used and analyzing
the properties of the characters in those
fonts. Most humans can read a text, in
a new font without studying its characteristics, but machines often cannot.
The best solution to this problem is to
avoid it. For texts created on a computer, both a human-readable image and a
machine-readable string are available.
Character recognition is not needed.
An AI System for
As a new professor, I made appointments with three famous colleagues to
ask how to recognize a good topic for
my students’ Ph.D theses. The late Alan
Perlis, the first recipient of ACM’s prestigious Turing Award, gave the best answer. Without looking up from his work,
he said, “Dave, you’ll know one when
you see it. I’m busy; get out of here!” Two
other Turing Award winners, the late Allen Newell and the late Robert Floyd,
met with me. Separately, both said that
while they could not answer my question directly, they would discuss both a
good thesis and a bad one. Interestingly,
g This example was found in Wikipedia.