195907 195907

User Manual: 195907

Open the PDF directly: View PDF PDF.
Page Count: 36

Open PDF In BrowserView PDF



International Conference
on Information Processing,
- the Opening

A General Problem-Solving
Program for a

The Application of
a Computer
to Bank



VOL. 8





Do computers
really pay?
47 users in the civil engineering field
alone, are proving that the Bendix G-15
more than pays its way.
The repeated computations encountered by civil engineers
in the design of highways, bridges, dams and other public
works, are tedious at best. With electronic computation the
engineers are relieved of such uncreative work because the
computer performs repetitive arithmetic automatically at
high speed.
In time savings alone, the Bendix G-15 is a profitable tool.
But add to that the value of the extra productive hours
available to each engineer and the fact that the computer
eliminates compromise solutions by finding the best answer
through many "trial and error" solutions at tremendous speed
- you can begin to see the important hidden profits of electronic computing.
Many problems are being solved today on the Bendix G-15
that have never been solved before, because of the many
man-years of math that manual methods would require.
Profits here are so great that it is difficult to even measure
them. Then there is the increased accuracy of electronic
computing, with the resulting reduction of checking time.
The benefits are so many and varied that it is difficult to
express them in dollars and cents. But consider the proof that
47 Bendix G-15s are being used in the civil engineering field
alone. And in other fields - electronics, optics, tools, missiles, navigation, illumination, and even animal husbandry,
the G-15 is making itself known as the computer that pays
big profits in many ways. Full details are available on request.



Alfred Benesch and Associates
Barber-Colman Company
Bonneville Power Administration
Bucyrus-Erie Company
Butler Manufacturing Company
Clark, Daily and Dietz
Consoer, Townsend and Associates
Cook County Highway Department
Crawford, Murphy & Tilly
De Leuw Cather and Company
Edwards and Kelcey, Engineers & Consultants
Ellerbe and Company
Emmet J. McDonald Associates
Harley, Ellington & Day, Inc.
Highway Research Board, AASHO, Road Test
H. W. Lochner, Incorporated
Homer L. Chastain & Associates
Hurst-Rosche, Incorporated
Illinois Division of Highways
]. E. Greiner Company
J. Stephen Watkins, Consulting Engineers
Jenkins, Merchant & Nankivil
John F. Meissner Engineers, Incorporated
Lockwood, Kessler & Bartlett, Inc.
Michigan State Highway Department
Palmer and Baker Engineers, Inc.
Parsons, Brinckerhoff, Hall and Macdonald
Portland Cement Association
Reynolds, Smith & Hills
Richardson, Gordon and Associates
Rochester and Goodell Engineers, Inc.
Stanley Engineering Company
Tudor Engineering Company
U. S. Army Corps of Engineers
Vogt, Ivers, Seaman Associates
Warren & Van Praag, Incorporated
Wilson and Company, Engineers & Architects
Wyoming Department of Highways









Volume 8
Number 7









September 1951

Assistant Editor
Assistant Editor

MUrray Hill 2-4194
New York 17, N.Y.








.1, 6

Nuvistor Tube (RCA) Undergoing Shock Test.


535 Fifth Ave.



JULY, 1959







International Conference on Information Processing the Opening, HOWARD H. AIKEN, R. MAHEU, A.
A General Problem-Solving Program for a Computer,


The Application of a Computer to Bank Accounting,









Middle Atlantic States
535 Fifth Ave.
New York 17, N.Y.
MUrray Hill 2-4194
TVashington 6, D.C.
COlumbia 5-9727
1519 Connecticut Ave.
San Francisco 5
YUkon 2-3954
605 Market St.
Los Angeles 5
DUnkirk 7-8135
439 S. Western Ave.
Berkeley Enterprises, Inc.
815 Washington St., Newtonville 60, Mass.
DEcatur 2-5453 or 2-3928

COMPUTERS and AUTOMATION is published monthly
at 815 Washington St., Newtonville 60, Mass., by Berkeley
Enterprises, Inc. Printed in U.S.A.
SUBSCRIPTION RATES: (United States) $5.50 for 1
year, $10.50 for 2 years; (Canada) $6.00 for 1 year, $11.50
for 2 years; (Foreign) $6.50 for 1 year, $12.50 for 2 years.
Address all Editorial and Subscription Mail to Berkeley
Enterprises, Inc., 815 Washington St., Newtonville 60,
Office at Boston, Mass.
~OSTMASTER: Please send all Forms 3579 to Berkeley
Enterprises, Inc., 815 Washington St., Newtonville 60,
Copyri.ght © 1959, by Berkeley Enterprises, Inc.
CHANGE OF ADDRESS: If your address changes, please
send us both your new address and your old address (as
it appears on the magazine address imprint), and allow
three weeks for the change to be made.

Report of "Progress

· 26

Red Tape Story





· 26

On Debugging A Computer, VV. T. GANT .


Computer or Man in Space?, S. DANISHEVSKY .
The Limits of Computer Power, EDMUND C. BERKELEY



Computer Art
Faithful Servant

. 28

Survey of Recent Articles, MOSES M. BERLIN

• 32




Advertising Index.
Back Copies
see June,
Bulk Subscriptions
. see June,
The Computer Directory & Buyer's Guide, 1959
see June,
. see June,
Who's VVho Entry Form
. see June,



page 91
page 87
page 95




i,: ~~~. ~";;~;~"";-'~';",~'";=:''' .":,~'



:",'~~~~-:-:~=~:=!~~'~~.',,:~~. "~~~~!,: ,~,~ l~;'~!



,' ,


Computer Programmers







IBM offers attractive career opportunities to versatile, imaginative
programmers who want to break new ground in the fast-growing
electronic computer field. You'll have unusual professional freedom
... work with specialists of diverse backgrounds ... have access to
a wealth of systems know-how. Whether you like to work independently or as a member of a small team, your contributions
and achievements will be quickly recognized.


l:f i



I. !
.~. ;i


t. :
!r ,1/


