% eaicl2-ch1.tex
% (C) Copyright S. L. Tanimoto, 1993 and W.H. Freeman. Inc.
%. All rights reserved.
% Permission is granted to the students of CSE 326 at the
% University of Washington to use this file in text compression
% experiments.

% The Elements of Artificial Intelligence Using Common Lisp
% Chapter 1 (Introduction)

\input{../eaicl2-defs}

\setcounter{chapter}{0}

\chapter{Introduction}
\section{An Intellectual and Technical Challenge}

Artificial intelligence (AI) is the art of
developing, and the science of
understanding, computer systems that reason,
learn, perceive, understand, solve problems,
communicate, and possess knowledge.
Part of AI emphasizes developing practical systems, while the other
part focuses on understanding the mechanisms of thought and intelligence.

People have been trying to create intelligent computer systems
since the early days of computers.
It is a tempting and exciting activity.
The design of a system that possesses and further acquires large
amounts of knowledge and that reasons deeply with that knowledge
to solve real problems is perhaps the ultimate intellectual
challenge.
In this chapter, we consider the questions
``Why pursue artificial intelligence?''
``What is intelligence?''
and ``Why is artificial
intelligence difficult to achieve?''

What could be a more intense intellectual experience than
creating an intellect?  Human intelligence is applied in every aspect
of our culture.  In building an intelligent machine, one might become
involved in any aspect of human culture.

Like statistics, artificial intelligence (AI) brings a
collection of techniques
that can be applied in other fields such as history, biology,
or engineering.  Like philosophy and mathematics, AI is concerned
with reasoning, but unlike either statistics or philosophy, artificial
intelligence gets deeply involved with the theories and meanings in
the subjects to which it is applied.  The application of artificial
intelligence to history might easily require that a theory about the rise
and fall of nations be reworked and formalized and that new representations
be designed for describing historical events such as battles.
Whereas statistics\index{statistics!compared with AI} may help to justify or refute a hypothesis, artificial
intelligence may produce the hypothesis or show an inconsistency with it.
Its wide applicability and the great depth with which it can embrace a
subject make artificial intelligence unique and powerful, and
for this reason AI may be the most interdisciplinary field of study
taught in universities.

\subsection{A Historical Skepticism}

While artificial intelligence presents a fascinating vision,
we must acknowledge that the highly knowledgeable, broadly able
automated problem solver is a difficult goal to achieve.
Quite a few prominent people have declared AI to be
impossible.  Here are some simplified but popularly held views:
\begin{quotation}

It is not possible for a machine to think.

Computers can deal only with zeros and ones.

Only natural things like people and animals can
have intelligence.

\end{quotation}

The prospect of intelligence in machines has produced widespread skepticism\index{skepticism!about AI}.
There are two main reasons for this.  First,
until recently, there have been relatively few examples of machine expertise
that were in the public eye.  Furthermore,
AI is sufficiently complicated that it is difficult for the
uninitiated to understand.  Without seeing any artificial thing
behave intelligently and without understanding how AI techniques work,
it is hard to believe that it could be possible.

A second reason for the skepticism has to do with people's
perceptions of themselves.  Most people hold their
own intelligence close to their hearts.  People often feel that intelligence
is what gives them their significance and their identity in our complicated
world.  The possibility that a machine might possess intelligence can
be frightening.  ``If intelligence is something mechanical, then am I
nothing better than a machine?''
Machines are supposed to be subservient to humans.
What is to be the status of human beings if we can no longer claim to be the
smartest of earthly beings?  Many people would rather believe that
machine intelligence is impossible than try to answer some of these questions.

\subsection{Artificial Intelligence in Action}

Let's consider some systems that have been developed in industry and
research centers which
incorporate AI.

