XW 061 VQ 8842

SR
PROBLEM-SOLVING METHODS
IN
ARTIFICIAL INTELLIGENCE
Nils J. Nilsson
Artificial Intelligence Group
Stanford Research Institute
November 1969
(Preliminary Draft, ® 1969 Nils J. Nilsson)
Bibliographical and reference sections of Chapters I thru VIII,

and combined reference list (revised February 1970) .
(Chapter I)
D. Bibliographical and Historical Remarks
1. The "intelligence" of Computers
The question of whether or not machines can (or ever will be able
to) "think" still provokes lively debate even among those who concede that
man is a machine. Turing (1950) delightfully shatters many of the standard
arguments against intelligent machines. To decide whether or not a
machine is intelligent, he proposes what has come to be called the Turing
Test.
Selfridge and Kelly (1962) debate about the magnitude of the practical
problems in creating intelligent machines after agreeing that there are
no known theoretical barriers. Hubert Dreyfus (1965) thinks that digital
computers are inherently incapable of such "necessities" of intelligence as
"fringe consciousness" and "perspicuous grouping." His arguments are
systematically refuted by Papert (1968).
2. Overviews of Artificial Intelligence
Attempts to "organize" the field of Artificial Intelligence have
never been wholly successful. The subtopics of Search, Pattern Recognition,
Minsky (1961a)
Learning, Problem-Solving, and Induction have been suggested by
in an important survey article. This breakdown is still useful even though
its logical validity is challenged by the plethora of statements in the
literature that have the form: "The problem of Xis basically a problem
More recently Minsky

of V " where X and V could be any pair of subtopics.
(1968) has written another thoughtful article on the foundations of Artificial
Intelligence and concludes that a major problem is that of acquiring, maintain
ing and accessing a large knowledge base
116
3. Ap pr oa c hes to Artificial Intelligence
In attempting to build intelligent machines one naturally asks
"what is the secret of animal intelligence?" People have had a variety
of adventures pursuing this question but no one has yet found the secret.
Rosenblatt (1962) suggested brain models called perceptrons; these were
networks of "artificial neurons" based on the neuron models of McCulloch
and Pitts (1943) . The study of perceptrons stimulated early pattern-
recognition research and led to some elegant mathematical results on
computational geometry by Minsky and Papert (1969). The complex processes
of "intelligence," however, were beyond the power of these simple percept ron
models .
Another biologically-based strategy was the rather grandiose attempt
to simulate evolution itself. Since evolution produced intelligent man
in two billion years or so, let us simulate the processes of evolution
at high speed in the computer. Fogel et al (1966) describe experiments
involving the production of many generations of finite state machines
using the strategies of mutation and selective survival. Although this
technique may be capable of condensing the first few million years of
evolution to a few days of computer time, it seems that the important
middle and later stages of evolution involve structures already so complex
(though not yet "intelligent") that their evolution cannot be speeded up by
computer simulation. Thus the "artificial evolution" approach did not
succeed in producing adequately complex machines either.
Another way to learn about intelligence from animals is to study their
behavior, particularly the problem-solving behavior of man. Travis (1963,
1967) discusses the role of introspection in the design of problem-solvers.
117
Newell, Shaw and Simon (1959) describe a General Problem Solver' that is
supposed to attack problems in much the same way that humans do
A rich source of ideas about how humans attack problems is found in
Polya (1957). -m
—^ 1
Polya quotes the Greek mathematician Pappus who,
around 300 A.D., gave an excellent description of the Problem-reduction
approach ':
"in analysis, we start from what is required, we take it for granted,
and we draw consequences from it, and consequences from the consequences,
till we reach a point that we can use as a starting point in synthesis.
For in analysis we assume what is required to be done as already done
(what is sought as already found, what we have to prove as true). We
inquire from what antecedent the desired result could be derived; then
we inquire again what could be the antecedent of that antecedent, and so
on, until passing from antecedent to antecedent, we come eventually upon
something already known or admittedly true. This procedure we call analysis,
or solution backwards, or regressive reasoning.

*
In the problem-solving methods based on analysis of human behavior,
we find that trial and error search at some level plays a key role.
Campbell (1960) calls the unguided search process a blind-variation-and
selective-survival process. He concludes:
1. A blind-variation-and-selective-survival process is fundamental
to all inductive achievements, to all genuine increases in
knowledge, to all increases in fit of system to environment.
* From page 142 of Polya (1957)
118
2. The processes which shortcut the full blind-variation-and-
selective-survival process are in themselves inductive
achievements containing wisdom about the environment

achieved
originally by a blind-variation-and-selective survival process.
in their own
3. In addition, such substitute processes contain
operation a blind -variation-and-selective-survival

process at
some level.
primacy of search. The real

We agree with Campbell about the ultimate
problem-solver is to search at
trick in designing an efficient automatic
the highest level permitted by the available information about the
problem and about how it might be solved. Thus in this book we are
with how they can be made

primarily concerned with search techniques and
more efficient by using all available information.
4. Problem-Solving Methods
study problem-solving
There have been only a few attempts to
methods and to
processes abstractly in order to catalog the different
deduce general properties of these methods. In this book we identify three

probably not meet with universal
major approaches although our division would
approval among researchers in this field. A slightly different taxonomy of
(1969). The organization of

problem-solving methods is suggested by Newell
by a series of difficult but
the present book has been much influenced
worthwhile papers by Ajê^^^l^TJ;^ . A paper by Sandewall (1969)
ideas that we treat in this

formalizes some of the same problem-solving
highly formal treatment of
book. A book by Baner.ii (1969) contains a
problem solving and game playing.
119
Problem-solving programs demand a heavy diet of puzzles and games
on which to sharpen techniques. Some good general books of puzzles are
those of Martin Gardner (1959, 1961) who edits a puzzle column in The
Scientific American. Also see the books of puzzles by Dudeney (1958, 1967)
who was a famous British puzzle inventor. The 15 puzzle has a long history
and is discussed by Martin Gardner (1964, 1965a, b,c) , by Schofield (1967),
and by Ball (1931). The Tower of Hanoi problem is also discussed in Ball
(1931) and in Gardner (1959).
The state-space approach to problem-solving gets its name from the
use of "state-spaces" for similar purposes in control theory. It is also
used extensively in operations research. Some of the state -space search
methods that we shall be discussing later are identical to those called
branch and bound methods in operations research. Lawler and Wood (1966)
give a survey of branch and bound methods and their applications.
Our predilection to distinguish between state-space and problem-
reduction methods derives from the different search strategies used by
each method. The distinction is precisely the same as that made by
Amarel (1967) between "production type" and "reduction type" methods-
Slagle (1963a) also finds the problem-reduction formulation useful in
describing his program for symbolic integration. The General Problem
Solver (GPS) of Newell and his coworkers is thoroughly described in a
book by Ernst and Newell (1969). Although GPS can be described in terms
of state-space methods, it is our opinion that its operation can be under-
stood more clearly if it is described as a problem-reduction type problem-
solver .
120
The formal-logic based problem-solvers stem from tho Advice-Taker
memoranda of McCarthy (1958,1963). The Advice Taker was to be a system
that used formal methods to deduce the solutions to problems from a large-
set of axioms representing the problem-solver's knowledge base. It could
be given advice merely by adding new axioms. Some early work related to
this idea was undertaken by Black (1964) . We shall mention some of the
later work in this field in Chapter VII.
Some excellent ideas on solving large combinatorial problems have been
suggested by Shen Lin (1965,1968). Although these ideas don't appear to fit
neatly into any of our three categories of problem-solving methods, they
deserve the attention of any serious student in the field.
5. Applications of Problem-Solving Programs
It is fair to ask whether or not any oJ these methods that work
so well on puzzles and games has been usefully employed on real problems.
State-space methods have been employed in the solution of operations research

well-known
problems such as the /traveling salesman problem. The "best' exact solution
technique so far is a state-space method proposed in a Ph.D. dissertation
by Shapiro (1966) and discussed by Bellmore and Nemhauser (1968). Although
the traveling salesman problem may appear as frivolous as do puzzles and games
it is a model for problems of economic importance in scheduling and production
design .
Other applications of the state-space method have been made in the con-
trol of remote manipulators by Whitney (1969) and in sequential decoding by
Jelinek (1969) . Problem-reduction methods have been employed in a system
that performs symbolic integration (Slagle, 1963a) and in a system that
analyzes mass spectrograph data (Buchanan, Sutherland, and Feigenbaum, 1969) .

121
6. I mportant Source Materials for Artificial In tell i g ence
Artificial Intelligence is a much-surveyed field, and there are plenty
of bibliographies around. An early annotated one is that of Minsky (1961b) . Later
surveys by Feigenbaum (1963) and Solomonoff (1966) include many additional refer-
ences. A recent survey by Feigenbaum (1968) lists more articles and also
speculates about the future of the field.
A vol umni, that is often referenced because it contains many of the early
papers is entitled Computers and Thought, edited by Feigenbaum and Feldman.
D. Michie and others have edited a series of books called Machine Intelligence
These contain papers delivered at the Machine Intelligence Workshops held annually
in Edinburgh. Another important, book is called Semantic Information Processing
edited by Minsky; it contains complete versions of several Ph.D dissertations
dealing with language processing and "understanding,"
Artificial Intelligence is a journal devoted exclusively to A.I; it began
publishing in 1970. Also, the Journal of the Association for Computing Machinery
occassionally publishes articles on artificial intelligence subjects.
In the United States, Artificial Intelligence activities are coordinated
through a Special Interest Group on Artificial Intelligence (SIGART) of the
Association for Computing Machinery (ACM). SIGART publishes' a newsletter that
occassionally contains reference material not published elsewhere.
The Artificial Intelligence and Simulation of Behavior (AISB) group of the
British Computer Society publishes a European newsletter.
For completeness, we shall occassionally reference unpublished memoranda
and reports in this book. The authors of such material will sometimes provide
copies upon request.
122
E. References
Amarel, S. (1965)
Solving Procedures for Efficient Syntactic Analysis"

ACM
"Problem
(Also printed as Scientific Report
20th National Conference, 1965
No. 1, AFOSR Contract No. AF49(638)-1184,
1968).
Amarel, S. (1967)
in the
"An Approach to Heuristic Problem-Solving and Theorem Proving
Science, J. Hart and S.
Propositional Calculus," Systems and Computer
Takasu (Eds.), Univ. of Toronto Press, 1967.
Amarel, S. (1969)
"On the Representation of Problems and Goal Directed Procedures for

Computers," Communications of the American Society for Cybernetics,
Vol. 1, No. 2, 1969.
Ball, W. (1931)
Mathematical Recreations and Essays, Tenth Edition, 1931, Mac Millan &Co
London, (15 puzzle, pp. 224-228; Tower of Hanoi, pp. 228-229.)
Banerji, R. (1969)
Theory of Problem Solving: An Approach to Artificial Intelligence,
American Elsevier Publishing Co. Inc., New York, 1969.
Bellmore, M. and G. Nemhauser (1968)

Problem: A Survey," Operations Research
"The Traveling Salesman
Vol. 16, No. 3, May-June 1968, pp. 538-558.
Black, F. (1964)
"a Deductive Question-Answering System, "Ph.D. Dissertation,
Harvard,
Processing, M. Minsky (Ed)
June 1964. Reprinted in Semantic Information
MIT Press, Cambridge, Mass., 1968, pp. 354-402.
Buchanan, 8. , G. Sutherland, and E. Feigenbaum (1969)

Generating Explanatory Hypotheses
"Heuristic Dendral: A Program for
Intelligence 4, B. Meltzer and D.
in Organic Chemistry." in Machine
Publishing Co. , Inc., New York,
Michie (Eds.), American Elsevier
1969, pp. 209-254.
Campbell, D. (1960)
Survival as a General Strategy in
"Blind Variation and Selective Systems, M. Yovits&S. Cameron
Knowledge-Processes," In Self-Organizing
(Eds j, Pergamon Press, New York 1960, pp. 205-231.
123
Collins, No and D. Michie (Eds.)
Machine Intelligence 1, American Elsevier Publishing Co., Inc.,

New York, 1967.
Dale, E. and D. Michie (Eds.)

Co., Inc.,
«.Phi BB intelligence 2, American Elsevier Publishing
New York, 1968.
Dreyfus, H. (1965)
Corporation Paper
(AD
!^^^
625 719), December, 1965.
Dudeney, H. (1958)
York, 1958.
Dover Publications, Inc., New
The Canterbury Puzzles,
(Originally published in 1907.)
Dudeney,
Modern
H. (1967)
536 Puzzles and Curious Problems,
£L New York.
Puzzles
Martin Gardner (Ed. ), Charles
on from two of Dudeney' books.
196/71X1^110^1 Problems. 1931).
1926. and Puzzles and Curious
.
Sen bnc r s
Ernst, G. and A. Newell (1969)