to specify and program elements of a sophisticated
automatic programming system.
Operational Programmer: to develop computer program techniques for real-time
military applications using game theory and systems simulation.
Senior Programmer: to analyze engineering problems and develop machine
programs for their solutions; to develop digital programs for simulating
bombing and navigational problems.
Programmer: to write differential equations of circuit diagrams; to develop
mathematical models of nuclear reactors; to investigate real-time control
systems using high-speed digital and/or analog computers.
Diagnostic Programmer: to prepare diagnostic programs for real-time computers
which will check for computer malfunction, diagnosing source of error for
Systems Programmer: to generate efficient and unique logical programs for realtime control computers; to develop automatic FORTRAN-like coding systems
for systems programs.


i 1

,e j







,- ~

~ ~ ~~
r '
~ ~:

to handle mathematical analysis and 704 programming to solve
systems problems, differential equations, probability-type problems, photogrammetry problems.
704 Programmer: to analyze, program and code problems such as system simulation; to solve ordinary differential equations and numerical approximation
of integrals.
Qualiflcations: B.S., M.S., Ph.D. in Mathematics or the Physical Sciences.
For details, write, outlining your background and interests, to:




Mr. R. E. Rodgers, Dept. 539-G
IBM Corporation
590 Madison Avenue
New York 22, New York



Readers' and
Editor's Forum
The front cover shows an electronic tube of a new
type called Nuvistor being tested in a special drop test
of guillotine-type. The tube operates normally while undergoing repeated blows with an impact equal to hundreds of
times its own weight, up to 850 times the force of
This type of tube is being developed by RCA Electron
Tube Division, and is expected to be mass-produced in
1960. In size, it fits inside a thimble. It contains no
mica or glass, but is made chiefly of steel, molybdenum,
tungsten, and ceramic. It operates between plus 660 degrees Fahrenheit and minus 320 degrees in liquid nitrogen. The joints in the complete tube are processed
at white heat, 2000 degrees F., in a brazing furnace and
then in a vacuum exhaust furnace. It is constructed
using cylindrical shapes and cantilever supports, to resist vibration and shock. It requires much less power
than previous tubes.
It will be used in high speed data processors and television sets, and for many other commercial, entertainment, and military purposes. The name comes from
"nueva" meaning "new" and "vista" meaning "look."
W. T. Gant
Shell Oil Co.
Midland, Texas

I have a comment concerning the article by C. R.
Blair "On Economical Debugging" in the May 1959 issue of Computers and Automation. Mr. Blair suggests
an efficient console that will waste less computer time
than many waste today. This is certainly a step in the
right direction but why stop short here? Why not develop debugging aids that will also include anything
practical that one can do at a console? Some installations
aren't far from such sophistication today. With this
approach one not only increases the efficiency but also
saves the expense of the extra hardware of the console.
I for one will be glad when the computer manufacturer leaves the console off completely except for maintenance. In fact, I wonder if, in time, a console will
really be justified there.
I. From S. Danishevsky
Harvard Univ.
Cambridge 38, Mass.

When one thinks of a computer, he envisions a massive, room-filling structure, with numerous cabinets,
storages, and printers.
It is interesting if disconcerting to note then, th3;(! in a
recent article in "Time," Dr. James Van Allen is qQoted
as having said "Man is a fabulous nuisance in space,
right now." Dr,. Van Allen 1?0es on to point out that

instruments are lighter, less demanding, and are also
sensitive to many things a person's senses ignore.
Either man is considerably larger than he thinks he
is, or the computer smaller.
II. From the Editor
There exist very powerful automatic digital computers which occupy only a small space, particularly those
constructed for airborne applications. In the future
computers will be smaller still.
It really will be easier to send instruments with computer "brains" to explore space and report, than to send
men. For example, it would be relatively easy to send
a computer through the recently discovered belt of strong
radiation around the earth. A man would need heavy
shielding. Also, it would make little difference if the
computer could not return. The man might not like to
be certain of no return.
Edmund C. Berkeley
N MAY 28 in the mail we received the printed text

of the 55 papers which were given at the InterO
national Conference on Information Processing m Paus
June 13 to 20. In the next few days we spent about
eight hours examining and reading them. Many of
these papers are fascinating for they deal with the present frontiers of the powers of computers - even if
some of the papers are comprehensible only to persons
with advanced mathematical knowledge.
Of these papers, we have at this time chosen three for
publication in whole or in part in Computers and Automation, one U.S.S.R., one British, and one U.S.A., because among many closely competing papers, these in
particular seem to contain both interesting ideas and
evidence of accomplishment, and seem to throw a bright
light into the future development of computers and the
directions in which they will be applied. These three
papers are:
"Machine Translation Methods and their Application
to Anglo-Russian Scheme" by I. K. Belskaya, Academy of Sciences of the U.S.S.R.
"Time Sharing in Large Fast Computers," by C. Strachey, National Research Development Corp., London
"Report on a General Problem-Solving Program" by
A. Newell and J. C. Shaw, the Rand Corp., and
H. A. Simon, Carnegie Inst. of Technology
Other Frontiers
Of course there are other frontier fields besides those
alluded to in the titles of the foregoing papers. One
more field is for a computer to deal not only with digits
and symbols, not only with words and their relations,
but with meanings. We quote from the paper "A Reduction Method for Non-Arithmetic Data and Its Ap[Please turn to page 29}

Here's how General Electric solves
typical DC power-supply problems
for computers and special applications


"We need to devote our engineering time
to designing our electronic circuitry.
not the power components. JJ

This is a frequent problem facing computer manufacturers. General Electric's Rectifier Department has
complete engineering and manufacturing capability
not only to design and apply all types of power supplies, but also to incorporate power supplies into
completely integrated systems.
These systems could include load distribution, supply sequencing, protection for power supply and load,
and complete power distribution. Let General Electric
tackle your DC power problems such as those associated with load IR drop, "cross talk," and other
nuisance-type problems plaguing your engineers.


i Q;1.);" #:'11


tilt's always a problem making
sure transistorized equipment is
safe from its power supply."

ti My power supply requirements
fluctuate so much . .. big jobs,
little jobs, all in between."

"We have a real low-voltage
power distribution problem with
our computer."




To alleviate this problem, General
Electric has developed several methods of making transistorized equipment safer in this respect. With G-E
protective circuits, shorting a plus
high-voltage bus to a plus or minus
low-voltage bus would not cause the
low-voltage bus to exceed a small
percentage of nominal rated value.
General Electric power supplies
protect completely transistorized
pieces of equipment from large losses
due to over-voltage failures.

