Automated Theory Formation in Mathematics

1. INTRODUCTION

1.1. HISTORICAL MOTIVATION

Scientists often face the difficult task of formulating nontrivial research problems which are soluble. In most branches of science, it is usually easier to tackle a specific given problem than to propose interesting yet managable new questions to invesligille. For example, contrast solving the Missionaries and Cannib<1ls problem with the more ill-defined reasoning which led to i.nventi.ng it. The first type of activity is formaliz11ble 11nd 11dmits a deductive solution; the second is inductive and judgmental. As another example, contrast proving a given theorem versus proposing it in the first place.

A wealth of AI research has been focussed upon the former type of activity: · deductive problem solving (see, e.g., [Bledsoe 71 ], [Nilsson 71]. [Newell & Simon 72]). Approaches to inductive inference have al~o been made. Some researchers have tried to attack the problem in a completely domain-independent way (see, e.g., [Winston 70]). Other AI researchers believe that "expert knowledge" must be present if inductive reasoning is to be done 111 the level which humans are c11pab le of. Indeed, a few recent AI programs have incorporated such knowledge (in the form of judgmental rules gleaned from human experts) and succe!.sfully carried out quite complex inductive tasks: medical diagnosis [Shorl liffe 74], mass spectra identification [Feigenbaum 71], clinical dialogue [Davis 76), discovery of new mass spectroscopy rules [Buchanan 75).

The "next step" in this progression of tasks would be that

1 Thio work was supported in part by the Defense Advanced Research Projects A,ency (f411620-73-C-0074) and monitored by the Air Force Office of Scientific Research.