Solving ACM Monograph
r.PS: A Case Study in Generalityjmd_Problem
Series, Academic Press, 1969.
Feigenbaum, E. (1963)
Intelligence Research," lEEE Trans, on Info. Theory,
"Artificial
Vol. IT-9, No. 4, Oct., 1963, pp. 248-261
Inteligence: Themes in the Second
Decade," g2^£-
"Artificial Also printed as Stanford
IMPS 68 Congress. Edinburgh, Aug. 1968. Aug. 10, 1968.
Tj n Intelligence Project Memo No. 67,
7ver77t7~ATtTFicial
124
Feigenbaum, E. and Feldman, J. (1963)
Computers and Thought, McGraw-Hill Book Company, Inc., New York, 1963
Fogel, L. , A. Owens and M. Walsh (1966)

Artificial Intelligence Through Simulated Evolution, John Wiley, New York,
1966.
Gardner, M. (1959)
The Scientific American Book of Mathematical Puzzlos and Divers tons,
Simon and Schuster, New York, 1959 .
Gardner,
The
M.
X lit?
(1961)
Second Scientific American Book "of Mathematical
OOJJUIIU OtJLCII L. XX X\^
Simon and Schuster, New Y0rk, 1961

r*HK- iJ.
~ voh
Puzzles and Diversions
"^"^" -«- ""-»
~»«^-""~
— _
Gardner, M. (1964, 1965 a,b,c)
Mathematical Scientific American, Vol. 210, No. 2, Feb., 1964,

Games,
pp 122-13p; Vol .
212, No. 3, March,l96s, pp. 112-117;
1965,
Vol. 212, No. 6,
pp. 222-236.
June, l96s, pp. 120-124; Vol. 213, No. 3, Sept.,
Jelinek, F. (1969)
"Fast Sequential Decoding Algorithm Using a Stack," IBM J. of Res, and Dcv )
Vol. 13, No. 6, Nov, 1969, pp. 675-685.
Lawler, E. and D. Wood (1966)

Operations Research, Vol. 14, No. 4,
"Branch and Bound Methods: a Survey,"
pp. 699-719, July-August ,1966.
Lin , Shen (1965)

"Computer Solutions of the Traveling Salesman Problem," The Bell System
Technical Journal, Vol. XLIV, No. 10, Dec, 1965.
Lin, Shen (1968).

on a
"Heuristic Techniques for Solving Large Combinatorial Problems
Problem-Solving by Computer,
Computer," Formal Systems and Non-Numerical
Cleveland, Ohio, Nov., 1968.
Case Western Reserve Ufniversity,
125
McCarthy, J. (1958)
Programs with Common Sense," in Mechanization of Thought Processes, Vol . I
pp. 77-84,. Proc Symposium, National Physical Laboratory,
London. Nov
24-27, 1958. Reprinted in Semantic Information Processing,
M. Minsky (Ed.)
MIT Press, Cambridge, Mass., 1968, pp.
403-4107 "
McCarthy, J. (1963)
"Situations, Actions and Causal Laws," Stanford University Artificial
Intelligence Project Memo. No. 2, 1963. Reprinted in Semantic Infor-
,
mation Processing, M. Minsky, (Ed.) MIT Press, Cambridge, Ma55 .,1968,
pp. 410-418.
McCulloch, W. S. and W. Pitts (1943)

"A Logical Calculus of the Ideas Immanent in
Mathematical Biophysics, Vol. 5, pp. 115-137, 1943. Nets." Bulletin
Neural o1
~~"
Meltzer, B. and D. Michie (Eds.)

New York, 1969.
Michie, D. (Ed.)

New York, 1968.
Michie, D. (Ed.)
Machine Intelligence^, American

Elsevier Publishing to.,
Co Tne
Inc.,
New York, 1970.
126
Minsky, M. (1961a)
"Steps Toward Artificial Intelligence, " Proc.

of ire. Jnn ., 19(U , Vol 49
pp. 8-30.Reprinted in Computers and Thought , Feigenbaum
(Eds.), McGraw-Hill BookToT; New F nnd r r ,'h
York, 196^, pp. 406-450 "
Minsky, M. (1961b)
"A Selected Descriptor -Indexed Bibliography to the Literature on

Artificial Intelligence," IRE Trans, on Human Factors in Electronics,
March), 1961 ,
HFE-2, pp. 39-55. A Revision is reprinted in Computers
and Thought, Feigenbaum, E. and J. Feldman (Eds.), McGraw-Hill Book Co.
New York, 1963, pp. 453-523.
Minsky,M. (Ed.) (1968)

Semantic Information Processing, The MIT Press,
Cambridge, Mass., 1968.
Minsky, M. and S. Papert (1969)

Perceptrons: An Introduction to Computational Geometry, The MIT Press,
Cambridge, Mass. 1969.
Newell, A. (1969)
"Heuristic Programming: 111-Structured Problems," Progress in Operations
Research, J. Aronofsky (Ed.), Vol. 3, Wiley, 1969.
NewelliA.,J. Shaw and H. Simon (1959)

"Report on a General Problem-Solving Program," Proc of
Int'l Con*,
Paris, pp. 256-264, 1969.
on Information Processing, UNESCO House,
Papert, S. (1968).
"The Artificial Intelligence of Hubert L. Dreyfus. A Budget of
Fallacies,"
Massachusetts Institute of Technology Artificial Intelligence Memo #54,
Jan. , 1968.
Polya, G. (1957)
How to Solve It (Second Edition) , Doubleday & Co., Inc. Garden City
N. Y. ,1957.
Rosenblatt, F. (1962)
Principles of Neurodynamics, Spartan Books, New York 1962.
127
Sandewall E. (1969)
"Concepts and Methods for Heuristic Search," Proc of the International

Joint Conference on Artificial Intelligence.
Schofield, P. (1967)
"Complete Solution of the "Eight-Puzzle" in Machine Intelligence 1,
N. Collins and D. Michie (Eds), American Elsevier Publishing Co., Inc.,
New York, 1967, pp. 125—133.
Selfridge,0. and J. Kelly, Jr. (1962)

"Sophistication in Computers: a Disagreement," IRE Trans, on Info.
Theory, Feb. 1962.
Shapiro, D. (1966)
"Algorithms for the Solution of the Optimal Cost Traveling Salesman

Problem," Sc.D. Thesis. Washington Univ., .it. Louis, M0. ,1966.
Slagle, J. (1963a)
"A Heuristic Program that Solves Symbolic Integration Problems in
Freshman Calculus, "
JACM, Vol. 10, No. 4, Oct. 1963, pp. 507-520
Also in Computers and Thought, Feigenbaum, E. and J. Feldman (Eds.) ,
McGraw-Hill Book Co., New York, 1963, pp. 191-203.
Solomonoff, R. (1966).
"Some Recent Work in Artificial Intelligence ," Proc . lEEE , Vol. 54,
No. 112, Dec. , 1966.
Travis, L. (1963)
"The Value of Introspection to the Designer of Mechanical Problem-

Solvers," ,
Behav. Science Vol. 8, No. 3, pp. 227-233, July 1963.
128
Travis, L. (1967)
"Psychology and Bionics: Many old Problems and a Few New Machines, '
Conference Record 1967 Winter Convention on Aerospace and Electronic
Systems (WINCON) , Vol, VI, Feb. 1967, lEEE Publication No. 10-C-42.
Turing A. M. (1950)
Machinery and Intelligence," Mind , Oct. 1950, Vol. 59, pp
433-460. Reprinted in Computers and Thought, E. Feigenbaum and J.
Feldman (Eds.) McGraw-Hill Book Co. , New York, 1963, pp. 11-35.
Whitney, D. (1969)
"State Space Models of Remote Manipulation Tasks," in Proc of the