G.E. has built individual power supplies and complete systems ranging
from less than one watt up to 35,000
kilowatts. These power supplies span
the complete range of DC powerregulated and unregulated-applying
all types of components. G-E experience includes completely transistorized supplies, and supplies with the
new controlled rectifier, magnetic
amplifiers, voltage stabilizing transformers, and motor-alternator "brute
force" systems.

Low-voltage distribution problems can be hans died easily through
load compensau
tion. Curve "A"
L::O-::"C""':'"AM'"'"'P=S--I--is net desired noload to full-load regulation at load
point. "B" is regulation at load without remote sensing or load compensation. "C" represents IR compensation
in power supply itself. "D" is amount
of IR or load compensation.

NO MATTER WHAT your computer and other
special power-supply problems are, General
Electric can help you economize-economize
by helping you free your engineers of these
problems. For more information on power-

~gress Is

supply products and services, contact your
nearest General Electric Apparatus Sales
Office or write to Section D535-2, General
Electric Company, Schenectady, New York.

Our Mosf /mpoliqnt P,()t/ue;f



100"'-"~_ _ _--J~


International Conference On
Information Processing
-The Opening
Paris, France, June 15 - 20, ,1959 -- June 15 Opening

The first session of the International Conference on
Information Processing took place in the historic central
lecture room of the Sorbo nne, of the University of Paris,
at 11 :00 a.m. on June 15. All the other sessions of the
conference took place in the beautiful and up-to-theminute building of the United Nations Educational
Scientific and Cultural Organization, at the Place de
Fontenoy, in Paris. (See the picture.) Registration at
the conference on the first day totaled over 1300.
The principal address at the opening was by Professor Howard H. Aiken, Harvard University, President
of the Conference. There were four other speakers:
- Mr. Rene Maheu, acting Director General, UNESCO;
- Mr. Andre Danjon, director of the Paris Observatory and President of the French Computing Association;
- Mr. Hugues Vinel, representative of the French
Minister of State in Charge of Scientific Research; and
- Prof. Pierre Auger, Secretary-General of the Conference.
Following are brief summaries of four of these addresses.

Howard H. Aiken - "With Opportunity and Power
Comes Responsibility for the Wise Use of Computer
First, I want to congratulate UNESCO and the small
group which has made the preparations for this conference. We all are greatly indebted to them.
A short review of past developm'ents in the computer
field will show the position we are now in, and the
reason why we are here, and will help us extrapolate to
the next decades.
The first two problems which the computer field
faced at the beginning were these: constructing a computing device which would work; and showing that we
could solve scientific problems set by other people. How
far behind are these problems now!
Now we see very great improvements. Among the
improvements are solid-state components, computers becoming smaller and faster, and an improved theory of
switching. This theory leads to the foundations of a
theory of systems.
The application of machine ideas is having great

effects in many different ways: on commercial enterprises; on the control of machinery; and in a great
variety of other fields - automatic translation of languages, the composition of music, the making of concordances, .....
The information-processing aspect of every segment
of human activity is becoming our interest.
No group attending any conference ever faced so
many challenging problems with so much chance of success and so great a potential influence on the lives of
people and society in general, as do the members of this
With opportunity and power comes responsibility responsibility for the wise application of computer ideas
for the public interest, for 'Thumanite entier."

R. Maheu -

ttThe Free Exchange of Ideas and

This is the second large-scale international scientific
conference organized by Unesco in Paris - the first,
held in 1957, covered the use of radio-isotopes in scientific research. In bringing scientists together at such
conferences Unesco is fulfilling its mandate "to encourage the unrestricted pursuit of objective truth and the
free exchange of ideas and knowledge," to quote the
words of its constitution.
It is impossible to-day to imagine a large factory, a
large government office, or a large research laboratory,
without a computation service in which a few of these
machines replace a large number of specialized computing staff.
One cannot even say that these machines take the
place of men, because in fact they enable the performance of operations which would be practically impossible because of the number of man hours they would require.
Thus man's intellectual power has been increased in an
extraordinary manner by placing at his disposal inexhaustible memories and automatic calculation organs
capable of ultra-rapid consultation, which can perform in
a few seconds what once required weeks to accomplish.

A. Danjon - ttprograms That Used to Be Madness"
The invention of electronic mathematical computers,

Figure 1 - The UNESCO Building in Place de Fontenoy, Paris.

going back only fifteen years, deserves to be considered
a landmark in the history of science in the same way as
the invention of lenses or the microscope.
The ambitious program of the International Geophysical Year would have been pure madness if we had not
been certain of being able to analyze very rapidly all
the data gathered from the entire surface of the earth.
The use of electronics has given a big impulse to astronomy, geodesy, geophysics (all traditionally big consumers of numbers), atomic physics, crystallography,
genetics, biometry, and the social sciences, by opening
hitherto-closed fields to their research workers.
An electronic computer would have made it easier for
the French astronomer Le Verrier to have discovered
Neptune in 1845. It would have also helped him in his
studies of the irregularities in the long-term movement
of the perihelion of Mercury's orbit; but it would not
have made it unnecessary for Einstein to conceive the
theory of relativity, no more than a machine perfectly
aware of all theories in classical physics would have made
it unnecessary for Becquerel to discover radioactivity.

Computer Art

COMPUTERS al1d AUTOMATION for July. 1959

H. Vine! -

"A Choice of Various Solutions"

Paris has become for a few days the meeting ground
of the world's most eminent mathematicians, in additiqn
to being the site of Unesco's permanent headquarters.
This conference should not only determine the logical
structures of machines but, perhaps, it should also
achieve a realization of their limits.
These machines have already served mankind, occasionally in military research, but also and above all in
seeking the scientific knowledge which will be able to
create our welfare of tomorrow.
The present-day complexity of science and technology
requires a choice of various solutions. Only with electronic processing can this be done within acceptable
time-limits. To take some recent examples from our
own country, this was how calculations were produced
for the remarkable aircraft, the Caravelle; and this was
how the plan for developing natural gas resources at
Lacq was worked out.