• required. As it runs, AM is monitored by a human "user". AM keeps the user informed by instantiating Engli sh sentence temp l<1t es. The user's input is rare <Jnd can be success full y stereotyped.
• Formal reasoning (including proof) is not indispensable when doing theory formation in elementary mathematics. In the same spi rit, we need not worry in advance about the occurence of contradictions.
• Each mathematical concept can be rep1·esented as a li~;t of facets (aspe.cts, slots, ports, property/value pairs). For each new piece of knowledge gained, there will be no trouble in finding which facet of which concept it should be storf?d in.
• The basic activity is to choose some facet of some concep t, and then try to fill in new entries to store there; this will occasionally cause new concept s to be defined. The high-level decision about which facet of which concept to work on next can be handled by maintaining an "ordered agenda." of such tasks. The techniques for actually carrying out a task are cont ained within a large col lec tion of heuristics.
• Each heuristic has a well--defined domain of applicabi lity, which coincides perfectly with one of AM's concepts. We say the heuristic "belongs to" that concept.
• Heuristics superimpose; they never interact strongly with each other. If one concept Cl is a specialization of concept C2, then C I 's heuristics are more powerful and should be tri ed fir~;!.
• The reasons supporting a task (on the agenda of facet/concept tasks to be carried out) superimpose perfectly. They never ch<1t1ge wi th time, and it makes no difference in what order they were noticed. It suffices to have a single, positive number which characterizes the value of the reason.
• The tasks on the agenda are comple tely independent. No t as~. "wakes up" another. Only the general position (nf'ar the top, near the bottom) is of any significance.
• The set of heuristics need not grow, as new concept s are discovered. All common-sense ~.nowledge required is assumed to be alr f'ady present within the initially-given body of heuristic rules.

It is worth repeating that all the above points arc merely convenient falsehoods. Their combined presence made AM doable (by one person, in one year).

One point of agreeement between Weizenbaum and Lederbe1·g [Lederberg 76) is that AI can succeed in automating only those activities for which there exist s a "strong theory" of how that activity is done by people. Point tt4 above is a claim that such a clean, simple model exis ts for math resea1·ch: a sea1·ch process governed by a large collection of heuristic rules. Here is a simplified summary of that model:

1. The order in which a math textbook presents a theory is almost the exact opposite of the order in whch it was actually developed. In a text, definitions and lemrnat a are given with no motivation, and they turn out to be just the ones required for the next big theorem, whose proof magically follows. But in real life, a mathematician would begin by examining some already-known concep ts, trying to find some regularity involving them, formulating those as conjectures to investigate further, and using them to motivate some simplifying new definitions.
2. Each step the researcher t a~.es (see It I) involves choosing from a huge set of alternatives -- that is, searching. He uses judgmental criteria (heuristics) to choose the "best" alternative. This saves his search from the combinatorial explosion.
3. Non-formal criteria (aesthetic interestingness,
4. empirical induction, analogy, utility estimates) are much more impodant lhan formal methods.
5. All such heuristics can be viewed as si tuation/action (IF /THEN) rules. There is a common core of (a few hundred) heuristics, basic to all fields of milth at all levels. In addition to these, each field has several specific, powerful rules.
6. Nature is metaphysically pleasant: It is fair, uniform, regular. Statistical considera tions are valid and valuable when trying to find regularity in math data. Simplicity and syne1·gy and symmetr y abound.

2. DESIGN OF THE ~AM' PROGRAM

A pure production system may be considered to consist of th1·ee components: data memory, a set of rules, and an interpreter. Since AM is more or less a rule-based system, it too can be considered as havinp, three main design components: how it represents math knowledge (its frame­ like concept /facets scheme), how it enlare,es its knowledge base (its collection of heuristic rules), and how it controls the firing of these rules (via the agenda mechanism). These form the sub jects of the following three subsections.

The task of the AM program is to define plausible new mathematical concepts, and investigate them. Each concept is represented internally as a bundle of slots or "facets". Each f ace t corresponds to some aspect of a concept, to some question we might want to ask about the concept. Since each concept is a mathematical entity, the kinds of questions one might ask are fairly constant from concept to concept . A set of 25 facets was therefore fixed once and for aiL Below is that list of facets which a concept C may have. For each facet, we give a typical question about C which it answers.

Name: What shall we cal l C when talking with the user? Generalizations: Which other concepts have less restrictive (i.e., weaker) definitions than C?

Speciali za tions: Which concepts sa ti sfy C's definition plus

some additional constraints'! Examples: What things that sati sfy C's definition? Isa's: Which concepts' definitions does C itself satisfy? In-domain-of: Whi ch operations can operate on C's? In-range-of: Which ope1·ations result inc·~. when run? Views: How can we view some X as if it were a C?

Intuit ions: What abstract, analogi c representations are known for C'!

Analogies: Are there any simi lar concepts?

Conjec's: What are some potential theorems involving C?

Definitions.: How can we tell if x is an example of C?

Algorithms: What exactly do we do if we want to execute the operation Con a given argument'!

Domain/Range: What kinds of arguments can operation C be executed on? What kinds of va lues will it return? Worth : How valuab le is C? (overall, aesthetic, utility, etc.) Interestingness: What special features can make a C especially interesting'! Especially boring?

In addition, each facet F of concept C can possess a few little subf acet s which con tain heuristics for dealing with that facet of C's:

F.Fillin: What are some methods for filli1w in new entries for facet F of a concept which is a C?

F.Check: How do we verify /debug potenti al entries?

F.Suggest: If AM bogs down, what are some new tasks (related to facet F of concep t C) to consider doing?

In the Lisp implement~tion of AM, each concept is me~int11ined as e~n ntom with an attribute/value list (property list), Each facet, and its li s\ of entries, is just a property and its associ<~ted vnlue. As e~n example, here IS a rendition of the Set s concept. It is meant to correspond to the notion of a collection of elements.

To decipher the Definitions fac:e t, there are a few things you must know. Facet F of concept C will occasionally be abbreviated as C.F. In those cases where F is "executable", the notation C.F will refer to appl y inp, the corresponding function. So the first entry in the Definitions facet is recursive because it cont<Jins an embedded call on the function Set.Definition. Since there are three separate but equivalent definitions, AM may choose whichever one it wants when it recurs. AM can choose one via a random selection scheme, or always try to recur into the same definition as it was just in, or perh~ps suit its choice to the form of the argument at the moment. All concepts possess executable def initions (Lisp predicates), thour,h not necessarily effective ones. When r,iven an e~rgument x, Set.definition will return True, False, or will eventually be interrupted by a timer (indic~ting that no conclusion was rParhed about whether or not x is a set).

The Views, Intuitions, ·and Analor,ies facets must be distine,uished from each other. Views is concerned with transformations between two specific concepts (e.g., how to view any predicate as a set, and vice versa). An entry on the Analogies facet is a mappinG from a set of concepts to a setof concepts (e.[;., between {bags, ba&-union, bag­ intersection, ... ] and {numbers, addition, minimum, ... }; or between {primes, factoring, numbers ... } nnd {simp\P. groups, fe~ctorin& into subgroups, groups ... }). lt2!1~!i2D~ deals with transformations between a bunch of concepts and one of a few lilr[;e, standard scenarios (e.g., intuit the relation "~" as playing on a see-saw; intu[t a set by drawing a Venn diar,ram). Intuitions are characterized by being (i) opaque (AM cannot introspect on them, delve into their code), (ii) occasionally fallible, (iii) very quick, and (iv) carefully handcrafted in advance (since AM can not pick up new intuitions via· metaphors to the real world, i1S we can).

Since "Sets" is a static concept, it had no Alr,orithms facet (as did, e.g., "Set-union"). The Alr,orithms facet of a concept cant a ins a li st of entries, a list of equivalent algorithms. Each algorithm must have three r.eparate part s:

1. Descriptors: Recursive, Linear, or ltNi1tivP? Quick or Slow? Opaque or Transparent'' Dest ructi ve?
2. Relators: Is this just a specia l case of some other concept's algorithm"/ Which others does thi s one call on'! Is this similar to any other al&orithms'!
3. Progr· am: A small, executable piece of Lisp code. It may - be used for actu~lly "running" the alr,orithm; it may al so be inspec:ted, copied, r ea~.oned <~bout, etc.

There are multiple algorithms because different ones have different properties: some ar·e very quick in some cases, ~. orne are always slow but arc very cleanly written and hence easier t.o reason about, etc.

Anolher facet possessed only by acti ve concept s is Domain/range. It is a list of entries, each of the form <"Dl 02 ... Di --> R>, which means that the concept takes a list of <~rgurnents, the first one bPing an ex~mple of concept IJI, th.e second of D2, ... , the last argument beinr, an example of concept Di , and if the alr,orithrn (~ny entry on the Alp,orithms filcet) is run on this argument list, then the value it returns will be an example of concept R. We may say that the Domain of the concept i ~. the Cartesian product Dl xD2x ... xDi, ;mel thilt the Rane;e of the concept is R For example;· the Domain/range of Set - union is <Sets Sets--> Set s>; Set -union takes a pair of sets as its argument list, and returns a set as its va lue.

Once the representation of knowledge is settled, there remains the actual choice of what knowledge to put into the program initially. One hundred elementary concepts were selected, corresponclinr, roup,hly to what Piaget might have called "prenumeric al ~.nowledgc". rigurc 1 presents a gr aph of these concepts, !d1owine, their interrelationships of Generalization/Specialization and Examples/lsa's. There is much static structural knov.>lode;c (sets, truth-values, conjectures ... ) and much knowlecle;e about simple activities (boolean relations, composition of relations, set operations, ... ). Notice that there is no notion of proof, of formal reasoning, or of numbers or arithmetic.

AM's basic activity is to find new entries for some facet of some concept . But which particular one should it choose to develop next? Initi<~lly, there arc over one hundred comepts, each with about twenty blank facets; thus the "space" from which to choose is of size two thousand. As more concepts get defined, this number increases. It's worth having AM spend some time deciding which basic task to work on next, for two reasons: most of the tasks will never get explored, and only a few of the tasks will appear (to the human user) rational things to work on at the moment.

Murh informal expert knowledge is required to constrain the search, to quickly zero in on one of these few very_ good !asks to tackle next. This is done in two stages:

1. A list of plausible facet /concept pairs is maintained. No task can get onto this "agenda" unless there is some reason why working on that facet of that concept would be worthwhile.
2. Each task on this agenda is ass igned a priority rating, based on the number (and strengths) of reasons supporting it. Thi s allows the entire agenda to be kept ordered by plausibility.

The first of these c.onstrainings is much like replacing a legal move generator wifh a plausible move generator~ in .a heuristic search program. The second ktnd of constraint IS akin to using a heuristic evaluation function to select the best move from among the good ones. Here is a typical entry on the agenda, a task:

' Activity: Fill in some entries Facet : for the GENERALIZATIONS facet Concept: of the PRIMES concept Reasons: because ( 1) There is only known gen'l. of Primes, so far . (2) The worth rating of Primes is now ve ry high. ( ~3) Focus of attention: AM just worked on Primes. I (4) Ve·r· y .. few numbers are primes; a slightly more I : plentiful concept may be more interesting. ;_ J='!:.i~it~: _ ---'-- - 350_~~! scal~f__~~~~ __

The <1ciUill top - level control policy is to pluck the top task (highest priority rating) from the agcndil, and then execute it. While a task executes, some new tasks may be proposed (and merged into the agenda), some new concepts mily get created, and (hopefully ) s01ne E'ntries for the specified f <~eel of the specified concept will be found and filled in. Once a tasi', is chosen, the priority rating of that task now ~.e r ves a new function: it is lilken ilS an estimate of how much computational resource to devote to wori',ing on this tnsk. The task ilbove, in the box, might be allotted 35 cpu seconds and 350 list cells, beciluse its rating w<Js 350. When either resource is exh<nJsted, work on the task halts. I' he task is removed from the agend~, and the cycle begins <mew (AM stilrts working on whichever task is now at the top of the agenda).

2.3. LOW-LEVEL CONTROL: THE HEU~ISTICS

After a task is selected from the ilgenda, how is it "pxecuted'"! A concise ilnswer would be: AM selects relevilnt heuristics and executes them; they satisfy the task v iil side-effects. This really just splits our original question into two new ones: How are relevant heuristics IOcilted'' What does it mean for a heuristic to be executed ilnd to achieve something?

2.3.1 How Relevant Heuristics are Located

E<Kh heuri stic is repre(·ented as a condition/action rule. The condition or left - hand-s ide of a rule tests to see whether th·e rule is applicable to the task on hand. The action or right - hand-side of the rule consists of a li st of actions to perform if the rule is applicable. E.g.,

IF thr curr<'nt t.a,k i< to r.hrrk r.x;Hnpks of a concept. X, and (l'nrsom<' Yl Y is a generalization of X, anrl Y ltas at. ira<t 10 known <'xmnple< a!HI all examplr.s of Y arr also r.xarnplr·s of X, THI·:N con,ircturr: X is rr.ally no more <pe<:ializr.d than Y, anrl arlrl t II at cnnjr.ct urc as a nrll' r.nt ry on I hr t·:xmnplr.s facet. of tllr. ConjN:s concept, anrl arlrl thr following ta<k t.o the agcnrla: "Check exampks of Y" for this rr.a,on: Y nwy analogou<ly turn out. to he equal to one of its supposrrl gcnrralizat.ions.

It is the heuristics' right h;md sides which ilccomplish the selected task; that process described in the next subsection. The left sides relev ancy checkers, and will be focussed on now: actually will be are the

Syntactically, the left side must be a predicate, a Lisp function which always returns True or False. It must be a conjunction P 1 AP2AP3A ... of smaller predicates Pi, each of which must be quick and must have no side effects. Here are some typical conjucts which might appear inside a left hand side:

Over half of Lloe current ta'k 's tinw allnt.mcnl i< used up; Thr'rr are <onw known cxauoplc' of Structure<; Some known g<'nrrali7.at.ion of the current concept (lhc concrpt. rncntionrrl as part of tile cunent task) has a romplct.rly r.mpty Example< facd; A ta<k rr'crntly worked on loarl tlor. form "Fill in facet. F of C", for any I<', wlocrr. Cis the cunrnt concept.; Tlor' U<rr h11< used this program at lra<t. on<:r' hdore;

It turned out that the laxity of constraints on lhe form of the heuristic rules proved excessive: it made it very difficult for AM to analyze and modify its own heur istics.

f'rom a "pure production system" viewpoint, we have ;mswered the question of loca ting relevant heuristics. Namely, we evaluate the left sides of all the rules, and see which ones respond "True". Bul AM contains hundreds of heuristics, and repeatedly evalu~ting each one's condition would use up tremendous amounts of time. AM is able to quickly select a set of potentially relevant rules, rules whose left sides are then evaluated to tes.l for true relevance. The secret is that each rule is stored somewhere a propos to it s "domain of applicability". The proper place to ~tore the rule is determined by the first conjunct on its left hand side. Consider this heuristic:

IV t.llc currrnt. task is to fiiHI rxtllnples of activity F, a111l a fast. algorithm for computing F i< known, TH I<N onn. way t.o get cxaonplr,, of I' i< to Til II F on randomly don<r.n cx·Hnpl<" of tile Domain of fi.

The very fir st conjunct of a rule's left side is always speciill. It specifies the domain of applicability (potential r e levilnce) of the heuri sti c, by naming a particular f<~cet of a particular concept to which this rule is relevant (in the above rule, the domain of relevance is therefore the l: xamp les face t of the Activity concep t). AM uses such first conjuncts as pre-preconditions: II potentially re levant rule can be locat ed by its first conjunct alone. Then, its left hand side is fully evaluated, to indicate whether it's truly rel evant . Here are a few typical expressions which could be first conjuncts:

The currcut t.a'k (the our. ju<t. <ckctr.rl from tloc agenda) i< of the form "Check the Domaiu/raugc f acct. of concept. X", whr.re X i~ 'omc 'urjcct ivc fun<:tion; Thr curn~nt t.ask rnatchc' "Viii in hounrlary ('xamplr.s of X", whrrc X is an opr.rat.ion on pairs of sets; The~ current. task is "Viii in examples of Primes";

The key observation is that a heuristic typically applies to all examples of a particular concept C. The rule above has C = Acti vity; it's relevant to each individual activity.

When il task is chosen, it specifies a concept C and a facet F to be worked on. AM then "ripples upward" to gather potentially relevant rules: it looks on facet F of concept C to see if any rules are tacked on there, it looks on facet F of each generalization of C, on each of their generl'llizations, etc. If the curr~t task were "Check the Domain/r ilnge of Union -a-Union" , then AM would ripple upward from Union-o-Union, alonp.; the Generalization facet entries, gatherin~ heuristics as it went. The program would ascertain which concepts claim Union-o-Union as one of their examples. These concepts include Compose-with­ self, Compose, Operation, Active, Any-concept, Anything. AM would collect heuristics that tell how to check the Domain/range of any composition, how to deal with Domain/range facets of any concept, etc. Of course, the further out it ripples, the more e,enernl (and hence weaker) the heuristics lend to be. Here is one hemislic, tncked onto the Domain/rane,e facet of Operation, which would be garnered if the selected task were "Check Domain/range of Union-o-Union":

2 This operation is the result of composing set-union with itself. It performs >.. (x,y,z) xu(yuz).

• I I' the r.u rrent t a'k i' "CI"'"k t I"' Domain/rang"' of F", an<l an entry on that. facet . ha' the form <D D ... D.., R>,

an <I conr.ept H i' a generali1.at ion of .C"oncnpt D,

TH I·:N it. i' worth 'pen<ling time r.hcr.king whethnr or not the range of F might h" 'imply D, in,tca<l of H.

Suppose one entry on Union-a-Union's Domain/range facet w<~s "<Nonempty-sels Nonempty- sels Nonempty-sets .., Sets>". Then the above heuristic would be truly relevant (all three conjuncts on its left hand side would be s f!lisfied) and it would pose the question: Is the union of thr ee no~empty sets fllways nonempty? Empirical evidence would .eventunlly confirm this, nnd the Domnin/rane,e facet of Union-o-Union would then contain that fact .

1-iere is another way to look at the heuri s tic -gathe~ing process. All the concepts known to AM are arranged tn a big hierarchy, via subset -of links (SpeciaHzations) . and e lement - of links (lsa). Since each heunsltc ts assoctaled w ith one indiv idual conrept (its domain of npplicability), there is a hiernrchy induced upon the set of heuri stics. Heritability properties hold: a heuri stic lacked onto concept C is applicable to working on all "lower" concepts. This allows us to efficiently analogically access the relevant heuristics simply by chasing upward links in the hierarchy. Note that the task selected from the agenda provides an expli cit pointer to the "lowest" -- most specific -- concer:>t; AM ripples upward from it. Thus concept s are gath~red tn order of increasing generality; hence so are ·the heunsttcs.

Below are summarized the three main points that comprise AM's scheme for finding ·relevant heuri stics in a "natural" way and then using them:

1. Each heuristic is tacked onto the most general concept for which it applies: it is gi ~en as large a domain of applicability as poss ible. Tht s wtll maxtmtze it s generality, while leaving its power untouched.
2. When the current task deals with concep t C, AM ripples upward from C, tracing along Generalization and l s<l links, to quic~, ly find all concepts wht ch clatm C as one of their examples. Heuri stics attached to all such concept s are polcn!i il lly relevant.
3. 3 . All heuristics nre represented as condition/action rules. Once the potentially relevant rules are located (in step 2), AM evaluates each's left h;md side, in order of incre<~s ing generality. The rippling process automatically gathers the heuristics in this order. Whenever a rule's left side returns True, the rule is known to be truly relevant, and its right side is immediately executed.

2.3 .2 What Happens When Heuristics Are Executed

When a rule is recognized as relevant, its right side is executed. How does this accomplish the chosen task?

The right side, by contrast to the left, may lake a gre~t deal of time, have many side. effects, and the value tt returns is always ignored. The right side of a rule ts a series of little Lisp functions, each of which is called an o.cti.on. Semantically, each action performs some processing which is appropriate in some way to the kinds of situations in which the rule's left side would have been satisfied (returned True). The only constraint which each action must satisfy is that it have one of the following three kinds of side-effects, and no other kinds:

1. It suggests a new task to add to the agenda.
2. It dictates how son1e new concept is to be defined.

3. It <~dds .some entry to some facet of some concept. Bear in mind that the right side of a single rule is a list of such actions. Let's now treat these three kinds of actions:

2.3.2.1 Heuristics Suggest New Tasks

The left side of " rule trigger s. Scattered among the list of "things to do" on its right side are some suggestions for fulttre tasks. These new tasks are then simply added to the agenda. The suggestion for the task includes enough information about the \ask to make it easy for AM to assemble its parts, to find reasons for it, to numerically ev C~IuC~te those reasons, etc. For example, here is a typical rule which proposes a new task. II says to generalize a predicate if it appears to be returning True very rarely:

.IF the current ta'k wa' "Fill in nxample' of X",

an<l concept X i' a Prc<licHtc,

an<l over 100 it em~ arc known in the tlornain of X,

an<l at. lea't 10 cpu ' """· have heen 'pent 'o far, atul X ha~ rct.nrnc<l True at lca<t. once, an<l X ret.urne<l Jial<e over 20 t imr< a~ often a. True, THEN a·l·l the following task t.o the agen<la: "Fill in generalization~ of X"

for the foil owing rea<on:

"X i' rarely sati,fie<I; a slightly lc" restrictive concept. might. he much more intcrc<ling"

Thi' r.-,a,on has a rating which ;, the Fal<e/True ratio

Let's see one instance where thi s rule was used. AM worked on the task "Fill in examples of List-Equality". One heuristic (di splayed in Se.c. 2.3.1, and again in detail in Sec. 2.3.2.3) said to randomly pick elements from that predicate's domain and simply run the predicate. Thus AM repeatedly plucked random pairs of li sts, and tested whether or not they were equal. Needless to say, not a high percentage returned True (in practice, 2 out of 242). This rule's left side was sati sfi ed, and it executed. Its right side caused a new task to be formulated: "Fill in generalizations of List-Equality". The reason w.as as staled above in the rule, and that reason got a numeric rating of 240/2 = 120. That task was then assigned an overall rating (in this case, just 120) and merged into the agenda. II s<~nclwiched in between a task with a rating of 128 and one with a 104 priority rating. Incidentally, when this task was finally selecte·d, it led to the creation of several interesting concepts, including the predicate which we might call "Same-length".

2.3.2.2 Heuristics Create New Concepts

One of the three kinds of allowable actions on the right side of a heuristic rule is to create a specific new concept. For each such creaiion, the heuristic must specify how the new concept is to be constructed. The heuri stic states the Definition facet entries for the new concept, plus usually a few other f acels' content s. After thi s action terminates, the new concept will "exist". A few of its facets will be filled in, and many others will be blank. Some new tasks may exist on the agenda, tasks which indicate that AM ought to spend some time filling in some of those facets in the near future. Here is a heuristic rule which results in a new concept being created:

IF the current. task was "Fill in ~xamplcs of F" atul .r i' an operation, from <lomain !I into range R, an<I more than 100 item~ arc known example' of A, and more than 10 rang" it<'>lll' (cxampks of H) were fomHI hy applying I<' to these domain clements, and at lca,t. on<'> of these range items 'h' is a ri ist.in­ guishc<l member (e,pccially, an extremum) of R, THJ·:N for each such 'h'EB, create the following concept:

and t.lo e reason for thi~ aeation is: "It.'s worth investigating A · ~ wloid1 have unusual F-valnes" and arid five nr w tasks to the agrnola,

of the form "Fill in farr t. x of F- iuvers()-nf-h" whcr0 x 1~ C:onjnct.urn~, Gnncn-l1i1.at ion~,

Spr.ciali7.ations, l·:xampl cs, an<l !sa's; for the following reason:

"Tht~ r:onr:<'pl. was nnwly synth f'sizr'!d; it. is r.ru .. cial to firul whrn~ it ' fit~ in' In t.h r hir.rardoy" Thr. r eason's rat.iug i ~ just Wnrth(F-iuvcrse-of -h).

One use of this heuristic w~s when the current task was "Fill in examples of Di visors-of". The heuri stic's left side was sati sfi ed because: Di visors -of is an operat ion (from Numbers to Sets of numbers), and f ar more than the required 100 differenl numbers are known, and more than 10 different sets of factor s were located ;~llogelher, and some of them were in fact di stinguished by being extreme kinds of sets (e.g., singletons, empty sel s, d~ubletons, lriplelons, ... ). After its left side triggered, the right side of the rule was executed. Four new concep ts were created immediatel y. Here is one of them:

··------- ·---------, NAM fo:: Divisors-of - Inverse-of - Douhleton DlO:FINITION: A (a) Divisors-nf(a) is a Dnuhlr.t.on GEN Jo:H A J.JZATIONS: Numhers WORTH: 100 INTF.HI':ST: Any con jecture involving hoth this concept and ci th<'r Di visors -of or Times

Thi s is a concept representing ~ certain c l~ss of numbers, in fact the numbers we ca ll "primes". The heuristic rule is of course appliCable to ~ny kind of operation, not just numeric ones. As another instance of its use, consider what happened when the current task was "Fill in examples of Set-intersect". This rule caused AM to notice that some pairs of sets were mapping over into the most extreme of e~ll set s: the empty se t. The rule then had AM define the new concept we would call "disjointness": pairs of sets having empty intersection.

There is just a tiny bit of "theory" behind how these concept - creating rules were designed. A facet of a new roncept is filled in immediately iff both (i) it's trivial to fill in at creation-time, and (ii) it would be very difficult to fill in later on. The following face ts are typically filled in right awe~y: Definitions, Algorithms, Domain/range, Worth. Each other facet is either left unmentioned by the rule, or else is explicitly made the subject of a new task which gel s e~dded to the agenda. For instance, the heuristic rule above would propose many new tasks at the moment . that Primes were created, including "Fill in conjectures about Primes", "Fill in specializations of Primes", etc.

2.3.2.3 Heuristics Fill in Entries for a Specific Facet

If the task plucked from the agenda were "Fill in examples of Set-union", it would not be too much to hope for that by the time all the heuristic rules had fini shed executing, some examples of that operation would indeed exist on the Examples facet of the · Set-union concept. Let's see how this can happen.

AM starts by rippling upward from Set - union, looking for heunstics which are relevant .to finding examples of Setunion (there are no such rul es), relevant to finding ex e~rnples of Set-operations, of Operations, of any Activi t y, of any Concept, of Any thing. Here is one rul e app.li.cable to any Acti v it y:

l F thr current task i~ to fill in exarnpl<·s nf 1", arul V is an operation, say with domain D, anrl thrrc i~ a fast knowu <tlgnrit.l1111 for F, THI·:N onr way to grt r.xanoplrs nf Vi s to non t''s algorithm on ranrlornly chns<'n ··xarnpl<'s of D.

Of course, in the Li sp implementation, thi s si tuation- action rule is not coded quite so neatl y. It would be more faithfully translated ;~ s follows:

IF' Cl JHR -TASK mat <:hes (FILLIN EXAMPLES F+-anything), an<l F . i~a Act iv ity,

anrl t.h r. Algorithms far.r. t of Vis not hlank ,

TH J<:N carry out t.hc following prnc<'durc:

• L Find t.hr <lomain of 1', and call it D;
• 2.. Find rxamplr.s of D, anrl ca ll tlw rn I·:;
• :l. Find a fast. algorithm to compute V; c<tll it. A;
• 1-. Repr.at.crlly :

~-a. Choose any rn<' rnhrr of 1·:, aud r.all it El.

~-h. Hun A on 1·:1, and ca ll thr result X.

1-c. Chr.r.k whrthcr <El ,X> satisfies tire dr.finition of 1'.

~· ol. If ~o, t h<'n add <1':1 ..,. X> to thr. F:xampl cs t:acr.l nf V.

1-c. Tf not., t.hr·n ;Hiol { 1·:1 _, X> to the Noncxmnpks facr t. of V.

Let's see exact ly how thi s rule fo~ncl exampl es of Set ­ union. Step (I) says to locale the domain of Set-union. The f acet labelled Domain/range, on the Set -union concept, coni a ins the entry (SET SET -> SET), whi ch indi ca tes that the domain is a pair of set s. That is, Set-union is an operation whi ch accepts (;~ s its arguments) two sets.

Since the domain elements are sets, step (2) says to locale examples of sets. The facet labelled Examples, on . the Sets concept, points to a li st of about 30 different sets. This includes {Z}, {A,B,C,D,E}, {}, {A,{{B}}}, .. .

Step (3) involves nothing more than accessing some entry tagged with the descr iptor "Qui ck" on the Algorithms facet of Set-union. One such entry is a recursive Li sp function of two arguments, which halt s when the f ir st argument is the empt y set , and otherwi se pull s an element out of that set, Set-insert s it into the second argument, and then recurs on the new values of the two sets. For convenience, we'll refer to thi s algorithm as UNION.

We then enter the loop of Step (4). Step (4a) has us choose one pair of our examples of sets, say the first two {Z} and {A,B,C,D,E}. Step (4b) has us run UNION on these two sets. The result is {A,B,C,D,E,Z}. Step (4c) has us gra·b an entry from the Definitions facet of Set - union, and run it. A t y pical definition is this formal one:

(A (SI S2. S:l) (AND (For all x in SJ, xis in S:l) (f'or all x in S2., x is in S.1) (For all x in S:l, x is in S1 or x is in S2.))))

It is run on the three. arguments S 1 ={ Z}, S2={A,B,C,D,E}, S3={A,B,C,D,E,Z}. Since it returns "True", we proceed to Step (4d). The construct <{ Z}, {A,B,C,D,E} -> (A,B,C,D,E,Z}> is added to the Examples facet of Set - union.

At this stage, control returns to the beginning of the Step (4) loop. A new pair of sets is chosen, and so on. The loop ends when either the lime or space allotted to this rule is exhausted. AM would then break away at a "clean" point (just after finishing a cycle of the Step (ll) loop) and would move on to a new heuristic rule for filling in examples of Set-union.

3. RESULTS

3.1. EXCERPT OF T~-~AM' PROGRAM RUNNING

l~cpcalcdly, the top task is plucked from the agenda, and heuristi cs are executed in an attempt to satisfy it. AM has il modest filcility that print s out a descr iption of these ilclivi ties ii S they occur. Here is il tiny excer pt:

• ** J il ~!<,_; ** Fill in Examples of the concept "Di visors-of". 3 Reasons:
• ( 1} No known examples of Divi sors-of ye t.
• (2} Times (related to Di visors-of) is now v. in!.
• (3} Focus of attention: AM just defined Di visors-of.

26 examples found, in 9 sees. e.g., Divisors-·of(6)={1,2,3,6).

• ** Tas~ ** Consider nos. having small sets of Divisors-of. 2 Reasons:
• ( 1) Worthwhile to look for extreme cases.
• Focus: AM just worked on Di visors-of.
• Filling in exilmples of numbers with 0 divisor s. 0 examples found, in 4.0 seconds.

Conjecture: no numbers have preci sely 0 di visor"s.

• Filling in examples of numbers wit h 1 divisors. 1 ex<tmples found, in 4 sees. e.g., Divisors-of( 1} = { 1 ). Conjecture: 1 is the onl y n11mber with exactl y 1 divisor.
• Fi lling in examples of numbers with 2 di visors. 24 examples found, in 4 sees. Divisors -of(l3}={1,13). No obvious conjecture. May merit more study.

Creating a new concept : "Numbcrs-with-2-divisors".

Fi lling in ex<tmples of numbers with 3 divisors. 11 examples found, in 4 sees. Di visors-of(49}={ 1,7,49). All nos. with 3 div isors arc al so Squares. Unexpected!. Cre<>ting a new concept: "Numbers-with-3-·divi sors".

• ** T<tsl_; ** Consider squ<tre-rool s of Nos-with-3-divisors. 2 Reasons:
• ( 1} Numbers-wi th -3-divisors unexpectedly turned out to all be Perfec.t Squares as well.

(2) Focus: AM just defined Nos--with-3-divisors.

All squ<tre-rools of Numbers-with-3 --divisors seem to be Number s-with-2-di visors.

E.g., Divisors(l69} = Divi sors(l3) = ll,13}.

Even the converse of thi s seems empirically to be true. The chance of coincidence is below acceptable limits. Boosting the Worth rating of both concepts.

• ** Task: ** Consider the squares of Nos-with-3-divisors. 3 Reasons:
• ( 1} Squares of Nos-with -2-divisors were v. int.
• (2} Squilre-roots of Nos-with-3-divisors were in!.
• (3} Focus: AM just worked on Nos-with-3-divisors.

3.2. OVERALL PERFQB.MAtl_Q_F;_

Now !hill we've seen how AM works, and we've been exposed to a bit of "loca l" results, let's 1 ake a moment to discuss the totality of the mathematics which AM carried out. AM began its investi gations with scanty knowledge of a hundred elementary concepts of finile set theory (see Fig. 1 }. Most of the obvious set-theoretic concepts and relationships were quickly found (e.g., de Morgan's laws; si ngletons), but no sophistic<tled set theory was ever done

(e .g., di<tgon<tlization). Rnlher, AM di scovered natural number s <tnd went off exploring elementary number theor y . Arithmetic operations were soon found (as analogs to set-theoretic operations), and AM made r<tpid progress in di visibility theory. See Fig. 2. Prime pairs, Diophantine equations, the unique factori zation of numbers into primes, Goldbnch's conject ure - - these were some of the nice di scoveries by AM. Many concept s which we know to be cruc i<tl were never uncovered, however: remainder, gcd, greater- than, infinity, proof, etc. These "omiss ions", could h<tve been discovered by the ex isting heuristic rules in AM. The paths which would h<tve resulted in their definition were simply never r.ated high enough to explore.

All the di scoveries mentioned (including those in Fig. 2} were made in a run lasting one cpu hour (lnterl isp+100k, Surnex PDP- 1 0 Kl}. Two hundred jobs in toto were selected from the agenda- and executed. On the average, <t job was gr<tnled 30 cpu seconds, but <tclu<tlly used only 18 seconds. For a t y pical job, about 35 rules were located as polentially relev<tnt, and about <t dozen <tctua lly f ired. AM began with 115 concepts and ended up wilh lhree times !hil l many. Of the synlhesized concepts, half were technic<tll y termed "losers" (both by the author and by AM), and half the remaining ones were only marginal.

Although AM f<tred well according to sever<t l different measures of performance (see Section 3.4), of great signific<tnce are its limito.tions. As AM r an longer and longer, the concepts it defined were further and further f rom the primiti ves it began with. E.g., "prime- pai rs " were defined using "primes" and "addit ion", the former of which was defined f r om "divisors-of ", which in turn c<tme from "multiplication", which arose from "<tddition", which was defined as a restriction of "union", which (finally!) was a primitive concept that we hnd supplied (with heuristics) to AM initi<tll y. When AM subsequently needed help with prime pairs, it was for ced to rel y on rules of thumb supplied originally about unioning. Although the heri tability property of heuri stics did ensure that those rules were sl ill v alid, the trouble was that they were too general, too weak to deal effectively with the specialized notions of primes and arithmetic.

r or instance, one general rul e indicated that AuB would be interesting if it possessed properties absent both from A <tnd from B. This translated into the prime- pair case as "If p+q=r, a.nd p,q,r a.re primes, Then r is interesting if it ha.s properties not possessed by · p or by q." The search for ca tegories of such interesting primes r was of course barren. It showed a fundamental lack of understanding about numbers, addition, odd/even -ness, and primes.

The key deficiency was the lack of adequate meto.-rules (Davis 76]: heuristics which reason about heuristics: keep t rack of their performance, modify them, create new ones, etc.

A!> ide from the preceding major limitation, most of the other problems pertain to missing knowl edge: Many concepts one might consider basic to discovery in math are absent from AM; analogies were under-utilized; physical intuition was hand-crafted only; the interface to the user Wils far from ideal; etc. A large effort is underway this year at C<trnegie-Mellon Uni versity, comprised of Greg Harris, Doug Lena!, Elaine Rich, Jim Saxe, and Herbert Simon, to overcome these limitations.

One valuable aspect of AM i~. th<~t it i~: amenable to many kinds of experiments. Although AM is too ad hoc for numeric results to have much significance, the qualitative results of such experin\ents may have some valid implications for math research, for autom<~ting math research, and for designing "scientist assistant" programs.

3.3.1 Must the WORTH numbers bo finely tuned?

Each of the 115 initial concepts had, supplied by the author, a rating number (0-1000) signifying its overall worth. The worth ratings affect the overall priority values of tasks on the agenda. Just how sensitive is AM"s behavior to the initial settings of the Worth numbers?

To test this, a simple experiment was performed. All the concepts' Worth facets were set to 200 initially. By and large, the same discoveries were made as before. But there were now long periods of blind wanderings (especially near the beginning of the run). Once AM hooked into a line of productive developments, it advanced at the old rate. During such chains of discoveries, AM was guided by massive quantities of symbolic reasons for the tasks it chose, not by nuances in numeric ratings. As these spurts of development died out, AM would wander around again until the next one started. ·

3.3.2 How Finely Tuned is the Agenda?

The top few candidates on the agenda illmost always appear to be reasonable things to do at the time. But what if, im:tead of picking the top-rated task, AM selected one randomly from the top 20 tasks on the agenda? In that case, AM's rate of discovery is fdowed only by about a factor of 3. But the apparent "rationality "of the program (as perceived by a human onlooker) disintegrates.

3.3.3 How Valuable is the Presence of Symbolic 'Reasons'?

Only one effec.t of note was observed: When a task is proposed which already exists on the agenda, then it tmtlters very much whether the tilsk is being suggested for a new reason or not. If the reason is an old, already­ known one, then the priority of the task on the agenda shouldn't rise very much. But if it is a brand new reason, then the task's rating should be boosted tremendously. The importance of this effect argues strongly in favor of having symbolic justification of the rank of each task in a priority queue, not just "summarizing" each task's set of reasons by a single number.

3.3.4 What if Certain Concepts are Excised?

As expected, eliminating certain concepts did seal off whole sets of discoveries to the system. For example, excising Equality prevented AM from discovering Cardinality. One surprising result was that many common concepts get discovered in several ways. For instance, multiplication arose in no fewer than four separate chains of discoveries.

3.3.5 Can AM Work in the New Domain of Plane Geometry?

One demonstration of AM's gener:1lity (e.g., that its "Activity" heuristics reillly do apply to any activity) would be to choose some new mathemiltical field, add some concepts from !hilt domain, and then let AM loose to discover new things. Only one experiment of this type was actually carried out on the AM program.

·Twr->nty concepts from elementary plane geometry were defined for AM (including Point, Line, Angle, Triangle, [quality of points/linesfangles /tri<~ngles). No new heuristics were ;~deled to AM.

AM was able to find examples of all the supplied concepts, and to use the char11cter of such empirical data to determine reilsonable directions to proceed in its research. AM derived the concepts of congruence and similarity of triangles, plus many other well -known concepts. An unusual result was the repeated derivation of the concept of "timberline": this is a predicate on two triangles, which is I rue iff they share a common vel"! ex and angle, and if their opposite sides Me parilllel. AM 11i so came up with a cute geometric interpretation of Goldbach's conjecture: Any angle (0 - 180°) can be approximated to within 1° as the sum of two angles each of a prime number of dep.;rees.

3.4. EVALUATING THE 'AM' PROGRAM

We may wish to ev<~luate AM using various criteria. Some obvious ones, with capsule results, appear below:

1. By AM's ultimate achievements. Besides discovering many well-known useful concepts, AM discovered some which aren't widely known: rnilximally -divisible numbers, numbers which can be uniquely represented as the sum of two primes, timberline.
2. 1:3y the character of the differences between initial ilnd final states. AM moved all the way from finite set theory to divisibility theory, from set s to numbers to interesting 1-,inds of numbers, from skeletal concepts (none of wllich had any Examples filled in) to completed concepts.
3. By the quality of the route AM took to accomplish this mass of results. Only about half of AM's forays were dead-ends, and most of those looked promising initially.
4. By the character of the hum<ln-·machine interactions. AM was never pushed far along this dimension.
5. By its informal reasoning abilities. AM was able to quickly "guess" the truth value of conjectures, to estimate the overall worth of each new concept, to zero in on plausible things to do each cycle, and to notice glaring anillogies (sometimes).
6. By the results of experiment!; -- and the fact that experiments could be performed at all on AM.
7. By future implications of thi~ project. Only time will tell whether this kind of work will irnpilct on how mathematics is taught (e.g., explicit teaching of heuristics?), on how empirical research is carried out by scientists, on our understanding of such phenomena as discovery, learning, and creativity, etc.
8. By comparisons to other, similar systems. Some of the techniques AM uses were pioneered earlier: e.g, prototypical models [Gelernter 63), and analogy [Evans 68], [Kling 71]. There have been many attempts to

incorporate heuri stic knowl edge into a theorem prover [Wang 60), [Guard 69), [Bl edsoe 71 ], [B1·otz 7 4), [Eloyer & Moore 7~ ]. Most of I he apparent differences between them <1nd /\M vanish upon close examinntion: The goal­ dnven control structure of these sy(. l ems is a compiled form of AM's rudimentary "focus of attention" mechanism. The fe1d that their overil ll aclivi1y is l ypic<1ll y labelled as cleclucl.i vc is <1 mi snomer (since constructing a ciifficull proof is u~.ually in prac:tice quite inductive). E.ven the character of I he inference processes are analor;ous: The provers I yp ica ll y coni <lin a couple binary infe r ~e nre 1·ules, like Modus Ponens, which are rPiali ve ly ri >.ky to iipply but can y ield big results; AM's few "binar y " operators have the ~ ame characteristics: Compose, C<1110nize, Logically-combine (di sjoin and conjoin). The deep di ~. tinction ~; between AM <~n cl the "heursti c theorem rrovers" are these: the underlying motivations ·(heuri stic r.10delling vs. building tool s for problem sol ving), the ri chness of the knowledge b<~ ~· e (hundreds of heuri sti cs vs. only a few), and the amount of emphasis on formal mel hods.

Theory formation sys tems in any field have been few. Meta -Dendral [Buchanan 75] represents per haps the best of these. But even thi s sys tr~ m i!_; given a fi xed set of templates for rules which it wi ~; hes to find, and a fixed vocabule1ry of mass spectral concerts to plug into those hypothesis templates; whc1·eas AM ~.e l ect i ve ly enla1·ges its voc <~bul<~ry of math concept s. Also, AM must gather its own data, but thi s is much easier in math than in organic chem.

There has been very lillie published thought about "di scovery" from an algorithmi c point of view; even clear I hinv.ers like Poly a and Po inc a1·e' treat mathematical ability as a ~; acred, almost mystic quality, ti ed to the unconscious. The writings of philosopher s and psychologists invariably i' ll empt to examine human performance and belief, which <1re f M more managable lh<1n ·creativity in vitro. Amarel [ 1967) notes it may be poss ible to learn from "theorem finding" programs how to \acl\ le the general task of e1ulomating scientific research. AM has been one of the first attempts to construct such a program.

3.5. FINAL CQNCLUS_LQfi~

• -> AM is a demonstration that a few hundred general heur istic rul es suffice to guide an automated math researcher as it explores and expands a IMge but incomplete knowledge base of math concepts. AM demonstrates thai some a~.pects of creative research can be effectively modelled as heuri stic search.
• -> This work has also introduced a control structure based upon an ordered ilgenda of small research tasks, each with a list of supporting reasons attached.
• -> The rnain limitation of AM was its inability to synthesize powerful new heuristics for the new concepts it defined.
• -~ 1 he main successes were the few novel ideas 1! came up with, the ease with wh1ch a new task domain was fed to the system, and -- most importantly -- the overall rational sequences of behavior AM exhibited.

ACKNOWLEDGEMENT

Thi s research was initi.al ed as my Ph.D. the ~;is ill Stanford University, and I wish to ciPej?ly thanv. my Rdvi sers and committee members: Bruce [luchanan, Paul Cohen, Edward Feigenbaum, Cordell Green, Donald Knu\h, and Allen Newell. In <1cldition, I gladly acknowi PCige the ideas I have received in di scussions with flvra Cohn and with Herbert Simon.