Int'l Joint Conf. on Artificial Intelligence, pp. 495-507.
129
((Chapter II)
I. Elements of a State-Space Representation
The three elements of a state-space representation — state-
descriptions, operators, and goal test

— have long been recognized as
basic in automatic problem-solving. These notions are discussed in the
book on the General Problem Solving (GPS) program by Ernst and Newell
(1969). A more abstract treatment of the problem of description of
states and operators may be found in Amarel (1967,1969). An example of the use
of rewriting rules to represent operators can be found in the problem-solving
system of Quinlan and Hunt (1968) . This system uses tree structures for state
descriptions.
2. Graph Theory
The basic vocabulary of graph theory (arcs, nodes, paths, and so
on) is often used to describe problem-solving processes. It does not appear
that much more than this vocabulary is of use in automatic problem solving.
Perhaps this is because most of the theorems of graph theory refer to explicit
graphs while in problem solving we usually use the notion of an implicit graph .
Classic books on graph theory are those of Berge (1962) and Ore (1962) . Ore
(1963) has also written a popular, elementary book illustrating applications
of graph theory to various combinatorial problems.
3. Non-deterministic Programs
The phrase "non-deterministic algorithm" was proposed by Floyd
(1967a). In these algorithms, Floyd allowed the use of a "choice" function
to simplify the description of exhaustive search strategies. Later Manna

(1970) described a class of programs that allowed non-deterministic
assignment statements (similar to the choice function) as well as non-
deterministic branching operations. He described techniques for proving
1133
the "correctness" of programs containing these new elements. (In an
earlier paper, Manna (1969) considered the problem of proving the
correctness of ordinary, non-deterministic programs.) Fikes (1970)
describes a complete problem-solving system in which problems are
stated in a procedural language that allows the use of non-deterministic
choice functions.
4 . Background Literature on the Example Problems
The example problems that we have used to illustrate state-
space techniques come from diverse fields each with its own individual
tradition of specialized problem-solving methods. Many of these methods
can be viewed as an application of the state-space approach. It would be
instructive for the reader to carry out the exercise of translating some
of the descriptions of these specialized methods into the common language
of the state-space approach.
The traveling salesman problem has occupied an important place in
Operations Research. For a review see Bellmore and Nemhauser (1968).
Problems of syntax analysis are common in language processing.
Feldman and Gries (1968) give a thorough survey of syntax analysis
techniques as used by translating systems for the formal languages of
computation. Amarel (1965) discusses syntax analysis from the point of
view of automatic problem-solving and proposes a problem-reduction
procedure. For a highly readable treatment of the use of symbol strings
and production systems as models of computation see the final chapters in
a book on computation by Minsky (1967).
1134
Many problems involving distribution, flow and queuing can be
solved
by similar techniques. A discussion of these can be found in a book by
Ford and Fulkerson (1962).
Control theory is a large and specialized field with a variety of
problem solution methods. A book by De Russo. Roy and Close (1965) is a good
introduction to modern control theory.
5. The Problem of Finding a Good Representation
The problem of finding good representations for problems has been
treated by only a few researchers notably by Amarel. Amarel (1968) is a
classic paper on the subject; it takes the reader through a series of pro-
gressively better representations for the "missionaries and cannibals"

problem.
The use of variables in state descriptions has been mentioned

as a
powerful representational technique. Later versions of GPS allowed the
use of "object schemas" with variables as did Fikes' (1970) problem-
solving system. A Paper by Newell (1965) examines some possible approaches
(and their limitations) toward making progress on "the representation
problem. "
1135
E. References
Amarel, S. (1965)
"Problem Procedures for Efficient Syntactic Analysis" ACM

Solving
20th National Conference, 1965 (Also printed as Scientific Report
No. 1, AFOSR Contract No. AF49(638)-1184, 1968).
Amarel, S. (1967)
"An Approach to Heuristic Problem-Solving and Theorem Proving in the

Propositional Calculus," Systems and Computer Science, J. Hart and S.
Amarel, S. (1968)
"On Representations of Problems of Reasoning About Actions,"

in Machine Intelligence 3, D. Michie (Ed), American Elsevier, New
York, 1968, pp. 131-171.
Amarel, S. (1969)

Vol. 1, No. 2, 1969.
"The Problem: A Survey,"

Traveling Salesman
ptêjônsê^rch
pp. 538-558.
Vol. 16, No. 3, May-June 1968,
Berge, C. (1962)
(Translated by Alison Doig)
The Theory of Graphs and its Applications,
1
(First published in France

John Wiley & Sons, Inc. New York, 1962.
in 1958 by Dunod, Paris).
P. , R. Roy and C. Close (1965)

De Russo,
1965
State Variables for Engineers, Wiley, New York,

ACM Monograph
GPS: A Case Study in Generality and Problem Solving
1136
Feldman, J. and D. Gries (1968)
"Translator Writing Systems" Comm. of ACM, Vol. 11, No. 2, Feb., 1968,
pp. 77-113.
Fikes, R. (1970)
"Ref-Arf: A System for Solving Problems Stated as Procedures,'

Artificial Intelligence, Vol.l, No. l , 1970.
Floyd, R. (1967a)
"Nondeterministic Algorithms," J. of ACM, Vol. 14, No. 4, 0ct. ,1967,
pp. 636-644.
Ford, L. Jr., and D. Fulkerson (1962)

Flows in Networks, Princeton University Press, Princeton, New Jersey, 1962
Manna, Z. (1969)
J. of Computer and Sytem Sciences, Vol
3
"The Correctness of Programs,"
May ,1969.
Manna, Z. (1970)
Programs," Artificial Intelligence
"The Correctness of Non-Deterministic
Vol. 1, No. 1, 1970.
Minsky, M. (1967)
Computation: Finite and Infinite Machines, Prentice Hall, Inc.,
Englewood Cliffs, N.J. , 1967.
Newell A. (1965)
"Limitations of the Current Stock of. Ideas about Problem Solving," in
Electronic Information Handling, A. Kent and 0. Taulbee (Eds. ), Spartan
Books, Wash. D.C., 1965.
Ore, 0. (1962)
Theory of Graphs, American Mathematical Society Colloquium Publication
Vol. XXXVIII, Providence, Rhode Island, 1962.
1137
Ore, 0. (1963)
Graphs and Their Uses, Random House, 1963.
Quinlan, J. and E. Hunt. (1968)

"A Formal Deductive Problem-Solving System," J. of ACM, Vol. 15.
No. 4, 0ct., 1968, pp. 625-646.
11-38
(Chapter III)
1. Shortest Path Algorithms
Efficient methods for finding the shortest (or least costly)
path between two nodes in a graph are of great interest in a variety of
disciplines. The procedure that we have called the Uniform Cost Method
was first described by Dijkstra (1959). A similar breadth-first search
technique was also proposed by Moore (1959). Also, the dynamic
programming algorithms of Bellman are essentially breadth-first search
methods. For a thorough discussion of dynamic programming see the book
by Bellman and Dreyfus (1962). A depth-first search procedure, often
called "backtrack programming" in computer science, is described by Golomb
and Baumert (1965). Stuart Dreyfus (1969) presents a detailed survey of
some of these and other graph searching methods.
2. Heuristic Search Techniques
The use of heuristic information to increase search efficiency
has been studied both in Artificial Intelligence and in Operations Research
Probably the most well-known use of heuristic evaluation functions has been
in game-playing programs, notably the checker-playing program of Samuel
(1959, 1967). The use of evaluation functions to direct the search of
state-space graphs has been proposed by Doran and Michie (1966) and further
discussed by Doran (1968). Our examples using the 8-Puzzle are based on
those of Doran and Michie. A general theory of the use of evaluation
functions to guide search was presented in a paper by Hart, Nilsson, and

Raphael (1968); our description of the Ordered Search Algorithm and its
properties is taken from that paper.
111-49
In the branch and bound methods of Operations Research we also see
the use of evaluation functions to guide search. For a description of
these see the survey article by Lawler and Wood (1966). The branch and
bound technique proposed by Shapiro (1966) for the traveling salesman
problem can also be interpreted as a direct application of algorithm A *

Our analysis supporting the importance of including g (as well as fi)
is taken from a dissertation by Pohl (1969). (See also Pohl, 1970. )
Pohl (1969) considers also the problem of searching outward from both start
and goal nodes. Particularly interesting here is his thorough discussion
of the more complex termination criterion needed for "bidirectional search.'

Our proposal that the search process might be occasionally punctuated
by tree pruning operations (to reclaim needed storage space) was also
suggested by Levy (1969).
3. Measures of Performance
Doran and Michie (1966) proposed the penetrance ' measure for
judging the efficiency of a given search. Slagle and Dixon (1969) propose
another measure which they call the depth ratio. Our effective branching
factor" was motivated by these earlier measures.
111-50
K. References
Bellman, R. and S. Dreyfus (1962)

Applied Dynamic Programming, Princeton University Press, 1962.
Dijkstra, E. (1959)
"A Note on Two Problems in Connection with Graphs," Numerische

Mathematik, 1, 1959, pp. 269-271
Doran, J. (1968)
"New Developments of the Graph Traverser," in Machine Intelligence 2

E. Dale and D. Michie (Eds), American Elsevier Publishing Co., Inc.,
New York, 1968, pp. 119-135.
Doran, J. and D. Michie (1966)

"Experiments with the Graph Traverser Program," Proceedings of the
Royal Socitey, A, Vol. 294, pp. 235-259, 1966.
Dreyfus, S. (1969)
TI
An Appraisal of Some Shortest Path Algorithms," Operations Research,
Vol. 17, No. 3, pp. 395-412, May-June 1969.
Golomb, L. and L. Baumert (1965)

"Backtrack Programming," J. of ACM, Vol. 12, No. 4., 0ct., 1965, pp. 516
*
524.
Hart, P., N. Nilsson and B. Raphael (1968)
"A Formal Basis for the Heuristic Determination of Minimum Cost

Paths," lEEE Trans, on Systems Sciences and Cybernetics, Vol. SSC-4
No. 2, July, 1968, pp. 100-107.

"Branch and Bound Methods: a Survey," Operations Research, Vol. 14 No. 4
pp. 699-719, July-August ,l966.
111-51
Levy, D. (1969)
"A Comment on Some Tree Searching Methods Which is Designed to Optimize

15, April 1969, pp.
the Use of Storage," ACM SIGART Newsletter, No.
14-16.
Moore, E. (1959)
"The Shortest Path Through a Maze," Proc. Int'l Symposium on the Theory ol
Switching, Part 11, April 2-5, 1957, The Annals of the Computation
Laboratory of Harvard University 30, Harvard University Press ,1959.
Pohl, I. (1969)
"Bi-Directional and Heuristic Search in Path Problems," Stanford

University Computer Science Dept. Ph.D. Dissertation, 1969. Also
printed as Stanford Linear Accelerator Center Report No. 104, May
1969.
Pohl, I. (1970)
"First Results on the Effect of Error in Heuristic Search, " in

Machine Intelligence 5.
Samuel, A. (1959)
"Some Studies in Machine Learning Using the Game of Checkers," IBM

Journal, Vol. 3, pp. 211-229, 1959. Reprinted in Computers und Thought,
Feigenbaum, E. and J. Feldman (Eds.), McGraw-Hill Book Co., New York, 1963
pp. 71 -
105.
Samuel , A. (1967)
"Some Studies in Machine Learning Using the Game of Checkers 11. Recent
Progress," IBM Journal of Research and Development, Vol. 11, No. 6
Nov. 1967, pp7 601-6177"
Shapiro, D. (1966)
Problem," Sc.D. Thesis, Washington Univ., ot. Louis, M0. ,1966.
Slagle, J and J. Dixon (1969)

"Experiments with Some Programs that Search Game Trees," J. of ACM
Vol. 16, No. 2, April 1969 , pp. 189-207.
111-52
(Chapter IV)
E. Bibliographical and Historical Remarks
1. Problem-Reduction Methods and AND/OR Graphs
Some of the very earliest work in Artificial Intelligence used
the problem-reduction techniquef (also called "reasoning backwards") to
solve problems . Newell, Shaw, and Simon (1957) programmed a Logic Theory
Machine (LT) that proved theorems in the propositional calculus by working
backwards from the theorem to be proved. In the LT program, use was made
of a tree of subproblems to keep track of alternative chains of reasoning.
Another early program in which problem-reduction methods and subprob-
lem trees were used was the Symbolic Integration (SAINT) program of Slagle (1963a).
Slagle first called these trees AND/OR trees; in a later paper Slagle and Byrsky
(1968) used the term Proposition Tree. Amarel (1967) also used special graph
structures in discussing problem- reduction methods. Manna (1970) gives several
examples of representing an implicit

AND/OR tree by nondeterministic programs.
2. Example Programs Using the Problem-Reduction Approach
Our example symbolic integration system is based on the SAINT program
of Slagle (1963a). This program is described in detail in Slagle's Ph.D disser-
tation (Slagle 1961). A much more elaborate integration system (called SIN) was
later programmed by Moses (1967). Moses' system embodied so many special criteria
for applying the various operators that most integrations are carried out with
little or no search.
* One might speculate that most of the search effort that might have been needed
to perform integrations was carried out once and for all by Moses himself in
designing the program. The results of this design search were the special rules
about.w hich operators to apply in all cases.
1143
The geometry theorem-proving examples were based on the program by
Gele rnter et al (1959, 1960). This program was never really completed;
nevertheless several of its features and proposed features represented important
and original innovations.
The notion of key operators and differences and their use in problem-
solving is due largely to Newell and his co-workers on GPS. (See Ernst and Newell ,
1969) . The reader should be cautioned that our explanation of these ideas
differs somewhat from that of Newell, et al. Newell has used the phrase "means-
ends analysis" to refer to the process of extracting differences and matching
t hese differences with relevant operators. He also distinguishes among three
kinds of goals in the GPS system: the transform object goal, the reduce difference
goal, and the apply operator goal. Our description does not acknowledge the
utility of these distinctions. Our interest in GPS is solely in its ability
as an automatic problem-solving system whereas many of the GPS workers were also
interested in it as a psychological model of human thought processes. This
difference in purpose undoubtedly contributed to part of the difference in its
description.
Stressing the problem-solving abilities of GPS, Ernst (1969) inquired about
conditions under which GPS is guaranteed to find a solution. Ernst's study
resulted in formalizing the notions of differences and ordering of differences.
3. Games and the Problem-Reduction Approach
Slagle and his co-workers have stressed the essential similarities
between AND/OR trees and game trees (single 1970, Slagle and Bursky. 1968).
This similarity is particularly apparent in simple games that can be searched to
termination or in the "end-games" of more complex games such as chess. Indeed,
one often thinks of chess-end game puzzles as problems of proof rather than as
games. Our Grundy's game example/taken from an article by o' Beirne (1961) .
1144
E. References
Amarel, S. (1967)

Ernst, G. (1969)
"Sufficient Conditions for the Success of GPS," Journal of ACM, Vol.
No .4, o>l 1959, pp. o.'i 530
GPS: A Case Study in Generality and Problem Solving ACM Monograph

Gelernter, H. (1959)
"Realization of a Geometry Theorem-Proving Machine," Proc of an Int 'l . .
Conf. on Info. Proc, UNESCO House, Paris, 1959, pp. 273-282. Reprinted
,
in Computers and Thought Feigenbaum, E. and J. Feldman (Eds.),
Gelernter, H. J. Hansen, and D. Loveland (1960)

"Empirical Explorations of the Geometry Theorem Proving Machine," Proc
17, pp. 143-147. Reprinted
of the Western Joint Computer C0nf. ,1960, Vol.
in Computers and Thought , Feigenbaum, E. and J. Feldman (Eds.), McGraw-Hill
Book Co., New York, 1963, pp. 153-167.
Manna, Z. (1970)
"The Correctness of Non-Deterministic Programs, " Artificial Intelligence,
Vol. 1, No. I , 1970.
Moses, J. (1967)
Symbolic Integration, Massachusetts Institute of Technology, Project MAC,
Report MAC-TR-47 (Thesis), Dec. 1967.
Newell, A., J. Shaw, and it. Simon (i;>;>7)
ol Lhe Logic Theory Machine,"

"Empirical Explorations Proc of tho .
Western Joint Computer Conference, 1957, pp. 218-239. Reprinted in
Computers and Thought, Feigenbaum, E. and J. Feldman (Eds.), McGraw-Hill
O'Beirne, T. H. (1961)
Puzzles and Paradoxes, New Scientist, No. 245, July 27, 1961, and No. 246,
August 3, 1961.
IV-44
Slagle, J. (1961)
for
"A Computer Program/ Solving Problems in Freshman Calculus (SAINT),
Doctoral Dissertation, Mass. Inst, of Tech. Cambridge, Mass, 1961.
Also printed as Lincoln Laboratory Report SG-0001, May 10, 1961.
Slagle, J. (1963a)
Freshman Calculus," JACM, Vol. 10, No. 4, Oct. 1963, pp. 507-520.
Also in Computers and Thought, Feigenbaum, E. and J. Feldman (Eds.)
Slagle, J. (1970)
"Heuristic Search Programs," cfan Formal Systems and Non-Numerical

Problem Solving by Computer, M. Mesarovic and R. Banerji (Eds.)
Slagle, J. and P. Bursky, (1968)

"Experiments with a Multipurpose, Theorem- Proving Heuristic Program
J. of ACM, Vol. 15, No., 1, pp. 85-99, Jan 1968.
IV-45
(Chapter V)
E. Bibliographical and Historical Remarks
1. Development of AND/OR Graph Searching Techniques
The search strategies of many of thet. early programs that generated
subproblem trees employed only rather simple ordering methods. Early versions
of GPS used a depth-first strategy and a means for measuring problem difficulty;
backtracking occurred when a successor problem was judged more difficult than any
of its ancestors. Slagle' s SAINT program used depth of function nesting as a
measure of problem difficulty and generally worked on the easiest problems
first.
Slagle and his co-workers experimented with many search strategies for game
trees and AND/OR trees during the 19605. The game-tree strategies were sum-
marized in a paper by Slagle and Dixon (1969). The most complex of these
involved a "dynamic ordering" of node expansions. In their problem-solving
system called MULTIPLE (MULTlpurpose Program that LEarns) , Slagle and Bursky
(1968) incorporated a general strategy for searching AND/OR trees. This strategy
uses the notion of the "probability that a proposition is true" and then defines
a merit function" over the open nodes of the tree. That node having greatest
effect on the probability that the original proposition is true is said to have
the largest "merit"; this node is the one selected for expansion.
Amarel (1967) proposed an "attention control" strategy for ordering node
expansions in an AND/OR tree. This strategy attempted to find a "minimal cost
solution. The present author (Nilsson, 1968) also suggested a cost-minimizing
strategy and later realized that it was essentially identical to Amarel 's.
In Nilsson (1968) a proof is given that the strategy does indeed find minimal
cost solutions; this proof is based on a similar one for state-space graphs by
Hart, Nilsson and Raphael (1968). The Amarel Nilsson strategy
differs little from the dynamic ordering method of Slagle and Dixon. The exposition
of the ordered search algorithm in this Chapter is merely an attempt to describe
this basic strategy in a clear and general manner.
1147
2. Development of Game Tree Searching Techniques
Claude Shannon (1950) discussed some of the problems inherent in
programming a machine to play a complex game such as chess. He suggested a
minimax search procedure to be used in conjunction with a static evaluation
function. Newell, Shaw and Simon (1958) used several of these ideas in construc-
ting an early chess-playing program; they also give an excellent discussion of
this area of research. Additional discussion on chess-playing programs together
with a "Five Year Plan" for automatic chess can be found in an article by Good
(1968) that also lists several references.
Later Samuel (1959) discribed a checker-playing program that incorporated
polynomial evaluation functions, minimax search methods and various '''learning"
strategies for improving play . Samuels' program plays an excellent checker game
and beats all but the very best players. It continues to be one of the out-
standing examples of the application of artificial intelligence techniques.
Later work on this program is described in Samuel (1967). One of the features
of more recent versions of Samuel's program is a dynamic ordering search pro-
cedure somewhat similar to that of Slagle and Dixon (1969).
The a - 0 procedure is usually thought to be a rather obvious elaboration
of the minimaxing technique and was thus "discovered" independently by many

workers. It is first described by Newell, Shaw and Simon (1958) and was the
subject of much investigation by McCarthy and his students (Edwards and Hart,
1963) at M. I.T. Few clear expositions of the method and its properties exist
* Samuel later stated ( personal communication) that his program also used the
0/ - 3 procedure but that at the time he thought its use too straightforward to
merit discussion in the paper.
1148
Samuel's second checkers paper (Samuel, 1967) contains a good description as does
Hie paper by Slagle and Dixon (1969) . The results on the search efficiency of
the Ot - |3 procedures were first stated by Edwards and Hart (1963) based on a
theorem that they attribute to Michael Levin. Later Slagle and Dixon (1969)
give what they consider to be the first published proof of this theorem. Slagle
and Dixon discuss several variations of the a -(3 procedure culminating with one
employing dynamic ordering. The performance of these various strategies is
compared using the ancient game of Kalah.
Our discussion about improvements on minimax-based methods is taken from
some proposals by Slagle (1963hQ and Slagle and Dixon (1970). The latter
paper describes experiments with an "M & N Tree Searching Program" that adds (or
subtracts) a bonus when backing up scores.
3. Some Representative Game-Playing Programs
Chess
Kister, et al (1957) describe the earliest chess system programmed on
a computer (MANIAC lat Los Alamos). It used a reduced board
(6 X 6) and played rather poorly.
BerjisteiiL,__£t_al (1958) describe a chess system programmed at IBM.
It also played rather poorly but on a full (8 X 8) board
Newell, Shaw and Simon (1958) present another early chess program
under development at Carnegie
Kotok (1962) discussed an early M. I.T. program later taken to Stanford
by John McCarthy and modified slightly. This one achieved the
level of mediocre play.
Adelson - Velskii, et al (no paper available) wrote a program at the
Institute for Theoretical and Applied Physics in Moscow. This pro
gram beat the Kotok - McCarthy program in a tournament (See SICART
Newsletter, No. 4, June, 1967 p. 11).
1149
Greenblatt, et al (1967) describe an M.I.T. program now called
Mac Hack. Its level of play can be described as "middle-

amateur. It is an honorary member of the Massachusetts
chess society and has been given a class C rating. For some
example games see the following SIGART Newsletters: No. 6,
Oct. 1967, p. B (here, the computer beat H. Dreyfus who earlip r
doubted that a machine could beat even an amateur player) ;
No. 9, April 1968, pp. 9-10; No. 15, April 1969, pp. 8-10,
and No. 16, June 1969, pp. 9-11
Checkers
Samuel (1959, 1967) continues to improve a program that plays
excellent checkers but can't quite beat world champions.
Kalah
Russell (1964) wrote an early Kalah program.
Slagle and Dixon (1969) describe experiments using the game of
Kalah.
Slagle and Dixon (1970) discuss more experiments using Kalah to
test the "m & n" procedure.
(The Kalah programs are probably unbeatable by human players.)
Go
Zobrist (1969) has written a program to play this ancient and
difficult game. It plays rather poorly by human standards
and does no tree searching. For an example of how Zobrist's

program performs, see SIGART Newsletter No. 18, pp. 20-22,
October 1969.
1150
F. References
Amarel, S. (1967)
"AnApproach to Heuristic Problem-Solving and Theorem Proving in the

Bernstein, A. et al. (1958)
"A Chess-Playing Program for the IBM 704 Computer," Proc. of the Western
Joint Computer Conference, pp. 157-159, 1958 .
Edwards, D. and T. Hart (1963)
"The a-g Heuristic,"

Massachusetts Institute of Technology Artificial
Intelligence Memo no. 30 (Revised), Oct. 28, 1963 (Originally printed
as "The Tree Prune (TP) Algorithm," Dec. 4, 1961).
Good, I. (1968)
Intelligence 2,
"A Five-Year Plan for Automatic Chess," in Machine
Publishing Co., Inc.,
E. Dale and D. Michie (Eds. ), American Elsevier
New York, 1968, pp. 89-118.
Greenblatt, R. , et al (1967)
"The Greenblatt Chess Program," Proc. ol the AFIPS Fall Joint Computer
Conference, Anaheim, Call 1., 1967, pp. 801-810

Paths," lEEE Trans, on Systems Sciences and Cybernetics, Vol. SSC-4 ,
No. 2, July, 1968, pp. 100-107.
Kister, J. , et al (1957)
"Experiments in Chess," J. of the ACM, Vol. 4, No. 2, pp. 174-177,
April, 1957.
Kotok, A. (1962)
"A Chess Playing Program for the IBM 7090," unpublished B.S. Thesis,
Massachusetts Institute of Technology, 1962.
Newell, A., J. Shaw and H. Simon (1958)
'Chess Playing Programs and tho Problem ol Complexity," IBM Journal of

Research and Development, vol. 2, pp. 320-335, Oct., 1958. Reprinted in
Computers and Thought, Feigenbaum, E. and J. Feldman (Eds.) , McGraw-Hill
V-52
Nilsson, N. (1968)
"Searching Problem-Solving and Game-Playing Trees for Minimal Cost

Solutions," Proc. IFIP Cong. 68 , Edinburgh.
Russell, R. (1964)
-
"Kalah The Game and The Program" Stanford University Artificial Intelligence
Project Memo No. 22, Sept. 3, 1964.
Samuel, A. (1959)
' I
JoZ f v^ J" pp . 211

MaChln Learnln Us
Journal, ° -229, 1959.
* the Game of Checkers," IBM
Reprinted ln Computers and ThLht,
'»«
fl
Vol^,
leigenbaum E. and J.
Eeldman (Eds.), McGraw-Hill BoT^Cc , New York" 1963
Samuel , A. (1967)
"Some Studies in Machine Learning Using the Game of Checkers 11. Recent
Progress," IBM Journal of Research and Development, Vol. 11, No. 6,
Nov. 1967, pp. 601-617.
Shannon, C. (1950)
"Programming a Digital Computer for Playing Chess." Philosophy Magazine
March 1950, Vol. 41, pp. 356-375, Reprinted in The World of
Mathematics, Newman (Ed.) Vol. 4, Simon & Schuster, 1954, New York.
Slagle, J. (1963b)
"Game Trees, M & N Minimaxing, and the M
Artificial Intelligence Group Report No. 3. UCRL-4671 , University' "
& N Alpha-Beta Procedure
of
Calif. Lawrence Radiation Laboratory, Livermore,
Calif. Nov. ,1963.

"Experiments with a Multipurpose, Theorem-Proving Heuristic Program, '

M
Experiments with Some Programs that Search Game Trees," J. of ACM
Vol. 16, No. 2, April 1969, pp. 189-207.
Slagle, J. and J. Dixon, (1970)

"Experiments with the M& N Tree Searching Program, " to appear
Zobrist, A. (1969)
"A Model of Visual Organization for the Game of Go in Proc. AFIPS

Spring Joint Computer Conf. pp. 103- ,
112, 1969.
V-53
(Chapter VI)
1. Fundamentals of Logic
Our rather superficial treatment of mathematical logic can be
augmented by consulting some of the standard textbooks. Two excellent
ones are those of Mendelson (1964) and Robbin (1969). For the specialist
there is the classic by Alonso Church ( 1956 ). These treat what might be called
"classical logic"; the resolution principle (or indeed any discussion of
automatic theorem-proving) has not yet found its way into textbooks on logic.
We have based this chapter on the first order predicate calculus with
resolution because of its apparent importance in automatic problem-solving.
A notable omission, however, is any special discussion of the equality
relation. It is still not clear how the equality relation (and other standard,
übiquitous relations) ought to be "built-in" to automatic theorem-provers.
A discussion of these complexities would have been beyond the scope of the
book. One scheme for building the equality relation into a resolution
theorem-prover is discussed by Robinson and Wos (1969).
It also is becoming clear that complex, general problem-solvers will need
facilities for higher-order logics. For a discussion of the application of
higher order logics to problem-solving, see McCarthy and Hayes (1969). Robbin's
book (1969) contains a section on second order logic, and some papers by J. A.
Robinson (1968a, 1969) discuss the general problem of proof procedures for higher
order logics.
The steps that we have outlined for converting any wff into clause form are
based on the procedure of Davis and Putnam (1960). Clause form is also called
quantifier-free, conjunctive normal form.
2. Herbrand Proof Procedures and Resolution
The resolution principle in automatic theorem-proving is based on the
1153
"semantic tableaux" proof procedure of Herbrand (1930). A direct implemen-
tation of Herbrand' s procedure would be grossly inefficient; improvements
due to Pra w itz (1960) and others ultimately led to the resolution principle of
J. A. Robinson (1965a). Our exposition of resolution proof methods, using the
notion of semantic trees, is based on that of Kowalski and Hayes (1969). (See
also J. A. Robinson (1968b).) This semantic tree formulation makes obvious the
relationship between resolution and Herbrand methods and also justifies the use
of inference rules more general than simple resolution. Our proof of the
completeness of resolution is a special case of a proof of the completeness of
a more general inference rule given by Kowalski and Hayes (1969).
A clearly written, concise review of the resolution principle with proofs
of its soundness and completeness can be found in a paper by Luckham (1967).
J. A. Robinson's initial paper (Robinson, 1965a)a150 contains proofs of the
soundness and completeness of resolution Both of these last mentioned papers
also contain proofs of the "correctness" of the unification algorithm. J. A.
Robinson (1970) has also written an excellent survey entitled "The Present
State of Mechanical Theorem-Proving".
1154
E. References
Church, A. (1956)
Introduction to Mathematical Logic, Princeton University Press,

Princeton, New Jersey, 1956.
Davis, M. and H. Putnam (1960)
"A Computing Procedure for Quantification Theory," Journal ACM, Vol. 7,

No. 3, pp. 201-215, Ju1y, 1960.
Herbrand, J. (1930)
"Recherches sur la theorie de la demonstration," Travaux de la Societe
des Sciences et dcs Lettres de Varsovie, Clas.se 111 Sciences Mathematiques
et Physiques, No. 33, 1930.
Kowalski, R. and P. Hayes (1969)
"Semantic Trees in Automatic Theorem-Proving", in Machine Intelligence 1 .

. ,
B. Meltzer and D. Michie (Eds ) American Elsevier Publising Co. Inc.
,
New York ,1969, pp. 87-101.
Luckham, D. (1967)
"The Resolution Principle in Theorem-Proving, "

in Machine Intelligence 1,
N. Collins and D. Michie (Eds. ), American Elsevier Publishing Co., Inc.,
1967, pp. 47-61.
McCarthy, J. and P. Hayes (1969)

Intelligence
"Some Philosophical Problems from the Standpoint of Artificial
and D. Michie (Eds. ), American
in Machine Intelligence 4, B. Meltzer
ElseViTr~P"u¥]T.s~h7ng Co., Inc., New York, 1969, pp. 463-Ô2.
Mendelson, E. (1964)
Introduction to Mathematical Logic. D. Van Nostrand Company, Inc.
Princeton, N.J. 1964. ,
Prawitz, D. (1960)
Procedure," Theoria, Vol. 26, pp. 102-139, 1960.
"An Improved Proof
Robbin, J. (1969)
Mathematical Logic: A First Course, W. A. Benjamin, Inc. New Y0rk, ,
1969.
1155
Robinson, G. and L. Wos
"Paramodulation
(1969)
.
and Theorem-Proving in First-Order Theories with Equality
B. Meltzer and D. Michie (Eds .) American
Elsevier Publishing Co., Inc., New York, 1969, pp. 135-150
Robinson, J. A. (1965a)
"A Machine-Oriented Logic Based on the Resolution Principle,'
J. ACM, Vol. 12, No. 1, pp. 23-41, Jan., 1965.
Robinson, J.A (1968a)

"New Directions in Mechanical Theorem Proving," Proc. of the IFIP Cong.
1968, Edinburgh, 1968.
Robinson, J. A. (1968b)
"The Generalized Resolution Principle, in Machine Intelligence 3,

D. Michie (Ed.), American Elsevier Publishing Co., Inc., New York,
pp. 77-93, 1968.
Robinson, J. A. (1969)
"Mechanizing Higher Order Logic," in Machine Intelligence 4, B. Meltzer

and D. Michie (Eds.), American Elsevier Publishing Co., Inc., New York,
1969.
"The Present State of Mechanical Therem Proving," Formal Systems and

Non-Numerical Problem > Solving by Computer, M. Mesarovic and R. Banerji
(Eds.)
1156
(Chapter VII)
1 . Development of Formal Logic Methods
We have already mentioned that work on techniques for solving
problems using formal logic methods was stimulated by the "advice taker"
memoranda of McCarthy (1958, 1963) . Work toward implementing such
a system was undertaken by Black (1964) . Cordell Green was the first to
develop a formal logic problem solver using a complete inference system
(resolution) for first-order logic. Much of this work is described in his
dissertation (Green, 1969a) and in two papers (Green, 1969b, 1969c).
Professor McCarthy continued his investigations on the re-
quirements for a general, formal problem-solving system. He was particularly
concerned with the necessity for including higher (than first) order logic
features in order to formalize such concepts as situations, future operators,
actions, strategies, results of strategies, and knowledge. An excellent
discussion of these ideas is contained in the paper by McCarthy and Hayes
(1969) .
Many of the issues raised by McCarthy and Hayes are beyond
the scope of an introductory text . Our treatment of formal logic methods in
this chapter is based almost exclusively on the work of Green (1969a) .

2 . Question-Answering Systems
One of the tasks that could be given to a formal problem-solving
system is that of "question answering." This task involves a sophisticated
type of information retrieval in which the answers to queries require that
logical deductions be made from various facts stored in the data base. The
design of question-answering systems also raises the question of how to
VII-31
translate between a natural language, such as English, and a formal language,
such as the predicate calculus, used by the deductive system
An early general question-answering system was developed by
Raphael (1964 a, 1964b) . Raphael concentrated on the deductive and associative
mechanisms needed and largely ignored the issue of natural-language translation
On the other hand, Bobrow (1964a, 1964b) developed a system for solving simple
algebra problems stated in English. His system could translate these into the
appropriate equations to be solved. Another general question-answering system
called DEDUCOM (without English-logic translation abilities) was developed by
Slagle (1965) . Green and Raphael (1968) collaborated in the development of a
question-answering system using resolution and first-order logic. Coles (1968)
has developed a limited English-logic translation program that has been added
to this question-answering system.
Two good surveys of work on natural-language question-answering
systems have been written by Simmons (1965, 1970) .

3. Answer-Extraction Processes
Although the subject of computing instances of existentially
quantified variables has been discussed in classical proof theory.
Green (1969b) was the first to propose a definite
procedure for resolution-based systems. The answer-extraction method discussed
in this chapter is a generalization of Green's technique and is based on a
paper by Luckham and Nilsson (1970) .

4 . Example Applications of the Formal Logic Method
Our automatic program-writing example is an adaptation of one
discussed by Green (1969 a, Appendix C) . The problem of writing computer
VII-32
programs is related to that of proving them correct. There is a substantial
body of work on this latter subject including papers by McCarthy (1962) ,

Floyd (1967b) , and Manna (1969) . London ( 196§ gives a good survey of work
on proving the correctness of programs. A somewhat different (but still
resolution-based) procedure for automatic program writing is described by
Waldinger and Lee (1969) .

Applications of theorem-proving techniques to automatic problem
solving are well discussed by Green (1969 a, 1969c) . The state-variable method
described in this chapter was proposed by Green.
One of the most obvious applications of automatic theorem
provers (although it is not discussed in this chapter) is proving mathematical
theorems. This application has been pursued by Robinson and Wos (1969) and
by Guard, et al . (1969). In particular, Guard's program (with some human
aid) has succeeded in finding the first proof for a conjecture in modular
lattice theory.
VII-33
E. References
Black, F. (1964)
"A Deductive Question-Answering System, "Ph.D. Dissertation, Harvard,
June 1964. Reprinted in Semantic Information Processing, M. Minsky (Ed) ,
Bobrow, D. (1964a)
"Natural Language Input for a Computer Problem-Solving System," Ph.D.

dissertation, MIT, Sept. 1964. Reprinted in Semantic Information
Processing, M. Minsky (Ed), MIT Press, Cambridge, Mass., 1968.
Bobrow, D. (1964b)
"A Question-Answering System for High-School Algebra Word Problems,'

in Proc. of AFIPS Fall Joint Computer Conference, 1964, pp. 591-614.
Coles, L. S. (1968)
An On-Line Question-Answering System with Natural Language and Pictorial

Input," Proc.ACM 23rd Nat. Conf., 1968, Brandon Systems Press, Princeton,
N.J., pp. 157-167.
Floyd, R. (1967b)
"Assigning Meanings to Programs," Proc. of Symposia in Applied
Mathematics, American Mathematical Society, Vol. 19, pp. 19-32, 19b/.
Green, C. (1969a) „
"The Application of Theorem-Proving to Question-Answering Systems,June,
Ph.D
dissertation, Stanford University, Electrical Engineering Dept.,

Project Memo
1969. Also printed as Stanford Artificial Intelligence
AI-96, June,l969.
Green. C. (1969b)
"Theorem-Proving by Resolution as a Basis for Question-Answering Systems,

in Machine Intelligence 4, B. Meltzer, and D. Michie (Eds. ), American
Elsevier Publishing Co., Inc., New Y0rk, 1969, pp. 183-205.
VII-34
Green, C. (1969c)
"Application of Theorem-Proving to Problem Solving," Proc. Int'l Joint

Conference on Artificial Intelligence, Wash. D.C., May, 1969.
Green, C. and B. Raphael (1968)

The Use of Theorem-Proving Techniques in Question-Answering Systems,"
Proc. of 23rd Nat'l. Conf. ACM,, Brandon Systems Press, Princeton,
N.J. , pp. 159-181.
Guard, J. et al, (1969)
"Semi-Automated Mathematics," J . oi ACM , Vol. 16 , No. 1, pp. 49-62,

Jan, 1969.
London, R. (1969)
"Bibliography on Proving the Correctness of Computer Programs," Tech.
Report #64, University of Wisconsin, Computer Sciences Dept.
June, l969. ,
Luckham, D. and N. Nilsson (1970)

"Extracting Information from Resolution Proof Trees," to appear.
Manna, Z. (1969)
"The Correctness of Programs," J. of Computer and System Sciences, Vol. 3
May ,1969.
McCarthy, J. (1958)
Thought Processes, Vol 1
"Programs with Common Sense," in Mechanization of
National Physical Laboratory, London, Nov.
pp. 77-84, Proc. Symposium,
Minsky (Ed )
24-27, 1958. Reprinted in Semantic Information Processing, M.
MIT Press, Cambridge, Ma55. ,1968, pp. 403-410.
McCarthy, J. (1962)
"Towards a Mathematical Science of Computation, Proc. IFIP Congress 62,
North Holland Publishing Co. , Amsterdam, 1962.
McCarthy, J. (1963)
'Situations, Actions and Causal Laws," Stanford University Artificial
mation Processing, M. Minsky, (Ed.) MIT Press, ,
Cambridge, Ma55 .,1968
pp. 410-418.
VII-35
"Some Philosophical Problems from the Standpoint of Artificial Intelligence

in Machine Intelligence 4, B. Meltzer and D. Michie (Eds. ), American
Elsevier Publishing Co., Inc., New York, 1969, pp. 463-502.
Raphael, B. (1964a)
"SIR:A Computer Program for Semantic Information Retrieval," Ph.D

dissertation, MIT, June 1964. Reprinted in Semantic Information
Processing, M. Minsky (Ed.) ,
MIT Press, Cambridge, Mass. 1968.
Raphael, B. (1964b)
"A Computer Program Which 'Understands'", in Proc. of AFIPS Fall Joint
Computer Conference, 1964, pp. 577-589.
Robinson,
in
G. and L. Wos
"Paramodulation
Machine Intelligence 4,
Elsevier Publishing Co.,
(1969)
Inc.,
B. Meltzer and D. Michie (Eds. ) American
New York, 1969, pp. 135-150
.
and Theorem-Proving in First-Order Theories with Equality.'
Simmons, R. (1965)
"Answering English Questions by Computer: A Survey," Communications of
the ACM, Vol, 8, Jan. 1965, pp. 53-70.
Simmons, R. (1970)
"Natural Language Question Answering Systems: 1969," Comm. ACM,

Vol. 13, No. 1, pp. 15-30, January 1970. '
Slagle, J. (1965)
"Experiments with a Deductive-Question Answering Program, Communcations of
the ACM, Vol. 8, pp. 792-798, Dec. 1965.
Waldinger, R. and R. Lee (1969)

"PROW: A Step Toward Automatic Program-Writing," Proceedings of
Int'l Joint Conference on Artificial Intelligence , Wash D C . .
May, 1969.
VI I -36
(Chapter VIII)
E . Bibliographical and Historical Remarks
1 . Discussions of Search Strategies
An excellent discussion of the problem of developing
heuristically effective search strategies while maintaining logical
completeness is contained in a paper by J. A. Robinson (1967). G. A
Robinson, et al (1964) give a very clear exposition of several strategies
with many examples.
2 . Simplification Strategies
The problem of the elimination of subsumed clauses during
a search for a proof is more subtle than it might appear. Kowalski (1970a)
acknowledges inadequacies in the treatment of this subject by Kowalski and
Hayes (1969) and refers the reader to his dissertation (Kowalski, 1970b) for
a complete discussion.
3 . Refinement Strategies
The Ancestry Filtered (AF) form strategy is the simplest of
a family of related strategies. Our Theorem 8.1 states that the AF-form
strategy is logically complete; a proof of this theorem is given in Luckham
(1969) . Although we show the completeness of the set-of -support strategy as a
corollary of Theorem 8.1, it was in fact first developed and justified by
Wos. et al (1965) .
Several elaborations of the AF-form strategy are possible
Some of these combine the AF-form strategy with a strategy proposed by
Andrews (1968) involving merges . Among the papers proving the completeness
of AF-form with merging are Kieburtz and Luckham (1970) , Yates, Raphael, and
Hart (1970) and Anderson and Bledsoe (1970). The first of these contains
VIII-20
other results about the properties of AF-form proofs, while the last two
use rather novel methods of proving completeness that are of independent
interest . Anderson and Bledsoe use their method to establish the
completeness of other strategies as well. A paper by Loveland (1968)
establishes the completeness of another restriction on the AF-form
strategy .
The model strategies are elaborations of the P deductions originally
proposed by J. A. Robinson (1965b). Slagle (1967) proved the completeness
of some very general model strategies. Our Theorem 8.2 is due to Luckham
(1969) and is an easier-understood, special case of one of Slagle 's theorems.
Meltzer (1966, 1968) provides some additional results about P -type deduc-
tions .
4 . Ordering Strategies
The unit preference strategy was proposed and justified in
a paper by Wos , et al (1964) . It and the set of support strategy have been
incorporated as basic parts of a number of automatic theorem-provers .

The reader probably noticed that all of the search strategies
discussed in this chapter involved "syntactic" rather than "semantic" rules
(that is, search restrictions and orderings were based on the form of the
clauses and possible deductions rather than on their meaning) . Semantic
guidance could be provided in a number of ways, but there have not yet
been many attempts in this direction. One might ask whether it would be
possible to use an "evaluation function" over pairs of clause that are
candidates to be resolved. Presumably this evaluation function could be
influenced by the available semantic information as well as by the forms
of the candidate clauses. Some theoretical results about the properties
VIII-21
of strategies using evaluation-functions are contained in a paper by
Kowalski (1970 a ). Kowalski' s results on searching "inference-graph"
structures parallel those of Hart, et al (1968) for state-space graph
structures .
5. Examples of Implementations
Several automatic theorem-proving programs have now been
written. As examples we might mention those of Robinson and Wos (1969),
Allen and Luckham (1970) , Guard, et al (1969) and the Green-Raphael-
Yates system recently modified by Garvey and Kling (1969).
VIII-22
F. References
Allen, J. and D. Luckham (1970)
"An Interactive Theorem-Proving Program," in Machine Intelligence 5
Andrews, P. (1968)
"Resolution with Merging," Journal of ACM, Vol. 15, No. 3, pp 367-381

July 1968. (Also see corrections in JACM, Vol. 15, No. 4, Oct. 1968
p 720).
Anderson, R. and W. Bledsoe (1970)
"A Linear Format for Resolution with Merging and a New Technique for
Establishing Completeness ," Journal of ACM (to appear) .
Garvey, T. and R. Kling (1969)
"User's .
Guide to QA3 5 Question-Answering System," Stanford Research
Institute Artificial Inetlligence Group Technical Note 15, Dec, 1969.

"Semi-Automatod Mathematics," J. ol ACM, Vol. 16, No. 1, pp. 49-62,
Jan, 1969.

Paths," lEEE Trans, on Systems Sciences and Cybernetics, Vol. SSC-4,
No. 2, July, 1968, pp. 100-107.
Kieburtz, R. and D. Luckham (1970)

"Compatibility of Refinements of the Resolution Principle," to appear.
Kowalski, R. (1970a)
"Search Strategies for Theorem-Proving" in Machine Intelligence 5.
Kowalski, R. (1970b)
"Studies in the Completeness and Efficiency of Theorem-Proving by

Resolution," Ph.D. Thesis, Univers ity of Edinburgh.
VIII-23
Kowalski, R. and P. Hayes (1969)
"Semantic Trees in Automatic Theorem- Proving" in Machine Intelligence 4

,
B. Meltzer and D. Michie (Eds .) .American
Elsevier Publising Co. Inc. ,
New York ,1969, pp. 87-101.
Loveland, D. (1968)
"A Linear Format for Resolution," Carnegie-Mellon University Computer
Science Dept. Report, December 1968. Also to appear in Proc. IRIA 1968
Symposium on Automatic Deduction.
Luckham, D. (1969)
"Refinement Theorems in Resolution Theory," Stanford Artificial
Intelligence Project Memo AI-81, March 24, 1969. Also to appear in
Proc. IRIA 1968 Symposium on Automatic Deduction.
Me l l ze r , B . (1966)
"Theorem-Proving for Computers : Some Results on Resolution and

Renaming," Computer Journal, Vol. 8, pp 341-343, 1966.
Meltzer, B. (1968)
"Some Notes on Resolution Strategies," in Machine Inetlligence 3,
1968, pp. 71-75.

"Paramodulation
(1969)
and Theorem-Proving in First-Order Theories with Equality
Elsevier Publishing Co., Inc., New York, 1969, pp. 135-150.
.
Robinson, G. A., L.T. Wos and D. F. Carson (1964)
"Some Theorem- Proving Strategies and Their Implementation," Argonne
Nat'l Laboratories Technical Memorandum No. 72, 1964.
Robinson, J. A. (1965b)
"Automatic Deduction with Hyper-Resolution," Int'l J. of Comp. Math.

Vol. 1, pp. 227-234, 1965.
VI I I -24
"Heuristic and Complete Processes in the Mechanization of Theorem-
Proving, ' in Systems and Computer Science, J. T. Hart and S. Takasu
(Eds.), Univ. of Toronto Press, 1967,pp. 116-124.
Slagle, J. (1967)
"Automatic Theorem-Proving with Renamable and Semantic Resolution,"

J. of ACM, Vol. 14, No. 4, pp. 687-697, Oct., 1967.
Wos, L. D. Carson, and G. Robinson (1964)

"The Unit Preference Strategy in Theorem Proving, "
Proc. of the AFIPS
1964 Fall Joint Computer Conf., Vol. 26, pp. 616-621, 1964.
Wos, D., G. Robinson, and D. Carson (1965)
"Efficiency and Completeness of the Set of Support Strategy in Theorem-

Proving," JACM, Vol. 12, No. 4, pp. 536-541, Oct., 1965.
Yates, R., B. Raphael, and T. Hart (1970)
"Resolution Graphs," Stanford Research Institute Artificial Intelligence

Memo.
VIII-25
COMBINED REFERENCE LIST
Allen, J. and D, Luckham (1970)
"An Interactive Theorem-Proving Program," in Machine Intelligence 5
Anderson, R. and W. Bledsoe (1970)
A Linear Format for Resolution with Merging and a New Technique for
Establishing Completeness ," to appear in Journal of ACM.
Andrews, P. (1968)
"Resolution with Merging," Journal of ACM, Vol. 15, No. 3, pp 367-381

July 1968. (Also see corrections in JACM, Vol. 15, No. 4, Oct. 1968
p 720).
Amarel, S. (1965)
"Problem Solving Procedures for Efficient Syntactic Analysis" ACM

20th National Conference, 1965 (Also printed as Scientific Report
No. 1, AFOSR Contract No. AF49(638)-1184, 1968).
Amarel, S. (1967)

Amarel, S. (1968)
"On Representations of Problems of Reasoning About Actions,"

in Machine Intelligence 3, D. Michie (Ed), American Elsevier, New
York, 1968, pp. 131-171.
Amarel, S. (1969)

Vol. 1, No. 2, 1969.
1169
Ball, W. (1931)
Mathematical Recreations and Essays, Tenth Edition, 1931,

London,
Mac Millan &Co
(15 puzzle, pp. 224-228; Tower of Hanoi, pp. 228-229.)
.
Banerji, R. (1969)
Theory of Problem Solving: An Approach to Artificial Intelligence,
American Elsevier Publishing Co. Inc., New York, 1969.
Bellman, R. and S. Dreyfus (1962)

Applied Dynamic Programming, Princeton University Press, 1962.
"The Traveling Salesman Problem: A Survey," Operations Research

Vol. 16, No. 3, May-June 1968, pp. 538-558.
Berge, C. (1962)
The Theory of Graphs and its Applications, (Translated by Alison Doig) ,
John Wiley & Sons, Inc. New York, 1962. (First published in France
in 1958 by Dunod, Paris).
Bernstein, A. et al . (1958)
"A Chess-Playing Program for the IBM 704 Computer, " Proc. of the Western
Joint Computer Conference, pp. 157-159, 1958.
Black, F. (1964)
A Deductive Question-Answering System, "Ph.D. Dissertation, Harvard,

June 1964. Reprinted in Semantic Information Processing, M. Minsky (Ed) ,
1170
Bobrow, D. (1964a)
"Natural Language Input for a Computer Problem-Solving System," Ph.D.
dissertation, MIT, Sept. 1964. Reprinted in Semantic Information
Processing, M. Minsky (Ed), MIT Press, Cambridge, Mass., 1968.
Bobrow, D. (1964b)
"A Question-Answering System for High-School Algebra Word Problems,
in Proc. of AFIPS Fall Joint Computer Conference, 1964, pp. 591-614.
Buchanan, 8. , G. Sutherland, and E. Feigenbaum (1969)
"Heuristic Dendral: A Program for Generating Explanatory Hypotheses

in Organic Chemistry." in Machine Intelligence 4, B. Meltzer and D.
Michie (Eds.), American Elsevier Publishing Co. , Inc., New York,
1969, pp. 209-254.
Collins,N. and D. Michie (Eds.)

Machine Intelligence 1, American Elsevier Publishing Co., Inc.
New York, 1967.
Campbell, D. (1960)
"Blind Variation and Selective Survival as a General Strategy in

Knowledge-Processes," in Self-Organizing Systems, M. Yovits & S. Cameron
(EdsJ.Pergamon Press, New York 1960, pp. 205-231.
Church, A. (1956)
Introduction to Mathematical Logic, Princeton University Press,

Princeton, New Jersey, 1956.
Coles, L. S. (1968)
An On-Line Quest ion-Answering System with Natural Language and

Pictorial Input," Proc. ACM 23rd Nat'l. Conf., 1968, Brandon Systems
Press, Princeton, N.J., pp. 157-167.
1171
Dale, E. and D. Michie (Eds)
Machine Intelligence 2 American Elsevier Publishing Co., Inc., New
York, 1968.
Davis, M. and H. Putnam (1960)

"A Computing Procedure for Quantification Theory, " Journal ACM, Vol 7
No. 3, pp. 201-215, Ju1y, 1960.
De Russo, P. , R. Roy and C. Close (1965)

State Variables for Engineers, Wiley, New York, 1965
Dijkstra, E. (1959)
"A Note on Two Problems in Connection with Graphs ," Numerische
Mathematik, 1, 1959, pp. 269-271
Doran, J. (1968)
"New Developments of the Graph Traverser, "

E. Dale and D. Michie (Eds), American Elsevier Publishing Co. , Inc.,"
New York, 1968, pp. 119-135.
Doran, J. and D. Michie (1966)

"Experiments with the Graph Traverser Program, " Proceedings of the
Royal Socitey, A, Vol. 294, pp. 235-259, 1966.
Dreyfus, H. (1965)
Alchemy and Artificial Intelligence, Rand Corporation Paper P3244
(AD 625 719), December ,1965.
-R4-
Dreyfus, S. (1969)
"An Appraisal of Some Shortest Path Algorithms," Operations Research,
Vol. 17, No. 3, pp. 395-412, May-June 1969.
Dudeney, H. (1958)
The Canterbury Puzzles, Dover Publications, Inc., New York, 1958.
(Originally published in 1907.)
Dudeney, H. (1967)
536 Puzzles and Curious Problems, Martin Gardner (Ed. ), Charles Scribner s
Sons, New York, 1967. (A collection from two of Dudeney' s books:
Modern Puzzles, 1926, and Puzzles and Curious Problems, 1931).
Edwards, D. and T. Hart (1963)

"The a-|9 Heuristic," Massachusetts Institute of Technology Artificial
Intelligence Memo no. 30 (Revised), Oct. 28, 1963 (Originally printed
as "The Tree Prune (TP) Algorithm," Dec. 4, 1961).
Ernst, G. (1969)
"Sufficient Conditions for the Success of GPS," Journal of ACM, Vol.

16, No. 4, Oct. 1969, pp. 517-533.

GPS: A Case Study in Generality and Problem Solving ACM Monograph
1173
"Artificial Intelligence Research," lEEE Trans, on Info. Theory,

Vol. IT-9, No. 4, Oct., 1963, pp. 248-261
"Artificial Inteligence: Themes in the Second Decade," Proc. of
IFIPS 68 Congress. Edinburgh, Aug. 1968. Also printed as Stanford
University Artificial Intelligence Project Memo No. 67, Aug. 15, 1968
Feigenbaum, E. and J. Feldman (Eds.)

Computers and Thought, McGraw Hill Book Co., New Y0rk, 1963.
Feldman, J. and D. Gries (1968)

"Translator Writing Systems" Comm. of ACM, Vol. 11, No. 2, Feb., 1968,
pp. 77-113.
Fikes, R. (1970)
"Ref-Arf: A System for Solving Problems Stated as Procedures,'

Artificial Intelligence, Vol.l, No.l, 1970.
Floyd, R. (1967a)
"Nondeterministic Algorithms," J. of ACM, Vol. 14, No. 4, 0ct., 1967,
pp. 636-644.
Floyd, R. (1967b)
"Assigning Meanings to Programs," Proc. of Symposia in Applied
Mathematics, American Mathematical Society, Vol. 19, pp. 19-32, 1967.
1174
Fogel, L. A. Owens and M. Walsh (1966)
Artificial Intelligence Through Simulated Evolution, John Wiley, New York,

1966. " ~~ ~~ " ~
Ford, L. Jr., and D. Fulkerson (1962)

Flows in Networks, Princeton University Press, Princeton, New Jersey, 1962
Gardner, M. (1959)
_
The Scientific American Book of Mathematical .
Puzzles
.—
- ...„
~ „ and Diversions,
...,-.,...v,u 11 lilt J-'J.V^_XtJJ.»_»ll^)
Simon and Schuster, New York, 1959
Gardner, M. (1961)
The Second Scientific American Book of Mathematical Puzzles and Diversions
Simon and Schuster, New Y0rk, 1961
Gardner, M. (1964, 1965 a,b,c)

Mathematical Games, Scientific American, Vol. 210, No. 2, Feb., 1964,
pp. 122-13p;Vol .
212, No. 3, March, l96s, pp. 112-117; Vol. 212, 6 No!
June, l96s, pp. 120-124; Vol. 213, No. 3, Sept., 1965, pp. 222-236.
Garvey, T. and R. Kling (1969)

.
User's Guide to QA3 5 Question-Answering System," Stanford Research
Institute Artificial Inetlligence Group Technical Note 15, Dec, 1969.
Gelernter, H. (1959)
'Realization of a Geometry Theorem-Proving Machine," Proc. of an Int l

Conf. on Info. Proc ,
UNESCO House, Paris, 1959, pp. 273-282. Reprinted
'
in Computers and Thought , Feigenbaum, E. and J. Feldman (Eds.),
McGraw-Hill
-H7-
Gelernter, H. J. Hansen, and D. Loveland (1960)
"Empirical Explorations of the Geometry Theorem Proving Machine," Proc
of the Western Joint Computer Conf. ,1960, Vol. 17, pp. 143-147. Reprinted
in Computers and Thought, Feigenbaum, E. and J. Feldman (Eds.), McGraw-Hill
Golomb, L. and L. Baumert (1965)

"Backtrack Programming, " J. of ACM, Vol. 12, No. 4., 0ct. ,1965, pp. 516-
524.
Good, I. (1968)
"A Five-Year Plan for Automatic Chess in Machine Intelligence 2,
E. Dale and D. Michie (Eds. ), American Elsevier Publishing Co., Inc.,
New York, 1968, pp. 89-118.
Green, C. (1969a)
"The Application of Theorem-Proving to Question-Answering Systems" Ph.D
dissertation, Stanford University, Electrical Engineering Dept., June
1969. Also printed as Stanford Artificial Intelligence Project Memo
AI-96, June, l969.
Green, C. (1969b)
"Theorem-Proving by Resolution as a Basis for Question-Answering Systems,'
in Machine Intelligence 4, B. Meltzer, and D. Michie (Eds. ), American
Elsevier Publishing Co., Inc., New Y0rk, 1969, pp. 183-205.
Green, C. (1969c)
"Application of Theorem-Proving to Problem Solving," Proc. Int'l Joint
Conference on Artificial ,
Intelligence, Wash. D. C. May, 1969 .
Green, C. and B. Raphael (1968)

"The Use of Theorem-Proving Techniques in Question-Answering Systems,
Proc. of 23rd Nat' l. Conf. ACM, Brandon Systems Press, Princeton, N.J.,
pp. 169-181, 1968.
1176
Greenblatt, R. , et al (1967)
"The Greenblatt Chess Program," Proc. of the AFIPS Fall Joint Computer
Conference, Anaheim, Calif., 1967, pp. 801-810
"Semi-Automated Mathematics," J. of ACM, Vol. 16, No. 1, pp. 49-62,

Jan, 1969.

Paths," lEEE Trans, on Systems Sciences and Cybernetics, Vol. SSC-4,
No. 2, July, 1968, pp. 100-107.
Herbrand, J. (1930)
"Recherches sur la theorie de la demonstration," Travaux de la Societe

,
dcs Sciences et dcs Lettres de Varsovie Classe 111 Sciences Mathematiques
et Physiques, No. 33, 1930.
Jelinek, F. (1969)
"Fast Sequential Decoding Algorithm Using a Stack," IBM J. of Res, and Dev. J
Vol. 13, No. 6, Nov, 1969, pp. 675-685.
Kieburtz, R. and D. Luckham (1970)

"Compatibility of Refinements of the Resolution Principle," to appear.
Kister, J. , et al (1957)
"Experiments in Chess," J. of the ACM, Vol. 4, No. 2, pp. 174-177,

April, 1957.
Kotok, A. (1962)
"AChess Playing Program for the IBM 7090," unpublished B.S. Thesis,
Massachusetts Institute of Technology, 1962.
Kowalski, R. (1970a)
"Search Strategies for Theorem-Proving' in Machine Intelligence 5.
1177
Kowalski, R. (1970b)
"Studies in the Completeness and Efficiency of Theorem-Proving by

Resolution," Ph.D. Thesis, Univers ity of Edinburgh.
Kowalski, R. and P. Hayes

"Semantic
(1969)
.
Trees in Automatic Theorem-Proving", in Machine Intelligence 4
B. Meltzer and D. Michie (Eds. ) American Elsevier Publising Co. Inc.
New York ,1969, pp. 87-101.
,

"Branch and Bound Methods: a Survey," Operations Research, Vol. 14, No "1
pp. 699-719, July-August ,l966.
Levy, D. (1969)
"A Comment on Some Tree Searching Methods Which is Designed to Optimize

the Use of Storage," ACM SIGART Newsletter, No. 15, April 1969, pp.
14-16.
Lin , Shen (1965)

"Computer Solutions of the Traveling Salesman Problem," The Bell System
Technical Journal, Vol. XLIV, No. 10, Dec, 1965.
Lin, Shen (1968).

"Heuristic Techniques for Solving Large Combinatorial Problems on a
Computer," Formal Systems and Non-Numerical Problem-Solving by Computer,
Case Western Reserve Uuniversity, Cleveland, Ohio, N0v. ,1968.
London, R. (1969)
"Bibliography on Proving the Correctness of Computer Programs," Tech.
Report #64, University of Wisconsin, Computer Sciences Dept. f June, l969.
1178
Loveland, D. (1968)
"A Linear Format for Resolution," Carnegie-Mellon University Computer
Science Dept. Report, December 1968. Also to appear in Proc IRIA 1968
Symposium on Automatic Deduction.
Luckham, D. (1967)
"The Resolution Principle in Theorem-Proving," in Machine Intelligence 1,

N. Collins and D. Michie (Eds. ), American Elsevier Publishing Co., Inc.,
1967, pp. 47-61.
Luckham, D. (1969)
"Refinement Theorems in Resolution Theory," Stanford Artificial
Intelligence Project Memo AI-81, March 24, 1969. Also to appear in
Proc. IRIA 1968 Symposium on Automatic Deduction.
Luckham, D. and N. Nilsson (1970)

"Extracting Information from Resolution Proof Trees," to appear.
Manna, Z. (1969)
"The Correctness of Programs," J. of Computer and System Sciences, Vol. 3
May ,1969.
Manna, Z. (1970)
"The Correctness of Non-Deterministic Programs," Artificial Intelligence
Vol. 1, No. 1, 1970.
1179
McCarthy, J. (1958)
"Programs with Common Sense," in Mechanization of Thought Processes, Vol. I,
pp. 77-84, Proc. Symposium, National Physical Laboratory, London, Nov.
24-27, 1958. Reprinted in Semantic Information Processing, M. Minsky (Ed.) ,
McCarthy, J. (1962)
"Towards a Mathematical Science of Computation, Proc. IFIP Congress 62,
North Holland Publishing Co. , Amsterdam, 1962.
"Some Philosophical Problems from the Standpoint of Artificial Intelligence

in Machine Intelligence 4, B. Meltzer and D. Michie (Eds. ), American
Elsevier Publishing Co. , Inc., New York, 1969, pp. 463-502.
McCarthy, J. (1963)
"Situations, Actions and Causal Laws," Stanford University Artificial
mation Processing, M. Minsky, (Ed.) ,
MIT Press, Cambridge, Ma55. ,1968,
pp. 410-418.
McCulloch, W. S. and W. Pitts (1943)

"ALogical Calculus of the Ideas Immanent in Neural Nets, " Bulletin of
Mathematical Biophysics, Vol. 5, ,ip. 115-137, 1943.
Meltzer, B. (1966)
"Theorem-Proving for Computers : Some Results on Resolution and

Renaming," Computer Journal, Vol. 8, pp 341-343, 1966.
-Rl2-
Meltzer, B. (1968)
"Some Notes on Resolution Strategies," in Machine Inetlligence 3,
1968, pp. 71-75.
Meltzer, B. and D. Michie (Eds.)

Machine Intelligence 4, American Elsevier Publishing Co., Inc., New York
1969.
Mendelson, E. (1964)
Introduction to Mathematical Logic. D. Van Nostrand Company, Inc. ,
Princeton, N.J., 1964.
Michie, D. (Ed.)

1968.
Michie, D. (Ed.)

1970.
Minsky, M. (1961a)
Steps Toward Artificial Intelligence," Proc. IRE, Vol. 49, pp. 8-30,
January 1961. Reprinted in Computers and Thought, Feigenbaum, E. and
J. Feldman (Eds.), pp. 406-450, McGraw-Hill Book Co., New York, 1963.
Minsky, M. (1961b)
A Selected Descriptor-Indexed Bibliography to the Literature on

Artificial Intelligence," IRE Trans, on Human Factors in Electronics,
HFE-2, pp. 39-55, March 1961. A revision is reprinted in Computers
and Thought, Feigenbaum, E. and J. Feldman (Eds.), pp. 453-523,
McGraw-Hill Book Co., New York, 1963.
1181
Minsky, M. (1967)
Computation: Finite and Infinite Machines, Prentice Hall, Inc.,
Englewood Cliffs, N.J. , 19677
Minsky, M. and S. Papert (1969)

Perceptrons:An Introduction to Computational Geometry, The MIT Press,
Cambridge, Mass. 1969.
Minsky, M. (Ed.) (1968)

Semantic Information Processing, The MIT Press,
Cambridge, Mass., 1968.
Moore, E. (1959)
"The Shortest Path Through a Maze," Proc. Int'l Symposium on the Theory of
Switching, Part 11, April 2-5, 1957, The Annals of the Computation
aboratory of Harvard University 30, Harvard University Press ,1959.
Moses, J. (1967)
Symbolic Integration, Massachusetts Institute of Technology, Project MAC,
Report MAC-TR-47 (Thesis), Dec. 1967.
Newell A. (1965)
"Limitations of the Current Stock of Ideas ab ut Problem Solving, in '
Electronic Information Handling, A. Kent and 0. Taulbee (Eds. ), Spartan
Books, Wash. D.C., 1965.
Newell, A. (1969)
"Heuristic Programming: 111-Structured Problems," Progress in Operations
Research, J. Aronofsky (Ed.), Vol. 3, Wiley, 1969.
1182
Newell, A., J. Shaw, and H. Simon (1957)
"Empirical Explorations of the Logic Theory Machine," Proc. of the
Western Joint Computer Conference, 1957, pp. 218-239. Reprinted in
,
Computers and Thought Feigenbaum, E. and J. Feldman (Eds.), McGraw-Hill
Newell, A., J. Shaw and H. Simon (1958)

"Chess Playing Programs and the Problem of Complexity," IBM Journal of
Research and Development, vol. 2, pp 320-335, Oct., 1958. Reprinted in
Computers and Thought, Feigenbaum, E and J. Feldman (Eds.) , McGraw-Hill
NewellÂ^J. Shaw and H. Simon (1959)

"Report on a General Problem-Solving Program,' Proc. of Int'l Conf.
on Information Processing, UNESCO House, Paris, pp. 256-2 64, 1969.
Nilsson, N. (1968)
"Searching Problem-Solving and Game-Playing Trees for Minimal Cost
Solutions," Proc. IFIP Cong. 68 , Edinburgh.
O'Beirne, T. H. (1961)
Puzzles and Paradoxes, New Scientist, No. 245, July 27, 1961, and No. 246,
August 3, 1961.
Ore, 0. (1962)
Theory of Graphs, American Mathematical Society Colloquium Publication,
Vol. XXXVIII, Providence, Rhode Island, 1962.
Ore, 0. (1963)
Graphs and Their Uses, Random House, 1963.
Papert, S. (1968).
"TheArtificial Intelligence of Hubert L. Dreyfus. A Budget of Fallacies,
Massachusetts Institute of Technology Artificial Intelligence Memo #54,
Jan. ,1968.
1183
Pohl , I . (1969)
"Bi-Directional and Heuristic Search in Path Problems," Stanford

University Computer Science Dept. Ph.D. Dissertation, 1969. Also
printed as Stanford Linear Accelerator Center Report No. 104, May
1969.
Pohl, I. (1970)
"First Results on the Effect of Error in Heuristic Search," in

Machine Intelligence 5.
Polya, G. (1957)
How to Solve It (Second Edition) , Doubleday & Co., Inc. Garden City
N. Y. ,1957.
Prawitz, D. (1960)
"An Improved Proof Procedure," Theoria, Vol. 26, pp. 102-139, 1960.
Quinlan, J. and E. Hunt. (1968)

"A Formal Deductive Problem-Solving System," J. of ACM, Vol. 15,
No. 4, Oct., 1968, pp. 625-646.
Raphael, B. (1964a)
"SIR: A Computer Program for Semantic Information Retrieval," Ph.D
dissertation, MIT, June 1964. Reprinted in Semantic Information
Processing, M. Minsky (Ed.) , MIT Press, Cambridge, Mass. 1968.
Raphael, B. (1964b)
"A Computer Program Which 'Understands'", in Proc. of AFIPS Fall Joint

Computer Conference, 1964, pp. 577-589.
1184
Robbin, J. (1969)
Mathematical Logic: A First Course, W. A. Benjamin, Inc., New Y0rk, 1969.
Robinson, J. A. (1965a)
"A Machine-Oriented Logic Based on the Resolution Principle,'
J. ACM, Vol. 12, No. 1, pp. 23-41, Jan., 1965.
Robinson, J. A (1965b)
"Automatic Deduction with Hyper-Resolution," Int'l J. of Comp. Math.

Vol. 1, pp. 227-234, 1965.
Heuristic and Complete Processes in the Mechanization of Theorem-

Proving, " in Systems and Computer Science, J. T. Hart and S. Takasu
(Eds.), Univ. of Toronto Press, 1967, pp. 116-124.
Robinson, J. A (1968a)
"New Directions in Mechanical Theorem Proving," Proc of the IFIP Cong.

1968, Edinburgh, 1968.
Robinson, J. A.
.
(1968b)
"The Generalized Resolution Principle," in Machine Intelligence 3,

D. Michie (Ed. ) American Elsevier Publishing Co., Inc., New York,
1968, pp. 77-93.
"Mechanizing Higher Order Logic," in Machine Intelligence 4, B. Meltzer

and D. Michie (Eds.), American Elsevier Publishing Co., Inc., New York,
1969.
1185
"The Present State of Mechanical Therem Proving, "
Formal Systems and
Non-Numerical Problem i Solving by Computer, M. Mesarovic and R. Banerji
(Eds.)
Robinson, G. A., L.T. Wos and D.F. Carson (1964)

"Some Theorem-Proving Strategies and Their Implementation, " Argonne
Nat'l Laboratories Technical Memorandum No. 72, 1964.

"Paramodulation
(1969)
and Theorem-Proving in First-Order Theories with Equality,'

Elsevier Publishing Co., Inc., New York, 1969, pp. 135-150
.
Rosenblatt, F. (1962)
Principles of Neurodynamics , Spartan Books, New York 1962.
Russell, R. (1964)
"Kalah
Project
-Memo
The Game and The Program"
No. 22, Sept. 3, 1964.
Stanford University Artificial Intelligence
Samuel, A. (1959)
"Some Studies in Machine Learning Using the Game of Checkers," IBM

Journal, Vol. 3, pp. 211-229, 1959. Reprinted in Computers and Thought,
Feigenbaum, E. and J. Feldman (Eds.), McGraw-Hill Book Co., New York, 1963,
pp. 71 - 105.
Samuel , A. (1967)
"Some Studies in MachineLearning Using the Game of Checkers 11. Recent
Progress," IBM Journal of Research and Development, Vol. 11, No. 6
Nov. 1967, pp. 601-617.
1186
Sandewall E. (1969)
"Concepts and Methods for Heuristic Search, " Proc of the International
Joint Conference on Artificial Intelligence.
Schofield, P. (1967)
"Complete Solution of the "Eight-Puzzle" in Machine Intelligence 1,
N. Collins and D. Michie (Eds), American Elsevier Publishing Co., Inc.,
—
New York, 1967, pp. 125 133.
Selfridge, 0. and J. Kelly, Jr. (1962)

"Sophistication in Computers: a Disagreement," IRE Trans, on Info.
Theory, Feb. 1962.
Shannon, C. (1950)
"Programming a Digital Computer for Playing Chess." Philosophy Magazine
March 1950, The World of
Vol. 41, pp. 356-375, Reprinted in The of
Mathematics, Newman (Ed.) Vol. 4, Simon & Schuster, 1954, New York.
Shapiro, D. (1966)
Problem," Sc.D. Thesis, Washington Univ., St. Louis, M0. ,1966.
Simmons, R. (1965)
"Answering English Questions by Computer: A Survey," Communications of
the ACM, Vol, 8, Jan. 1965, pp. 53-70.
Simmons, R. (1970)
"Natural Language Question Answering Systems: 1969, Comm. ACM,

Vol. 13, No. 1, pp. 15-30, January 1970.
1187
Slagle, J. (1961)
ior
"A Computer in Freshman Calculus (SAINT),'
Program / Sol ving Problems
Doctoral Dissertation, Mass. Inst, of Tech. Cambridge, Mass, 1961.
Also printed as Lincoln Laboratory Report SG-0001, May 10, 1961.
Slagle, J. (1963a)
Freshman Calculus," JACM, Vol. 10, No. 4, Oct. 1963, pp. 507-520.
Also in Computers and Thought, Feigenbaum, E. and J. Feldman (Eds.),
Slagle, J. (1963b)
"Game Trees, M & N Minimaxing, and the M & N Alpha-Beta Procedure,'

Artificial Intelligence Group Report No. 3, UCRL-4671 , University of
Calif. Lawrence Radiation Laboratory, Livermore, Calif. N0v., 1963.
Slagle, J. (1965)
"Experiments with a Deductive-Question Answering Program," Commune at ions of
the ACM, Vol. 8, pp. 792-798, Dec 1965.
Slagle, J. (1967)
"Automatic Theorem-Proving with Renamable and Semantic Resolution,"

J. of ACM, Vol. 14, No. 4, pp. 687-697, Oct., 1967.
Slagle, J. (1970)
"Heuristic Search Programs," in Formal Systems and Non-Numerical

Problem Solving by Computer, M. Mesarovic and R. Banerji (Eds.)

"Experiments with a Multipurpose, Theorem- Proving Heuristic Program,
1188
"Experiments with Some Programs that Search Game Trees," J. of ACM
Vol. 16, No. 2, April 1969, pp. 189-207.
Slagle, J. and J. Dixon, (1970,)

"Experiments with the M & N Tree Searching Program," to appear.
Solomonoff, R. (1966).
"Some Recent Work in Artificial Intelligence ," Proc . lEEE , Vol. 54,
No. 112, Dec. ,
1966.
Travis, L. (1963)
"The Value of Introspection to the Designer of Mechanical Problem-

Solvers," Behav. Science, Vol. 8, No. 3, pp. 227-233, July 1963.
Travis, L. (1967)
"Psychology and Bionics: Many old Problems and a Few New Machines, "
Conference Record 1967 Winter Convention on Aerospace and Electronic
Systems (WINCON) , Vol, VI, Feb. 1967, lEEE Publication No. 10-C-42.
Turing A. M. (1950)
vComputing Machinery
and Intelligence," Mind , Oct. 1950, Vol. 59, pp
433-460. Reprinted in Computers and Thought, E. Feigenbaum and J.
Feldman (Eds.) McGraw-Hill Book Co., New York, 1963, pp. 11-35.
Waldinger, R. and R. Lee (1969)

"PROW: A Step Toward Automatic Program-Writing, " Proceedings of
Int'l Joint Conference on Artificial Intelligence, Wash. D.C. ,
May, 1969.
1189
Whitney, D. (1969)
"State Space Models of Remote Manipulation Tasks," in Proc of the

Int'l Joint Conf. on Artificial Intelligence, pp. 495-507.
Wos, L. D. Carson, and G. Robinson (1964)
"The Unit Preference Strategy in Theorem Proving," Proc of the AFIPS

1964 Fall Joint Computer Conf. ,
Vol. 26, pp. 616-621, 1964.
Wos, L., G. Robinson, and D. Carson (1965)
"Efficiency and Completeness of the Set of Support Strategy in Theorem-

Proving," JACM, Vol. 12, No. 4, pp. 536-541, Oct., 1965.
Yates, R., B. Raphael, and T. Hart (1970)
Stanford Research Institute Artificial Intelligence

"Resolution Graphs,"
Memo.
Zobrist, A. (1969)
"A Model of Visual Organization for the Game of Go," in Proc. AFIPS
Spring Joint Computer Conf. ,
pp. 103- 112, 1969.
-R22-

XW 061 VQ 8842

Uploaded by

Copyright:

Available Formats

XW 061 VQ 8842

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

XW 061 VQ 8842

Uploaded by

Copyright:

Available Formats

SR

(Preliminary Draft, ® 1969 Nils J. Nilsson)

Bibliographical and reference sections of Chapters I thru VIII,

D. Bibliographical and Historical Remarks

1. The "intelligence" of Computers

man is a machine. Turing (1950) delightfully shatters many of the standard

arguments against intelligent machines. To decide whether or not a

machine is intelligent, he proposes what has come to be called the Turing

problems in creating intelligent machines after agreeing that there are

no known theoretical barriers. Hubert Dreyfus (1965) thinks that digital

computers are inherently incapable of such "necessities" of intelligence as

"fringe consciousness" and "perspicuous grouping." His arguments are

systematically refuted by Papert (1968).

2. Overviews of Artificial Intelligence

Attempts to "organize" the field of Artificial Intelligence have

never been wholly successful. The subtopics of Search, Pattern Recognition,

in an important survey article. This breakdown is still useful even though

its logical validity is challenged by the plethora of statements in the

More recently Minsky

(1968) has written another thoughtful article on the foundations of Artificial

Intelligence and concludes that a major problem is that of acquiring, maintain

ing and accessing a large knowledge base

In attempting to build intelligent machines one naturally asks

"what is the secret of animal intelligence?" People have had a variety

Rosenblatt (1962) suggested brain models called perceptrons; these were

networks of "artificial neurons" based on the neuron models of McCulloch

and Pitts (1943) . The study of perceptrons stimulated early pattern-

recognition research and led to some elegant mathematical results on

computational geometry by Minsky and Papert (1969). The complex processes

to simulate evolution itself. Since evolution produced intelligent man

in two billion years or so, let us simulate the processes of evolution

at high speed in the computer. Fogel et al (1966) describe experiments

involving the production of many generations of finite state machines

using the strategies of mutation and selective survival. Although this

technique may be capable of condensing the first few million years of

evolution to a few days of computer time, it seems that the important

middle and later stages of evolution involve structures already so complex

(though not yet "intelligent") that their evolution cannot be speeded up by

computer simulation. Thus the "artificial evolution" approach did not

succeed in producing adequately complex machines either.

Another way to learn about intelligence from animals is to study their

behavior, particularly the problem-solving behavior of man. Travis (1963,

1967) discusses the role of introspection in the design of problem-solvers.

supposed to attack problems in much the same way that humans do

A rich source of ideas about how humans attack problems is found in

around 300 A.D., gave an excellent description of the Problem-reduction

till we reach a point that we can use as a starting point in synthesis.

For in analysis we assume what is required to be done as already done

(what is sought as already found, what we have to prove as true). We

we inquire again what could be the antecedent of that antecedent, and so

on, until passing from antecedent to antecedent, we come eventually upon

something already known or admittedly true. This procedure we call analysis,

or solution backwards, or regressive reasoning.

Campbell (1960) calls the unguided search process a blind-variation-and

selective-survival process. He concludes:

1. A blind-variation-and-selective-survival process is fundamental

to all inductive achievements, to all genuine increases in

knowledge, to all increases in fit of system to environment.

* From page 142 of Polya (1957)