This design symbolizes the enormous storage capacity
of magnetic tape to store information. Its motif expresses:
from the computer field - magnetic tape and magnetic
tape reels, which may contain over 2400 feet of tape
and over 100 million binary digits of information; from
analytic geometry - asymptotic curves pointing to inthe mathematical expression
finity; from calculus meaning "the limit of the sum approaches"; and from
mathematical logic - the Hebrew character aleph with
a zero subscript (aleph naught), which was the sign
used by Georg Cantor to designate the first transfinite
cardinal number, the infinity of the class of natural
numbers 1, 2, 3, 4, .... , which is also the infinity of all
even numbers, of all rational fractions, and of a variety
of other classes.

A. Newell and

.T. C. Shaw. Th~ RAND Corporation. and H. A. Simon, Carnegie
Institute of Technology

(Paper given at the International Conference on Information Processing, Paris, France,
June 13-20, 1959)

This paper deals with the theory of problem solving.
It describes a program for a digital computer, called
General Problem Solver I (GPS), which is part of an
investigation into the extremely complex processes that
are involved in intelligent, adaptive, and creative behavior. Our principal means of investigation is synthesis: programming large digital computers to exhibit
intelligent behavior, studying the structure of these
computer programs, and examining the problem-solving
and other adaptive behaviors that the programs produce.
A problem exists whenever a problem solver desires
some outcome or state of affairs that he does not immediately know how to attain. Imperfect knowledge
about how to proceed is at the core of the genuinely
problematic. Of course, some initial information is always available. A genuine problem-solving process involves the repeated use of available information to initiate exploration, which discloses, in turn, more information until a way to attain the solution is finally discovered.
Many kinds of information can aid in solving problems: information may suggest the order in which possible solutions should be examined; it may rule out a
whole class of solutions previously thought possible; it
may provide a cheap test to distinguish likely from unlikely possibilities; and so on. All these kinds of information are heuristics things that aid discovery.
Heuristics seldom provide infallible guidance; they give
practical knowledge, possessing only empirical validity.
Often they "work," but the results are variable and
success is seldom guaranteed.
The theory of problem solving is concerned with discovering and understanding systems of heuristics. What
kind~ are there? How do very general injunctions ("Draw
a figure" or "Simplify") exert their effects? What
heuristics do humans actually use? How are new heuristics discovered? And so on. GPS, the program described
in this paper, contributes to the theory of problem solving by embodying two very general systems of heuristics - means-ends analysis and planning - within an
organization that allows them to be applied to varying
subject matters.
GPS grew out of an earlier computer program, the
Logic Theorist (5, 8), which discovered proofs to theorems in the sentential calculus of Whitehead and Russell.

It exhibited considerable problem-solving ability. Its
heuristics were largely based on the introspections of
its designers, and were closely tied to the subject matter
of symbolic logic.
The effectiveness of the Logic Theorist led to revised
programs aimed at simulating in detail the problemsolving behavior of human subjects in the psychological
laboratory. The human data were obtained by asking
college sophomores to solve problems in symbolic logic,
"thinking aloud" as much as possible while they worked.
GPS is the program we constructed to describe as closely as possible the behavior of the laboratory subjects as
revealed in their oral comments and in the steps they
wrote down in working the problems. How far it is
successful in simulating the subjects' behavior - its
usefulness as a phychological theory of human thinking
- will be reported elsewhere (7).
We shall first describe the overall structure of GPS,
and the kinds of problems it can tackle. Then we shall
describe two important systems of heuristics it employs.
The first is the heuristic of means-ends analysis, which
we shall illustrate with the tasks of proving theorems
in symbolic logic and proving simple trigonometric
identities. The second is the heuristic of constructing
general plans of solutions, which we shall illustrate,
again, with symbolic logic.
The Executive Program and the Task Environment
GPS operates on problems that can be formulated in
terms of objects and operators. An operator is something than can be applied to certain objects to produce
different objects (as a saw applied to logs produces
boards). The objects can be characterized by the features they possess, and by the differences that can be observed between pairs of objects. Operators may be restricted to apply to only certain kinds of objects; and
ther'e may be operators that are applied to several objects as inputs, producing one or more objects as output (as the operation of adding two numbers produces
a third number, their sum).
Various problems can be formulated in a task environment containing objects and operators: to find a
way to transform a given object into another; to find an
object possessing a given feature; to modify an object so
that a given operator may be applied to it; and so on. In