The health-care\index{health care}
field provides many opportunities for applying AI.
As one example, let us consider the
process by which an insurance company processes a claim from
a hospital after an operation has been performed.
The claim will list various expenses including laboratory tests,
medication, the operation itself, postoperation visits by
physicians, etc.  Depending on which medical plan the
patient belongs to, various costs are allowed.  However,
the current version of the American Medical Association's
{\it Physicians' Current Procedural Terminology}\/ provides a very
complex coding for the various medical procedures, so it is
common for physicians to make mistakes in billing.  Often a
whole procedure, that would be covered at a fixed rate under
the plan is billed as a number of smaller procedures in what is
called ``unbundling'' with the effect of claiming a larger amount
of money.  Experienced claims adjudicators must catch these
errors and determine the proper amount to reimburse the hospital.
This process is time-consuming and costly.  Recognizing this
inefficiency, a team led by J.~Little and M.~Gingrich
\index{-Little, J.}\index{-Gingrich, M.}
at United HealthCare Corporation designed
and implemented an expert system, ADJUDIPRO\index{ADJUDIPRO}, which
was integrated with the existing information system for claims
processing.  ADJUDIPRO came into production use in March of 1991.
It uses a knowledge base of 461 rules to
handle a great many of the claims automatically.  Each claim
is either approved, denied, adjusted, or referred to a human expert.
For the referred claims,  ADJUDIPRO assembles a presentation
of the case to the expert.  ADJUDIPRO has reduced the time
needed to process claims and generated an estimated annual cost savings
equal to a 36.3 percent return on investment over a five-year period.

Let us now consider an example from an industrial factory context.
An automatic tube inspection system based on computer vision\index{vision!tube inspection}\index{tube inspection}\index{inspection!automatic}
shows one application of artificial intelligence in manufacturing.\index{manufacturing!tube inspection}
In order to build an airplane, a company such as Boeing must
make many tubes that will
carry cables and fluids through the fuselage and wings of the craft.
A tube is made from a straight piece of pipe stock by passing it
through a numerically controlled bending machine.
The machine works by feeding a length
of pipe, making a bend of a predetermined amount, rotating
the pipe a programmed amount, and then repeating this process to make
more bends until a tube with the precise combination of bends
has been produced.  The problem of inspecting the resulting
tubes for accuracy is difficult for humans because the 3-D shape of the
tubes may necessitate observing many poses and making many measurements
at each pose.  W.~Grimson\index{-Grimson, W.} and co-workers developed a computer-vision
system that automatically inspects such tubes.  It uses laser scanning
to obtain accurate image information, and it analyzes each tube into
cylindrical components.  The system then matches
these cylindrical components with the parts of
a stored model of the correct shape of the tube.
The tube inspection system has an accuracy of $\pm0.008$ inch
and handles a typical 6-foot-long, 5-bend tube in less than 2 minutes.

As a third example, consider the Internet
Softbot\index{softbot}\index{Internet
  Softbot}\index{agent!softbot}\index{intelligent
  agent}\index{software agent} developed by O. Etzioni and his
associates\index{-Etzioni, O.} at the University of Washington in
1994.  Given a task such as to find the e-mail address of David
McAllester\index{-McAllester, D.} at MIT, the Internet Softbot uses
its knowledge about how to find and analyze technical reports to hunt
down an e-mail address.  It employs a Unix shell and the World-Wide
Web\index{World-Wide Web!softbot} to access information on the
Internet.
It can change its environment through the use
of ``effectors,'' which include the software applications
FTP (file-transfer protocol), TELNET, MAIL, and a variety of
local file-manipulation commands.  It can sense information in
its environment using ARCHIE, GOPHER, NETFIND, and other facilities.
Unlike a single tool which might provide precisely one way to
search for a resource on the network, the Internet Softbot
draws on a collection of pieces of knowledge that it can apply
flexibly to work around gaps in the information in the environment.
It also can adapt to transient conditions such as a database
server's being down.
This flexibility permits the Internet Softbot to
serve the user as an intelligent
agent, automating what might otherwise be a tedious search procedure.

These three systems exemplify techniques in three areas of AI:
rule-based systems, computer vision, and robotics planning.
Much progress has also been made in other areas of AI, including
representation of commonsense knowledge, logical
inference and consistency systems, planning, probabilistic reasoning, speech
understanding, text understanding, neural networks, and genetic
algorithms.  Let us mention just a few of the
many other accomplishments of AI.

In the late 1950s and early 1960s, much of the research that went
by the name of artificial intelligence was concerned with getting
machines to play games.  An early success was the checkers-playing\index{checkers!Samuel's program}
program of Samuel.\footnote{See {\it Computers and Thought}, mentioned in
Section 1.7.}\index{-Samuel, A.}  It could beat most humans at the game,
and it could improve its technique through automatic learning.
Today computers play good chess, backgammon, and many other
games.

In the 1970s artificial intelligence made significant progress in
new methodologies for real-world problems.
AI programs have demonstrated that computers can reason effectively
with uncertain information using Bayesian methods.  The now-classical program
MYCIN\index{MYCIN} prescribed treatment for infectious diseases, after gathering
information about symptoms in dialogs with users.
\index{medicine!MYCIN}
Another program,
PROSPECTOR,\index{PROSPECTOR} analyzed geological information obtained from field observations,
and made predictions about minerals that might be found at a site.
\index{minerals prospecting!PROSPECTOR}
\index{geological exploration!PROSPECTOR}
Both programs employed knowledge bases built with the help of
specialists (``experts'').  Yet another well-known program, called XCON,\index{XCON} whose
development was sponsored by Digital Equipment Corporation, automatically
determined optimal configurations of VAX computers according to customer
needs and the available options.

Translation of written documents from one language to another requires
deep knowledge of both languages as well as the subject matter
under discussion.\index{machine translation}  Machine-aided German/English translation is now
performed in a practical way, combining the human's deep knowledge
with the computer's speed and facility with dictionaries and syntax.
Computers are also handling semantics; they translate questions phrased
in English into database queries.  This eliminates the need for users
of a database to know a strange query language or to write programs.

One of the great current challenges of AI is getting machines to
know things at a level and reason in a manner that humans take for granted:
``common sense.''  There is so much knowledge that we assume our
listener knows when we speak, that a two-hundred worker-year effort has been
dedicated to building a representation of all this commonsense
knowledge and basic reasoning ability.  The ``Cyc'' system was started
in 1985 at the Microelectronics and Computer Technology Corporation
(MCC) in Austin, Texas, with the objective of creating a base of
knowledge and commonsense reasoning ability that would allow expert
systems not to be ``brittle'' (i.e., not to fail as soon as they are
given a question slightly outside their narrow domain of expertise).
The knowledge would also allow them to acquire more expertise
(a system cannot learn effectively without already having quite a
bit of basic knowledge). Thus far, the project has created a
remarkably large knowledge base and come up with many innovative
design ideas for the representation of, and access to, such information.
Real applications of Cyc are not yet out (as of mid-1994) but on the horizon.


\section{What Is Intelligence?}

Intelligence is a property we usually attribute to people.  The word
is used in many different ways, and it's worth considering some of
these uses in detail.

\subsection{Aspects of Human Intelligence}

``She's intelligent,'' a student might say, referring to a classmate.
Different people will interpret
this sentence in different ways.
\index{intelligence!human}  Some take it to mean
``She knows a lot.''  Others would say it means ``She thinks rapidly,''
or ``She talks a mile a minute.''
People who have thought about thinking find these
interpretations simplistic.  Someone can be quick yet stupid, and
one can know a lot of facts but have difficulty putting information
together in a creative fashion.  A somewhat more satisfactory
interpretation might be ``Her actions are appropriate to each
situation.''  Of course, one might complain that this statement is
overly general and does not concentrate on the concept of intelligence
sufficiently.

Important aspects of human intelligence are
the use of
perception, interpretation, comprehension, adaptation,
 intuition, common sense, judgment, creativity,
goal-directedness, plausible reasoning\index{plausible reasoning}
(``if {\it A} happens, then {\it B} might
happen, and if so, then {\it C} might \ldots''), knowledge, and beliefs.
While human intelligence is powerful and
deep, there certainly are limits to it; humans are intellectually fallible,
they have limited knowledge bases (no man or woman can read every book or have
every kind of experience), and information processing of a serial nature
proceeds very slowly in the human brain when compared with today's computers.
Thus, the meaning of ``intelligence'' is not ``the human brain's
information-processing ability.''  However, intelligence is a quality that
much of human information processing has and which one might hope to find in
other creatures or in machines.

\subsection{Communication}

One way that people demonstrate their intelligence is by
communicating effectively (through text, pictures,
verbal expression, or another medium).

Effective communication\index{communication} requires skills both in analysis of messages
(reception) and in synthesis of messages (transmission).  In order to
communicate something effectively, one must be able to synthesize a
message, whether it be a letter, paper, poem, musical composition,
painting, or other form of communication, in such a way as to express
one's meaning to one's intended recipient or audience.  Doing this
well may require making judgments about  the level of sophistication
of a recipient, careful use of language, and proper speed of presentation.

On the
other hand, understanding a message also requires intelligence.  A listener
must know the meanings of most of the words a speaker is using,
and the listener must
have some knowledge of the context for the message.
It is usually necessary for the listener to use contextual knowledge to
constrain the possible interpretations of a message.
In addition, the
receiving person may need
to be able to formulate pointed questions to gather any bits of
lacking information  that are necessary to understand the message.  In
either synthesis or analysis of a message, skills are generally
required in determining
context and in altering the representation of information.

\subsection{Learning}

Another key aspect of intelligence is learning.  People may
demonstrate their intelligence by learning, that is, acquiring
new knowledge through experience, and
then demonstrating that they have learned the knowledge by communicating.

\index{learning}The ability to learn or adapt one's behavior to new 
situations is a vital component of intelligence.
Animals that can change in response to changes in their environment
are considered generally to be more clever than those unable to change
their behavior.  The kind of learning that people exhibit is
more sophisticated than that of animals;
people can reflect on knowledge, whereas lower animals cannot.
However, it is likely
that many of the basic mechanisms of learning are common to both
humans and other animals.

What is involved in learning how to deal with a new kind of situation?
There are four important aspects of this learning.
One must first learn what the major concerns are in the new context.
For example, a new soldier suddenly thrust into war must quickly
perceive its objectives and use that information as a
framework in which to insert knowledge gained later.  A second aspect
of learning is finding out what the basic descriptive units are in a
situation.  For example, in learning language, one must learn that
phonemes (and at the next level words and then phrases and sentences)
are structural units with which descriptions of experience can be
formed.  Learning these structural units is essential in all kinds of
learning experience.  In learning to see, one gradually becomes acquainted
with such distinctive features as corners of human-made objects (such as
buildings and furniture).  Colors, textures, and shape features are
gradually acquired as tools with which to describe (consciously or
subconsciously) visual experience.  The third aspect of learning is the
acquisition of the rules for combining primitive descriptors.  How do
words go together? How can a description of an object be composed from
shape, color, and texture features?  Both syntactic models and
semantic models must be acquired for each knowledge domain.  Learning
progresses as such models become more and more sophisticated in order
to understand the domain more deeply.  The fourth aspect is the organization
of knowledge into an appropriate framework.

Organizing knowledge is an important component of the learning process.
Just how pieces of information are related to one another and arranged
in
memory is a very important issue.  Facts must
be accessible when needed.  Skills must come into play readily when
the appropriate situation arises.  Knowledge must be structured in
such a way that further learning can take place smoothly.  Part of
knowledge is a framework in which various facts and aspects of
experience can be stored.  The framework must make it possible
for associations to be made between old and new when the old and new
are related.  The kinds of knowledge that must be stored in the
framework must include both specific facts and general rules.

\section{What Artificial Intelligence Is}

\subsection{A Field of Study}

\index{artificial intelligence!definition}Artificial intelligence is a field of study that encompasses
computational techniques for performing tasks that apparently
require intelligence when performed by humans.
Such problems include diagnosing an engine malfunction in an automobile,
debugging a computer program, prescribing therapy for a
cancer patient, designing a faster computer, writing
a science-fiction novel, composing a sonata, proving a
theorem in geometry, assembling and inspecting washing machines in factories,
tutoring a student in physics,
and negotiating an international treaty.
It is a technology
of information processing concerned with processes of reasoning,
learning, and perception.

Fundamental issues of artificial intelligence involve knowledge
representation, search, perception, and inference.  Knowledge can be
available in many forms: collections of logical assertions, heuristic
rules, procedures, statistical correlations, etc.  Much of AI is
concerned with the design and understanding of knowledge representation
\index{knowledge representation}
schemes.  How can knowledge be represented so that it (1) can be
easily used in reasoning, (2) can be easily examined and updated, and
(3) can be easily judged as relevant or irrelevant to particular problems?

Search\index{search} is a key issue because it is usually easy to invent brute-force
algorithms to solve problems, but they fail on all but ``toy'' problems.
An understanding of search techniques can help us to avoid the
``combinatorial explosion''\index{combinatorial explosion}
that swamps the brute-force attempts.

Inference\index{inference} is the process of creating explicit representations of knowledge
from implicit ones.  It can be viewed as the creation of knowledge itself.
Deductive inference\index{inference!deductive} proceeds from a set of assumptions called ``axioms'' to
new statements that are logically implied by the axioms.  Inductive
inference\index{inference!inductive} typically starts with a set of facts, features, or observations,
and it produces generalizations, descriptions, and laws that account for
the given information and which may have the power to predict new
facts, features, or observations.

\subsection{AI: Art or Science?}

      One  difference  between  a science and an  art  is  that  a
science\index{science vs art}  consists,  in good part,  of a body of proved principles
that  have  been  abstracted from  nature  through  processes  of
empirical  inquiry  and logical deduction.   That  physics  is  a
science is not contested.   On the other hand,  an art is for the
most part a collection of techniques,  developed pragmatically to
a  sophisticated  level,  but not necessarily in a  logical  way.
Most  cooks  would  agree that cooking is an art  rather  than  a
science.

     Artificial  intelligence is both an art and a science.   The
activity of developing intelligent computer systems employs  both
proved  mathematical  principles,  empirical results of  studying
previous   systems,    and   heuristic,   pragmatic   programming
techniques.  Information stored in relational data structures can
be  manipulated  by well-studied techniques of  computer  science
such   as   tree-searching  algorithms.    At  the   same   time,
experimental  or vaguely understood rules of thumb for  problem
solving  are often crucial to the success of a system and must be
carefully accommodated in intelligent systems.

Many researchers in AI believe in or assume
what is called the ``physical symbol system hypothesis.''
This is the idea that thought (whether by humans or machines)
can be effectively modeled and simulated by the use of formal
systems of symbols (including the  processing of structures made of those
symbols).\index{physical symbol system hypothesis}
This contrasts with other theories --- for example, that thought is based on
holographic representations in the brain or is best understood
in terms of the electrodynamics of a ``hormonal soup'' interacting
with a network of neurons in the brain.  (For these and
other metaphors for AI, see [West and Travis 1991]).
Understanding thought is
a question for science, and yet the building of simulations to
test or demonstrate such theories is largely an art.

     The   field   of   AI  is  fascinating   because   of   this
complementarity of art and science.   There is a lot of room  for
creativity  in  AI, yet  there is a growing body of  mature
ideas  that  are giving more rigorous support  to  the
practice of AI.

\subsection{Purpose}

The most important purpose\index{purpose!of AI} of artificial intelligence
is to increase our understanding
of reasoning, learning, and perceptual processes.  This understanding
is desirable for two reasons: it is needed in order to build useful new
tools, and it is needed in order to achieve a more mature view of
human intelligence than currently exists.  The development of new tools
is important because they may have commercial value, they may improve
the quality of our lives through better products or entertainment,
or they may increase the efficiency of governments
and companies.  In the author's opinion, a deeper
understanding of human intelligence and its
limitations is extremely important, for it might lead to suggestions
for partially resolving many of the political\index{politics} and religious\index{religion}
disagreements in the
world that currently pose a threat to civilized society.

\section{Artificial Intelligence Comes of Age}

\subsection{Growth of the AI Research Community}

        While the intellectual challenge to designers of artificial
intelligence has been with Western civilization for centuries, it is
only very recently that a glint of practical feasibility has shown on
a wide variety of applications.  During the early and mid-1960s,
overly ambitious projects in automatic English/Russian translation\index{machine translation} not
only failed to produce the promised systems, but dampened respect and
enthusiasm for AI as a field.  Critics of AI, of whom some were
very anticomputer
as well, lambasted these early failures and claimed that AI is impossible,
although their arguments, typically couched in the vague terminology of
phenomenological philosophy\index{philosophy!phenomenological}, have always been fallacious.

        Today, however, the field has recovered.  Many
scientists, engineers, and programmers are studying AI
techniques and building AI systems.  National and international
organizations dedicated to AI have been formed and are growing.
In the United States, the American Association for Artificial Intelligence
now holds a conference each three out of four years, at which research
results are reported, tutorials are offered, and an exhibition of
equipment and books is held.

The pendulum may even have swung back too far.  Amidst the current
excitement about AI, some voices are making claims that cannot
be substantiated.  It is the hope of the author that this book
will help in some small way to keep the field on an even keel by
presenting the elements of artificial intelligence as they
are, describing their limitations as well as their assets.

\subsection{Industrialization of AI}

\index{application of AI}
Unlike the early 1960s, today a much deeper understanding
of the problems and solutions in the major domains of AI provides a solid
base for many AI systems and ventures.  The intricacies of natural language
translation are not yet completely understood.  However, enough is
known to permit useful systems to be constructed; several commercial
ventures were launched during the mid-1980s in computer-assisted language
translation.  Machine vision became practical during the 1970s and
1980s in areas of robotics,
biomedical microscopy, and materials analysis, even though a good many
basic questions of vision have yet to be answered.  The market for
expert systems and tools for constructing them has been very
active since the mid-1980s.

\subsection{Integration of AI}

Whereas the mid-1980s saw a proliferation of efforts to create
expert systems, the early 1990s has witnessed a gradual change
to a different way of applying artificial intelligence --- what
we might call ``embedded AI'' or ``integrated AI.''  For example,
the ADJUDIPRO system mentioned earlier is one component of a larger
information system that tracks and processes health-insurance claims.

The reason that embedded AI systems are catching on is that 
intelligent systems usually must process information; they might
as well be plugged right into the source or main repository
of the information.  Thus we are more and more frequently finding
AI technology integrated into database systems, information networks,
stock-market information systems, and sensory-data processing
systems.  Much as the microcomputer gradually escaped from the
confines of ``computer systems'' and showed up in automobile
brake control systems, appliance control systems, and the like,
it is now reasonable to expect to find artificial intelligence technology
in portable telephones,  high-fidelity sound and television sets,
and industrial machine tools.


\subsection{Segmentation of the AI Literature}

While AI applications are becoming more ``integrated,'' another trend
is occurring at the research level.
The 1980s and the early 1990s have seen the artificial
intelligence research community gradually divide up into
a number of more specialized communities.  Although there remain
large regional and international conferences (e.g., the
International Joint Conference on AI), there are now many
conferences on more specific areas that draw many attendees
(e.g., the International Conference on Machine Learning
and the International Conference on Computer Vision).
It is natural that as AI matures as a field, it spawns
various communities of specialists.

\subsection{What an AI Practitioner Does}

\index{employment!in AI}\index{careers in AI}
As has been the case since 1985,
for the next decade the majority of artificial intelligence
engineers are likely to be designing expert systems.  Their jobs will
often be to work with experts in particular fields such as medicine,
corporate finance, astrophysics, and anthropology to develop suitable
representations for the knowledge in each field.  The knowledge must be
put into a form on which useful inferences can be made automatically.
Such work is challenging and at the forefront of the information
revolution.

        In addition to developing knowledge representations, suitable
displays and means of access must be designed for users.  Natural language
and CRT interfaces must be designed, often with capabilities particular
to each application.  The integration of multiple media (e.g., speech input,
graphic output, pen input, etc.) is a challenge of particular current interest.


After an expert system has been designed and debugged, it may
require maintenance\index{expert system!maintenance of}.  New knowledge must be added; heuristics found to
be inferior need to be replaced; new technology may need to be incorporated.
There is usually room for improvement in fields such as medical diagnosis,
mathematical theorem proving, anthropology, etc.  Postinstallation changes
to expert systems are likely to keep AI practitioners in work for a long
time to come.  Since AI systems are increasingly serving as components
of larger information systems, much work will consist in keeping these
components compatible and communicating at an appropriate level of
abstraction.  The trend toward global networking will place greater
and greater demand on data translation facilities, knowledge indexing
systems, and autonomous software agents that search or monitor
information sources.

Other people involved with artificial intelligence
will be scientists continuing to study basic mechanisms
of perception, reasoning, learning, problem solving, and
communication.   The field is sufficiently rich that
many basic issues, such as optimal search, probabilistic reasoning, and
inductive inference, will provide open problems for many years.

\section{Philosophical Challenges}

\index{philosophy}
The existence of artificial intelligence puts a new light on
much of philosophy.  ``Can a machine think?''  People often feel
threatened by the possibility that a machine can think.  It suggests
that they, too, are machines or no better than machines.
Without an understanding of how the machine works, the intelligence
of the machine is a mystery to them, and the machine may seem to
be an instrument by which the machine's creators might replace or overpower
and control them.

People argue this question
at higher levels of sophistication than in the past, but the debate
continues.  An excellent presentation of some of the views on this may
be found in Pamela McCorduck's book, {\it Machines Who Think}.

\subsection{Turing's Test}

\index{Turing test}
One of the philosophical problems of AI is also a practical problem.
How can one tell when (artificial) intelligence has been achieved?
A manager who wants to evaluate an AI project may well wish to
augment economic or marketplace criteria with another approach.
Researchers in AI also need a way of evaluating their work that
is understandable to the layperson.\index{Turing test}

The traditional answer to this question is that
artificial intelligence is manifested in a machine when the machine's
performance cannot be distinguished from that of a human performing
the same task.  This answer is based on a suggestion by Dr. Alan Turing
that comparison with a human be the criterion by which it is
decided whether or not a machine can think.  Turing's test
is to put a human and a machine in one room, and another human,
the ``interrogator,'' in a separate room, perhaps as illustrated in
Figure\ \ref{Turingtest}.
\begin{figure}[tb]
\eaifig{ch1/ch1fig1}
\caption{Turing's test.  The interrogator (a human) must distinguish the other human from the machine.}
\label{Turingtest}
\bottomfigrule
\end{figure}
The interrogator may
ask questions of either the other human or the machine, referring to
one as A and the other as B.  However, the interrogator is not told
whether A or B is the human or the machine.  The interrogator
cannot see or hear the others but passes messages through an intermediary,
which could be an electronic mail system or another person.
As they respond to questions, A and B each compete with one another to convince
the interrogator that he or she or it is the human.  If the machine can win,
on the average, as often as the human, then it passes the ``Turing test,''
and, by this particular criterion, can think.  In practice, the outcome of
such a test would probably depend heavily on the humans involved, as
well as the machine.
In the absence of a stronger evaluation method, a Turing test,
suitably arranged, can sometimes provide a useful method of evaluation for
an AI system (e.g., see [Chow et al. 1993] or [Agarwal et al. 1993]).

As we grow more sophisticated, we realize that the question of whether
a system is intelligent is a shallow one.
We should be asking about the kinds, quality, and quantity of knowledge in
a system, the kinds of inference that it can make with this knowledge,
how well directed its search procedure is, and what means of automatic
knowledge acquisition are provided.  There are many dimensions of intelligence,
and these interact with one another.

\subsection{AI and Human Beliefs}

\index{belief!human}
Studies in several areas of AI---concept formation, abstraction hierarchies,
belief representation, and truth maintenance systems---provide plausible
explanations for some intellectual limitations of human beings.
People develop prejudices by automatically forming generalizations even
when it is statistically invalid to do so.  People are willing to adopt
fantastic beliefs and maintain them in light of serious inconsistencies,
provided the beliefs supply plausible explanations for certain questions
that are emotionally central.  What are beliefs?  Can they or should they
be represented in systems as if they were knowledge?  Is a man or a woman
just the sum of his or her beliefs?  Can a person or personality be
represented in a machine?  If so, does this permit a kind of morality or
immorality to be developed?\index{religion}
What kinds of laws should there be to regulate societies of intelligent
machines?

The fact that AI raises so many of these sorts of questions contributes to
the excitement of an involvement with artificial intelligence.
For years, most scientists have treated computers as unintelligent tools.
More and more people are realizing not only that computers are changing
the way our society processes data, but also that the ideas of computing are
bringing some intellectual traditions into question,
changing how we think about ourselves.
AI is at the forefront of this computer
revolution.\index{revolution!computer}

\section{Organization of Artificial Intelligence}

The subject of artificial intelligence is usually divided up according
to its different techniques and challenges.  This book divides it
into four principal parts: (1) symbolic representation, (2) inference,
(3) communication, and (4) application.  The first part comprises
languages such as Common Lisp for representing and manipulating
symbolic information and methods for the representation
of knowledge.  The second part includes logical inference,
probabilistic inference, commonsense reasoning, search, and
inductive inference.  The communication part of AI comprises
vision and natural language understanding.  The application part of
AI includes tools and methodologies for building expert
systems and for integrating various AI techniques into useful systems.

The various techniques of AI can be thought of as ``elements,''
which when properly combined, afford useful ``compounds'' (expert systems).
Although this book provides many Lisp programs to illustrate how these
elements are applied, it is organized around the
presentation of the elements, and thus its title is explained.

\section{Bibliographical Information}

     Beginning with the volume of collected papers {\it Computers and
Thought}, edited by E.~Feigenbaum\index{-Feigenbaum, E.} and J.~Feldman\index{-Feldman, J.} in 1963, there has been
a  gradual growth of books that can be considered basic books  in
AI.  Although {\it Computers and Thought} is not a text,  it introduced the
subject  of  AI effectively,  using  two kinds  of  papers:  (1)  methodological
articles such as A.~Turing's\index{-Turing, A.} ``Computing Machinery and
Intelligence,'' and M.~Minsky's\index{-Minsky, M.}
``Steps  Toward  Artificial  Intelligence;''   and   (2)
descriptions of computer programs.   Some of the programs are
the ``Logic Theory Machine'' of A.~Newell,\index{-Newell, A.} J.~Shaw, and H.~Simon\index{-Simon, H.} and a
geometry theorem-proving program by H.~Gelernter.\index{-Gelernter, H.}

     The   first  textbook  was  {\it Artificial   Intelligence:   The
Heuristic  Programming Approach},  by J.~Slagle.\index{-Slagle, J.}   This book  surveys
some  of the programs for game playing and  problem solving  that
had been completed by the early 1960s.  The principle of minimax
analysis of a game tree is presented there in a clear way.

     A particularly influential text  by N.~J.~Nilsson\index{-Nilsson, N.} entitled {\it Problem Solving Methods  in
Artificial Intelligence} was published in 1971.   It presented two  key
topics in a straightforward and pleasing way.   The first topic is
that  of  searching  through a space  of  problem  configurations
called  ``states.''   The  second topic is the use of  the  predicate
calculus  in automatic reasoning.   This text is mathematical  in
style when compared with most of the other AI texts.

     The  books  by  Slagle and Nilsson each  treated  relatively
specific parts of AI as might be expected for the time.   A  book
that  covers cognitive models,  perception, and inductive  methods
such  as  clustering of patterns for subsequent  recognition,  in
addition to theorem proving, is {\it Artificial Intelligence}
by  E.~B.~Hunt,\index{-Hunt, E.} published in 1975.
This  book  covers a much  greater  variety  of
mathematical techniques than its predecessors.   Occasionally
the  treatment  is dense,  but the variety and  depth  of  topics
treated continue to make the book useful.

     An  introduction to AI suitable for readers who want a taste of
the issues and applications of AI  without  getting  deeply
involved in technique was written by P.~Jackson\index{-Jackson, P.}
and published in 1974.  A book
giving  a  similar  variety  of topics but  including  the  basic
techniques  of  AI was written by B.~Raphael.\index{-Raphael, B.}   It  appeared  in
paperback form in 1976,  and it was entitled {\it The  Thinking  Computer:
Mind Inside Matter}.

     A  course for college undergraduates at
MIT  was developed by P.~Winston,\index{-Winston, P.}  currently director of the  AI
laboratory  there.   This course concentrated on the systems  and
studies   done  at  the  MIT  laboratory, nonetheless spanning a
considerable  range of topics.   The course notes developed  into
the  text  {\it Artificial  Intelligence} (bearing the  same  title  as
Hunt's  book).   This  was  the  first AI text  to  include  Lisp
programming techniques as part of the core material.  Second and
third editions were published in 1984 and 1992; the latter
has excellent coverage of machine learning.

     In 1981, Nilsson\index{-Nilsson, N.} published a second AI text, entitled
{\it Principles of Artificial Intelligence}.  Like his earlier AI text,
this  one emphasizes search and the predicate calculus as the key
components  of  AI  systems.   The treatment of  both  topics  is
expanded  in  the  new  book.    In  addition,   the  programming
methodology called ``production systems'' is examined as a means of
implementing   the   search  and  deduction   methods   espoused.
Extensive   bibliographical  material  on   production   systems,
problem solving, plan generation, and theorem proving is given.

The text {\it Artificial Intelligence}\/ by
E.~Rich,\index{-Rich, E.}  published
in 1983, surveys AI in a style comparable to Raphael's {\it The
Thinking Machine}. 
With a coauthor K.~Knight, the book was expanded and updated in
1991.  It offers a very readable overview of many AI topics.
A graduate-level text, {\it Introduction to Artificial Intelligence}
by E.~Charniak\index{-Charniak, E.} and D.~McDermott,\index{-McDermott, D.} emphasizes the computational modeling of
human faculties.
An introduction using mathematical logic from the start is
{\it Logical Foundations of Artificial Intelligence}\/by
M.~Genesereth and N.~Nilsson.\index{-Genesereth, M.}

In recent years, a large number of introductory books on AI have
been published.  Notable among these are [Luger and Stubblefield 1993], and [Ginsburg 1993].

        The majority of writings on AI are research papers.
Some good general collections of these papers are listed below.
It should be kept in mind that each subarea of AI (such as machine
learning) has its own books and journals, references to which can
be found at the end of its particular chapter.

\begin{enumerate}
\item {\it IJCAI Proceedings}.  Every two years starting in 1969
there has been a meeting entitled
International Joint Conference on Artificial Intelligence. The proceedings
of these contain many papers covering all the major topics in AI.

\item {\it AAAI Proceedings}.  Starting in 1980, there has been a
conference each year (except years when the IJCAI is held in North America)
sponsored by the American Association for Artificial Intelligence.

\item {\it Journal of Artificial Intelligence}.  A limited number of
papers of high academic quality are published in this journal by
North-Holland Publishers.

\item {\it IEEE Transactions on Pattern Analysis and Machine Intelligence}.
The majority of the papers published here have focused on computer vision
and pattern recognition, and this publication has more of an engineering
orientation than the {\it Journal of Artificial Intelligence}.

\item {\it Cognitive Science}.  This journal publishes articles
that seek to explain how human thought works.  It is interdisciplinary,
representing research methodologies from psychology, computer science,
and neurophysiology.

\item {\it The AI Magazine}.  This periodical contains semiacademic
articles, book reviews, news items, and paid advertising.
These articles are often easier to read by the nonspecialist than
the research articles in regular journals and conferences.
Thus back issues of this publication are a good source of ideas
for students taking their first AI course.
It is published by the AAAI.

\item {\it SIGART Newsletter}.  News items and unrefereed articles can
be found several times a year in this publication by the Association
for Computing Machinery Special Interest
Group on Artificial Intelligence.

\end{enumerate}

The ADJUDIPRO system is presented in the fourth volume of
the book series
{\it Innovative applications of Artificial Intelligence}
edited by A.~Scott and P.~Klahr.
This series presents a wide variety of successful AI applications
in industry, finance, government, etc.
The example computer vision system discussed earlier is described in
[Grimson et al. 1993].
The third example AI program we discussed, the Internet Softbot, is
detailed in [Etzioni and Weld 1994].

The four-volume {\it Handbook of Artificial Intelligence}\/
contains lucid explanations of many AI concepts and systems.
The two-volume {\it Encyclopedia of Artificial Intelligence}\/
contains many thoughtful survey articles on subareas of the field.
Another good collection of survey articles is 
{\it Exploring Artificial Intelligence},
edited by H.~Shrobe.\index{-Shrobe, H.}

Some reflections on artificial intelligence from a broad perspective
are [Minsky 1987, 1991] and [West and Travis 1991].
For a fascinating historical account of the development of AI,
through especially the 1960s and 1970s but also the 1980s,
see [Crevier 1993].
A discussion of the limits to AI can be found in [Dodd 1991].
A thoughtful perspective on the Turing test is given in
[Epstein 1992].

\markright{REFERENCES}
\section*{References}
\markright{REFERENCES}
\addcontentsline{toc}{section}{References}
\begin{enumerate}

\item  Agarwal, R., Kannan, R., and Tanniru, M. 1993.
\index{-Agarwal, R.}\index{-Kannan, R.}\index{-Tanniru, M.}
Formal validation of a knowledge-based system using a
variation of the Turing test.
{\it Expert Systems with Applications}, Vol.~6, No.~2 (April-June), pp. 181-192.

\item Barr, A., Cohen, P.~R., and Feigenbaum, E.~A. (eds.) 1989.
{\it The Handbook of Artificial
Intelligence}, Volume 4.  Los Altos, CA: William Kaufman.
\index{-Cohen, P.}

\item Barr, A., and Feigenbaum, E.~A. (eds.) 1980, 1981.
\index{-Barr, A.}\index{-Feigenbaum, E.}
{\it The Handbook of Artificial
Intelligence}, Volumes 1 and 2.  Los Altos, CA: William Kaufman.

\item Charniak, E., and McDermott, D. 1985.
\index{-Charniak, E.}\index{-McDermott, D.}
{\it Introduction to Artificial Intelligence}.  Reading, MA: Addison-Wesley.

\item Chow, J., Litvin, D.~M., and Opiela, K.~S. (eds). 1993.
\index{-Chow, J.}\index{-Litvin, D.}\index{-Opila, K.}
{\it  Validating Expert System Prototypes Using the Turing Test}.
New York:  American Society for Civil Engineering.

\item Cohen, P.~R., and Feigenbaum, E.~A. (eds.) 1982.
\index{-Cohen, P.}\index{-Feigenbaum, E.}
{\it The Handbook of
Artificial Intelligence}, Volume 3. Los Altos, CA: William Kaufman.

\item Crevier, D. 1993.
\index{-Crevier, D.}
{\it AI: The Tumultuous History of
the Search for Artificial Intelligence}.
New York: Basic Books.

\item Dodd, T. 1991.
\index{-Dodd, T.}
Are there limits to AI?
{\it EXE}, Vol.~6, No.~2 (July), pp. 14-16, 18.

\item Epstein, R. 1992
\index{-Epstein, R.}
The quest for the thinking computer.
{\it AI Magazine}, Vol.~13, No.~2, pp. 81-95.

\item Etzioni, O., and Weld, D. 1994.
\index{-Etzioni, O.}\index{-Weld, D.}
A softbot-based interface to the Internet.
{\it Communications of the ACM},
Vol.~37, No.~7 (July), pp. 72-76.

\item Feigenbaum, E.~A., and Feldman, J. (eds.) 1963.
\index{-Feldman, J.}
{\it Computers and Thought}. New York: McGraw-Hill.

\item Genesereth, M.~R., and Nilsson, N.~J. 1987.
{\it Logical Foundations of Artificial Intelligence}.
San Mateo, CA: Morgan Kaufman.
\index{-Genesereth, M.}

\item Ginsberg, M.~L. 1993.
{\it Essentials of Artificial Intelligence}.
San Mateo, CA: Morgan Kaufmann.

\item Grimson, W.~E.~L., Lozano-Perez, T., Noble, N., and White, S.~J. 1993.
An automatic tube inspection system that finds cylinders
in range data.  {\it Proceedings of CVPR'93: the IEEE Computer Society 
Conference on Computer Vision and Pattern Recognition},
New York, pp. 446-452.
\index{-Grimson, W.}\index{-Lozano-Perez, T.}\index{-Noble, N.}\index{-White, S.}

\item Guha, R.~V., and Lenat, D.~B. 1990.
Cyc: A midterm report.  {\it AI Magazine}, Vol.~11, No.~3, pp. 32-59.
\index{-Lenat, D.}\index{-Guha, R.}

\item Hunt, E.~B. 1975.  {\it Artificial Intelligence}.
\index{-Hunt, E.}
Orlando, FL: Academic Press.

\item Jackson, P.~C.,~Jr. 1974.  {\it Introduction to Artificial Intelligence}.
New York: Petrocelli/Charter.

\item Luger, G.~F., and Stubblefield, W.~A. 1993.
{\it Artificial Intelligence: Structures and Strategies for
Complex Problem Solving}, 2d ed.
Redwood City, CA: Benjamin/Cummings.

\item McCorduck, P. 1979.  {\it Machines Who Think}.
\index{-McCorduck, P.}
New York: W.~H.~Freeman and Company.

\item Minsky, M. 1987.
{\it The Society of Mind}.
New York: Simon \& Schuster.

\item Minsky, M. 1991.
Logical versus analogical or symbolic versus connectionist
or neat versus scruffy.
{\it AI Magazine}, Vol.~12, No.~2, pp. 35-51.
\index{-Minsky, M.}

\item Nilsson, N.~J. 1971.
\index{-Nilsson, N.}
{\it Problem Solving Methods in Artificial Intelligence}.
New York: McGraw-Hill.

\item Nilsson, N.~J. 1981.
{\it Principles of Artificial Intelligence}. Palo Alto, CA:
Tioga Press; also Los Altos, CA: William Kaufman, 1983.

\item Raphael, B. 1976.  {\it The Thinking Computer: Mind Inside Matter}.
\index{-Raphael, B.}
New York: W.~H.~Freeman and Company.

\item Rich, E., and Knight, K. 1991.  {\it Artificial Intelligence}, 2d ed. New York: McGraw-Hill.
\index{-Knight, K.}

\item Scott, A.~C., and Klahr, P. (eds.) 1992.
{\it Innovative Applications of Artificial Intelligence 4}.
Menlo Park: AAAI Press (also distributed by MIT Press, Cambridge, MA).
\index{-Scott, A.}\index{-Klahr, P.}

\item Slagle, J. 1967.
\index{-Slagle, J.}
{\it Artificial Intelligence: The Heuristic Programming
Approach}. New York: McGraw-Hill.

\item Shapiro, S. (ed.) 1987. {\it The Encyclopedia of
Artificial Intelligence}. 
\index{-Shapiro, S.}
New York: Wiley.

\item Shrobe, H.~E. (ed.) 1988. {\it Exploring Artificial Intelligence:
Survey Talks from the National Conferences on Artificial Intelligence}.
Palo Alto, CA: Morgan Kaufman.
\index{-Shrobe, H.}

\item West, D.~M., and Travis, L.~E. 1991.
\index{-Travis, L.}\index{-West, D.}
From society to landscape: Alternative metaphors for artificial intelligence.
{\it AI Magazine}, Vol.~12, No.~2, pp. 69-83.

\item Winston, P.~H. 1977; 2d ed. 1984; 3d ed. 1992.
{\it Artificial Intelligence}.
\index{-Winston, P.}
Reading, MA: Addison-Wesley.

\end{enumerate}

\markright{EXERCISES}
\section*{Exercises}
\markright{EXERCISES}
\addcontentsline{toc}{section}{Exercises}

\begin{enumerate}
\item Write your own definition for intelligence.

\item List at least two reasons why people have been skeptical about the
possibility for machines to be intelligent.

\item What are some of the limitations of human intelligence?  What seem to
be some current limitations of machine intelligence?

\item Suppose that you could have an intelligent computer system running in
your home or in a portable unit.  Describe the capabilities you would
want it to have and some problems to which you would apply it.

\item Describe some of the jobs and challenges likely to be available to
people who are proficient in the techniques of artificial intelligence.

\item Where is your nearest source of literature on AI?

\item Find an article from a newspaper or magazine about artificial intelligence.
Is its emphasis technical, commercial, or political?

\item Imagine that you are going to use Turing's test to find out whether a
new software product you have just purchased has really achieved
artificial intelligence.  Assuming that this product runs on a
microcomputer and produces textual responses to textual inputs,
explain how you would set up the two humans, the computer hardware
and special software, and any other equipment to
make a fair test of the product.  What kinds of things could go wrong
with the test, and how could you prevent or tolerate them?

\item If you could connect through an electronic network to
whatever intelligent information services you desired, what sort
of problem solving or information would you want?  How feasible
do you think it would be to create an AI system to provide this
service?

\end{enumerate}

\openout15=lastpageno.txt
\write15{\arabic{page}}
\closeout15

\newpage
\tableofcontents
\thispagestyle{empty}
\newpage
\listoffigures
\thispagestyle{empty}

\end{document}