chess, for example, if we take chess positions as the objects and legal moves as the operators, then moves produce new positions (objects) from old. Not every move
can be made in every position. The problem in chess is
to get from a given object - the current position - to
an object having a specified feature ( a position in which
the opponent's King is checkmated).
The problem of proving therems in a formal mathematical system is readily put in the same form. Here the
objects are theorems, while the operators are the admissible rules of inference. To prove a theorem is to transform some initial objects - the axioms - into a specified object - the desired theorem. Similarly, in integrating functions in closed form, the objects are the mathematical expressions; the operators are the operations of
algebra, together with formulas that define special functions like sine and cosine. Integration in closed form is
an operation that does not apply directly to every object - if it did, there would be no problem. Integration
involves transforming a given object into an equivalent
object that is integrable, where equivalence is defined
by the set of operations that can be applied.
Consructing a computer program can also be described
as a problem in these same terms. Here, the objects
are possible contents of the computer memory; the operators are computer instructions that alter the memory
content. A program is a sequence of operators that
transforms one state of memory into another; the programming problem is to find such a sequence when certain features of the initial and terminal states are specified.
To operate generally within a task environment
characterized by objects and operators, GPS needs several main components:
1. A vocabulary, for talking about the task environment, containing terms like: object, operator, difference, feature, Object #34, Operator #7.
2. A vocabulary, dealing with the organization of
the problem-solving processes, containing terms
like: goal type, method, evaluation, Goal Type
#2, Method #1, Goal #14.
3. A set of programs defining the terms of the problem-solving vocabulary by terms in the vocabulary
for describing the task environment. (We shall
provide a number of examples presently.)
4. A set of programs (correlative definitions) applying the terms of the task-environment vocabulary
to a particular environment: symbolic logic, trigonometry, algebra, integral calculus. (These will
also be illustrated in some detail.)
Items 2 and 3 of the above list, together with the
common nouns, but not the proper nouns, of item 1
constitute GPS, properly speaking. Item 4 and the
proper nouns of item 1 are required to give GPS the
capacity to solve problems relating to a specified subject matter. Speaking broadly, the core of GPS consists of some general, but fairly powerful, problem-solving heuristics. To apply these heuristics to a particular
problem domain, GPS must be augmented by the definitions and rules of mathematics or logic that describe that
domain, and then must be given a problem or series of
. problems to solve. The justification for calling GPS
"general" lies in this factorization of p~oblem-solving
heuristics from subject matter, and its ability to use the
same heuristics to deal with different subjects.

Fig. 1 -

Executive organization of GPS
Command to
achieve goal

Evaluate goal


Do not
try to



Select method
for this type goal

Execute method

Goal achieved

Let us look more closely at the problem-solving vocabulary and heuristics. To specify problems and subproblems, GPS has a discrete set of goal types. We shall
introduce two of these initially:
Goal Type #1: Find a way to transform object a into
object b. (The objects, a and b, may be any objects defined in specifying the task environment.
The phrase "way to transform" implies "by applying a sequence of operators from the task environment." )
Goal Type #2: Apply operator q to object a (or to an
object obtained from a by admissible transformations).
Finding a proof of a theorem (object b) from axioms
(object a) is an example of a Type #1 goal; integrating
(operator q) an expression (object a) is an example of a
Type #2 goal.
The executive organization of GPS, shown in Figure 1,
is very simple. With each goal type is associated a set of
methods related to achieving goals of that type. When an
attempt is made to achieve a goal, it is first evaluated to
see whether it is worthwhile achieving and whether achievement seems likely. If so, one of the methods is selected
and executed. This either leads to success or to a repetition of the loop.
The principal heuristics of GPS are imbedded in the
methods. All the heuristics apply the following general
The principle of sub goal reduction: Make progress by
substituting for the achievem.ent of a goal the
achievement of a set of easier goals.
. Thi.s is, i~deed? only a heuristic principle, and it is not
'as: self-evident as it may appear. For example, none of
-the programs so far written for chess or checkers makes es~ential use of the principle (1, 3, 6).
The' constant use of this principle makes GPS a highly

recursive program, for the attempt to achieve one goal
leads to other goals, and these, in turn, to still other goals.
Thus, identical goal types and methods are used many
times simultaneously at various levels in the goal structure in solving a single problem. Application of the principle also combines the goals and methods into organized
systems of heuristics, rather than establishing each method
as an independent heuristic. We shall provide examples
of two such systems in this paper.
Functional or Means-ends Analysis
Means-ends analysis, one of the most frequently used
problem-solving heuristics, is typified by the following
kind of common sense argument:
I want to take my son to nursery school. What's the
difference between what I have and what I want? One
of distance. What changes distance? My automobile.
My automobile won't work. What's needed to make
it work? A new battery. What has new batteries?
An auto repair shop. I want the repair shop to put
in a new battery; but the shop doesn't know I need
one. What is the difficulty? One of communication.
What allows communications? A telephone ... And
so on.
This kind of analysis - classifying things in terms of
the functions they serve, and oscillating among ends, functions required, and means that perform them - forms
the basic system of heuristic of GPS. More precisely, this
means-ends system of heuristic assumes the following:
1. If an object is given that is not the desired one, differences will be detectable between the available object and the desired object.
2. Operators affect some features of their operands and
leave others unchanged. Hence operators can be
characterized by the changes they produce and can
be used to try to eliminate differences between the
objects to which they are applied and desired objects.
3. Some differences will prove more difficult to affect
than others. It is profitable, therefore, to try to
eliminate "difficult" differences, even at the cost of
introducing new differences of lesser difficulty. This
process can be repeated as long as progress is being
made toward eliminating the more difficult differences.
To incorporate this heuristic in GPS, we expand the vocabulary of goal types to include:
Goal Type #3: Reduce the difference, d, between object a and object b by modifying a.
The core of the system of functional analysis is given by
three methods, one associated with each of the three goal
types, as shown in Figure 2. Method # 1, associated with
Goal Type #1, consists in: (a) matching the objects a
and b to find a difference, d, between them; (b) setting up
the Type # 3 subgoal of reducing d, which if successful
produces a new transformed object c,' (c) setting up the
Type # 1 subgoal of transforming c into b. If this last
.goal is achieved, the original Type # 1 goal is achieved.
The'match in step (a) tests for the more important differences first. It also automatically makes substitutions tor
free variables.
- " Method #2, for achieving a Type #2 goal, consists in:
(a) determining if the operator can be applied by setting up a Type # 1 goal for transforming a into C (q), the
,input form of q; (b) if successful, the output object is

produced from P ( q), the output form of q. This method is
appropriate where the operator is given by two forms, one
describing the input, or conditions, and the other the output, or product. The examples given in this paper have
operators of this kind. Variants of this method exist for
an operator given by a program, defined iteratively, or defined recursively.
Method # 3, for achieving a Type # 3 goal, consistsin: ( a) searching for an operator that is relevant to reducing the difference, d; (b) if one is found, setting up
the Type #2 goal of applying the operator, which if
successful produces the modified object.
Application to Symbolic Logic. This system of heuristics already gives GPS some problem-solving ability. We
can apply GPS to a simple problem in symbolic logic. To
do so we must provide correlative definitions for objects,
operators, and differences. These are summarized in Figure
3. We must also associate with each difference the operators that are relevant to modifying it. For logic this is
accomplished explicitly by the table of connections in
Figure 3. These connections are given to GPS, but it is
not difficult to write a program that will permit GPS itself to infer the connections from the lists of operators
and differences. (E.g., comparing the right side of RI
with its left side, we find they have the difference .6P,
for the symbols A and B appear in opposite orders on the
two sides; hence, there is a connection between .6P, and
R1.) Finally, we provide criteria of progress, in terms of
a list of the differences in order of difficulty.
An illustrative logic problem and its solution are shown
in Figure 4. The object, LI, is given, and GPS is required to derive the object, LO. The problem is stated to
GPS in the form of a Type #1 goal; (Goal 1) Find a

Fig. 2 -


Methods for means-ends analysis.

Goal type #1: Transform object a into ob'ect b



ifference d ~



~ ..a 1







object ~
succeeds ....-S-u-c-ce-e-d--I ~

Fail, try for new

.8 ..a



Goal type.#2: Apply operator 9. to object
Method #2:
.Method ~

Transform ~
into c(g), the
mput form of






__ Produce the output
Succeeds £. from P(q) the
output form of 9.. _


Method succeeds
Goal type #3: Reduce the difference, £, between object ~
an~ object Q.
Method #3:




Figure 3
Figure 3a. Symbolic ;Logic Task Environment, Part I.
Objects. Expressions are built up recursively from variables,
P, Q, R, ...., three binary connectives, ., ~, v, and the
unary prefix, - , called tilde. Examples of objects: P,
-Q, PvQ, (-R.P) ~ -Q. Double Tildes cancel as in
ordinary algebra: - -Q =Q.
Operators. There are twelve operators, given in the form
C(q) ~ P(q), where C(q) is the input form, and P(q)
is the output form. Thus anything of the form at the tail
of an arrow can be transformed into the corresponding
expression at the head of the arrow. A double arrow means
the transformation works both ways. The abstracted operators, used in the planning method, are given in the righthand column opposite the operator.






Abstract Operators

BvA, A.B


A ~ B ~ -B ~ -A
AvA ~ A,A.A ~ A
(AA) ~ A
- Av(BvC) ~ (AvB)vC, A. (B.C) ~
A(BC) ~ (AB)C
AvB ~ -(-A.-B)
A ~ B ~-AvB
Av(B.C) ~ (AvB) (AvC), A.(BvC) ~
A(BC) ~ (AB) (AC)
A.B ~ A, A.B ~ _B
(AB) ~ A
A ~ AvX
(X is an expression.)




RIO [A, B] ~ A.B ' (Two expressions input.)
[A, B] ~ (AB)
Rl1 [A ~ B, A] ~ B (Two expressions input.)
[(AB), A] ~ B
R12 [A ~ B, B ~ C] ~ A~ C (Two expressions
[(AB), (BC)] ~ (Ae)
Differences. The ,differences apply to subexpressions as
well as total expressions, and several differences may exist
simultaneously for the same expressions.
6. V A variable appears in one expression that does not
in the other. E.g., PvP differs by + V from PvQ,
since it needs a Q; P ~ R differs by -V from R,
since it needs to lose the P.
6N _A vaJiabl~ OCqIrs different numbers of times in the
two expressions. E.g., P.Q differs from (P.Q) ~
Q by +N, since it needs anoth-er Q; PvP differs
from P by -N, since it needs to reduce .the nu,mber of P's.
6. T There is a difference in the "sign" of the two expressions; e.g., Q versus -Q, or -(PvR) versus

There is a difference in binary connective;- e.g.,
P ~ Q versus PvQ.
"6.G There is a difference in grouping;' e.g., Pv'(QvR)
versus (PvQ) vR.
',CO~~U~ERS an.d

AUTOMATION for July, 1959

There is a posltlOn difference in the components
of the two expressions; e.g., P ~ (QvR) versus
(QvR) ~ P.
Figure 3b. Symbolic Logic Task Environment, 'Part II.
Ca1Z1zectiol1S between Differences and Operators. A
or x in a cell means that the operator in the column of
the cell affects the difference in the row of the cell. + in
the first row means + V) - means -V, etc. The stars
show the differences and operators that remain after abstracting, and thus mark the reduced table of connections
used in the abstract task environment for planning.


* *






RI R2 R3 R4 R5 R6 R7,RS R9 RIO_RI! Rl2
*6. V
x x
x x
6.P x x
Criteria of progress. All differences i~ sub expressions are
less important than differences in expressions. For a pair of
expressions the differences are ranked: + V, -V, +N,
:-N, 6. T, 6C, 6.G; 6.P, from most important to least.
E.g., '6. T is more important in -(PvQ) versus P ~ Q,
but 6. C is more important in -PvQ versUs 'P -~ Q.

+ +
+ +

way to transform Ll into LO. -By Figure 2; this goal type
calls for- Method # 1. Comparison of LL and· LO- shows
that they have the difference, .6P; for the "R"_ is on the
left end of Ll, but on the right end of.~LO~- -GPS now
erects the Type #3 goai; (Goaf2) Reduce 6.P,'between
Ll and LO. -Goal Type #3 calls for application of Method
#3.· Since, the table of connections '(Figure 3) shows that
Rl is relevant to reducing 6.P, GPS erects the· Type #2
goal: (Goal 3) Apply operator Rl to L1. 'The· reader
can follow the remaining -steps that lead to the s()lution
from Figure 4. The resulting derivation .may be sum.


Ll = R. (-P~Q)
12 = (-P~Q).R
Apply Rl to Ll, 1 '
L3 = (P v Q).R
Apply R6 to left side of L2
L4 . (Q v P).R
Apply Rl to left side of L3
Q. E. D.
L4 is identical with LO
GPS can 'solve problems a good deal more difficult 'than
the simple one illustrared. To make full use of the twelve
operators, an additional method is added to the Type #3
goal that searches the available objects for the additional
input required in rules RIO, R:ll, and R12.
; Application to ,Trigonometry. GPS is a general problem solver to the extent that its heuristics can be applied
to varying subject-matrers; given.'the- appropriate correlative
'. ':definitio-!IS: ~ Elementary algebra_ and .calcuhis~ provides a
. csupject' marter' aistinCt' from :logic, -and Figure ~S- 'shows' the
ffraginegt ~,ot :this task ;eirvironment.- !lecess~;:Y" for DPS- ·to
! try':ro prove 'some: simple trigonomerric~ identities. :'The r ob': (jeets are .flOW .algebraiC' ~tia trigonO'metric expressions; and
l..the 'operarors perfbrtnti.actodzat'ion,: l!lgebraic' simplificadon,
and trigonometric transformation. The differen~es ~
same ~ inM,IQgk; ~~(ept~Jor two {>missions,o which are related to -the -associative and coriUn{itative laws. In logic
Nlhese )"'rnusr :be' petformet{, explr&itlyrLl\Vh~telts in .or.dinary
I algebra' a nC?,tatipn is ,usedJ-tltat asn:kes7,"ml;sel,;1iw~ ~implkit



Figure 4. Example of means-ends analysis in logic.


Given: Ll
Obtain: LO
Goal 1: Transform Ll into LO.
Match produces position difference (6P).
Goal 2: Reduce 6P between Ll and LO.
First operator found is Rl.
Goal 3: Apply Rl to L1.
Goal 4: Transform Ll into C(Rl).
Match succeeds with A = R and B = -P :J Q.
Produce new object: ,
L2 = (-P:JQ).R
Goal 5: Transform L2 into LO.
Match produces connective difference (6 C) in left
Goal 6: Reduce 6C between left of L2 and left of LO."
First operator found is R5.
Goal 7: Apply R5 to left of L2.
GoalS: Transform left of L2 into C(R5).
Match produces connective difference (6 C) in left
Goal 9: Reduce 6 C between left of L2 and C (R5 ) .
Goal rejected: difference is no easier than difference
in Goal 6.
Second operator found is R6.
Goal 10: Apply R6 to left of 12.
Goal 11: Transform left of L2 into C(R6).
Match succeeds with A = -P and B = Q.
Produce new object:
L3 = (PvQ).R
Goal 12: Transform L3 into LO.
Match produces position difference (6P) in left
Goal 13: Reduce 6 P between left of L3 and left of
First operator found is Rl.
Goal 14: Apply R1 to left of L3.
Goal 15: Transform left of L3 into C(Rl).
Match succeeds with A
P and B
Produce new object:
L4 = (QvP).R
Goal 16: Transform 14 into LO.
Match shows L4 is identical with LO, QED.



and their operation automatic. The connections between
differences and operators is not made via a simple table, as
in logic, but requires a comparison of the object with the
output form of the operator. The criteria of progress remain the same as for logic.
GPS can now attempt to prove a trigonometric identity
(tan + cot) sin cos = 1
This is given as the problem of transforming the left
side, which becomes Ll, into the right side, LO. The process of solving the problem, which involves 33 goals and
subgoals, is shown in Figure 6, which is to.. be interpreted
. in exactly the same way as Figure 4, with the llelp of
Figures 2 and 5, except that the methods are not melltioned
, explicitly.
Planning as a Problem-Solving Tec~nique
The second system of heuristic used by GPS is a form 01
planning that allows GPS to COnstruct a proposed solution

in general terms before working out the details. It acts as
an antidote to the limitation of means-ends analysis in
seeing only one step ahead. It also provides an example of
the use of an auxiliary problem in a different task environment to aid in the solution of a problem. * Planning is incorporated in GPS by adding a new method, Method #4,
to the repertoire of the Type # 1 goal.
This Planning Method (see Figure 7) consists in (a)
abstracting by omitting certain details of the original objects and operators, (b) forming the corresponding problem in the abstract task environment, ( c) when the abstract problem has been solved, using its solution to pro-

Figure 5. Trigonometry task environment

Objects. Ordinary algebraic expressions, including the
trigonometric functions. The associative and commutative laws are implicit in the notation: the program can
select freely which terms to use in an expression like
Combine: recursively defined to apply the following elementary identities from the innermost subexpressions to the main expression:
(1) A + (B
C) ~ A+ B
C, A(BC) ~
(2) A
0 ~ A, A
A ~ 2A, A - A

+ +






(3) AO ~ 0, Al ~ A, AA ~ A2, AB AC ~
(4) AO ~ 1, OA ~ 0, At ~ A, (AB)C ~ ABC
(A - B) (A
B) ~ A2 - B2
B)2 ~ A2 + 2AB
A(B + C) ~ AB
tan x ~ l/cot x
(tan x) (cot x) ~ 1
tan x ~ sin x / cos x
cot x ~ cos x / sin x
cos2x ~ 1
Differences. Defined as in logic: 6 V, 6N, 6 C, 6 T,
and 6 G and 6 P do not occur in algebra, since associativity
and commutativity are built into the programs for handling expressions. The trigonometric functions are detected by 6 V and 6N.
Connections between Differences and Operators. A
- , or x in a cell means that the operator in the column
of the cell affects the difference in the row of the cell. A t
means that the test defined at the bottom is applied.
AO Al A2 A3 Tl T2 T3 T4 T5













Test t: accept if other functions in output form already
occur in expression.
Criteria of progress. Defined as in logic, but with 6C
more important than 6N or 6P.

* See the work of H. Gelernter and N. Rochester on theorem
proving programs for plane geometry (2), where the geometric
diagram provides an example of a very powerful auxiliary problemlem space.

Figure 6.

Example of means-ends analysis in


cot x) sin x cos x
Given: 11 = (tan x
Obtain: 10 = 1
Goal 1: Transform 11 into 10.
Goal 2: reduce -V between 11 and 10 (tan).
Goal 3: Apply AO (combine) to 10 [no change
Goal 4: Apply Tl to 11.
Goal 5: Transform 11 into C(Tl) [succeeds]
12 = [(l/cot x)
cot x] sin x cos x
Goal 6: Transform 12 into LO.
Goal 7: Reduce -V between 12 and 10 (cot).
Goal 8: Apply AO to 12 [no change produced].
Goal 9: Apply T4 to 12.
Goal 10: Transform 12 into C(T4) [succeeds].
13 = [( 1/ ( cos x/sin x»
cos x/sin x)] sin x
cos x
Goal 11: Transform 13 into 10.
Goal 12: Reduce -V between 13 and 10 (cos).
Goal 13: Apply AO to 13:
14 = [( sin x/cos x)
cos x/sin x)] sin x cos x
Goal 14: Transform 14 into 10.
Goal 15: Reduce -V between 14 and 10 (sin).
Goal 16: Apply AO to 14 [no change produced].
Goal 17: Apply T5 to 14.
Goal 18: Transform 14 into C(T5).
Goal 19: Reduce 6.C between 14 and C(T5) (. to


several smaller problems, the sum of whose lengths is about
equal to the length of the original problem, may reduce
the problem difficulty by whole orders of magnitude.
Figure 8 shows the Planning Method applied to a problem of symbolic logic. The particular abstraction scheme
that is illustrated ignores differences among connectives
and the order of symbols (6. C and 6.P), replacing, for
example, "(R:J-P) . (-R:JQ)" with "(PR) (QR)".
The operators are similarly abstracted, so that "AvB~BvA"
Fig. 7 - Planning Method
Goal type 11: Transform object!!. into object
Method #4:


Goal 20: Apply AO to 14 [no change produced].
Goal 21: Apply Al to 14.
Goal 22: Transform 14 into C(Al).
Goal 23: Reduce 6.C between 14 and C(Al) [reject] .
Goal 24: Apply A3 to 14.
Goal 25: Transform 14 into C(A3) [succeeds].
15 = [sin x/cos x]sin x cos x
[cos x/sin x]sin
x cos x
Goal 26: Transform 15 into C(T5).
Goal 27: Reduce 6. C between left of 15 and left of
Goal 28: Apply AO to left of 15:
16 = sin 2x
[cos x/sin x] sin x cos x
Goal 29: Transform 16 into C(T5).
Goal 30: Reduce 6. C between right of 16 and right
of C(T
Goal 31: Apply AO to right of 16:
17 = sin2x
Goal 32: Transform 17 into C(T5) [succeeds].
Goal 33: Transform 18 into 10 [identical], QED.




vide a plan for solving the original problem, (d) translating the plan back into the original task environment and
executing it. The power of the method rests on two facts.
First, the entire machinery of GPS can be used to solve the
abstract problem in its appropriate task environment; and,
because of the suppression of detail, this is usually a simpler
problem (having fewer steps) than the original one.
Second, the subproblems that make up the plan are collectively simpler (each having few steps) than the original
problem. Since the exploration required to solve a problem
generally increases exponentially with the number of steps
in the solution, replacement of a single large problem with
COMPUtERS and AUTOMATION for July, 1959

Method fails

Abstract a and b
objects, !!.',~'




Transform !!.' into
using abstract


Sequence of
abstract operators:

Method fails

Fail, try
for new plan

Specialize operators
Sequence of
Ql' q2' •••

Fail, try for new

Apply sequence of
operators to !!.
Final object, £.

Transform £. into

Fail, try for new
final object

Method succeeds

becomes "( AB ) ~ (AB ) "-i.e., the identity operator and "A.B~A" becomes "(AB)~A", as shown in Figure
3. The abstracted problem, Transform Al into AO, has
several solutions in the abstracted task environment. One
of these may be summarized:
Al (PR) (QR)
A2 (PR)
Apply R8 to get left side of At
A3 (QR)
Apply R8 to get right side of Al
Apply R12 to A2 and A3
But (PQ) is identical
Q. E. D.
with AO
Transforming Al into AO is the abstract equivalent of the
problem of transforming 11 into LO. The former is solved
by applying the abstracted operators corresponding to
R8, R8, and R12 in sequence. Hence (Figure 9, Goal 4)
a plan for solving the original problem is to try to apply
R8 to 11 (obtaining a new object whose abstract equivalent is (PR), applying R8 to the other side of 11 (obtaining an object corresponding to (QR) ), applying R12 to
the objects thus obtained, and finally, transforming this
new object (which should be an abstract equivalent of
LO) into 10. Each of the first three parts of this plan
constitutes a Type #2 goal in the original task environ15

'Figure 8. Example of planning in logic:
Given: L~ = (R::J-P). (-R::JQ)
Obtam: LO = - (-Q.P)
Goal 1: 'Transform Ll into LO [Method #1 fails; now
Method #= 4 is tried].
Abstract Ll and ]..0:
Al = (PR) (QR)
AO = (PQ)
Goal 2: Transform Al into Ao [using abstracted
operators] .
Several plans are generated [details are omitted]:
PI = RS, Rl1, R12.
P2 = RS, RS, R12.
P3= ...
Goal 3: Apply PI to Ll [fails, details are omitted].
Goal 4: Apply P2 to L1.
Goal 5: Apply R8 to L1.
Goal 6: Transform Ll into C(R8) [succeeds].
L2 = R::J-P
Goal 7: Apply RS to L1.
Goal S: Transform Ll into C(RS) [succeeds].
L3 = -R::JQ
Goal 9: Apply R12 to L2 and L3.

Goal 10: Transform L2 and L3 into C(RI2) [L2 fits
B::J C].
Goal 11: Reduce 6,P between L3 and C(RI2)
(A::J B with B = R).
Goal 12: Apply R2 to L3.
Goal 13: Transform L3 into C(R2) [succeeds].
L4 = -Q::JR
Goal 14: Transform L2 and L4 into C(RI2) [succeeds].
L5 = -Q::J-P
Goal 15: Transform L5 into LO.
Goal 16: Reduce 6, T between L5 and LO.
Goal 17: Apply R2 to L5 [fails, details omitted].
Goal 18: Apply R5 to L5.
Goal 19: Transform L5 into C (R5 ).
Goal 20: Reduce, 6, C between L5 and C (R5).
Goal 21: Apply R5 to L5 [reject].
Goal 22: Apply R6 to L5.
,Goal 23: Transform L5 into C(R6) [succeeds].
L6 = Qv-P
Goal 24: Transform L6 into C(R5) [succeeds].
L7 = -(-Q.P)

Source Exif Data:
File Type                       : PDF
File Type Extension             : pdf
MIME Type                       : application/pdf
PDF Version                     : 1.3
Linearized                      : No
XMP Toolkit                     : Adobe XMP Core 4.2.1-c041 52.342996, 2008/05/07-21:37:19
Create Date                     : 2015:08:25 15:28:08-08:00
Modify Date                     : 2015:08:25 14:46:08-07:00
Metadata Date                   : 2015:08:25 14:46:08-07:00
Producer                        : Adobe Acrobat 9.0 Paper Capture Plug-in
Format                          : application/pdf
Document ID                     : uuid:c670485f-2b6b-2c4d-8889-1afb331c2de2
Instance ID                     : uuid:14d3418b-3951-1d43-b268-2dcd3c609205
Page Layout                     : SinglePage
Page Mode                       : UseNone
Page Count                      : 36
EXIF Metadata provided by EXIF.tools

Navigation menu