A Language Based Problem-Solver

1. Introduction

The state of the art in problem­ solving, constituting the background to the work reported here, is based on a nwnber of con­ cepts and techniques, including the following:

use of heuristics, in addition to algorithms, in programs (1, l);

provision for pursuing a hierar­ chically organized set of goals and subgoala, by the use of rec­ ursive routines and push-down stacks (3);

use of a scheme of representation for mapping problem-situations into data structures (4);

use of an input language resembling a natural language (5);

use of sets of strings in a language as rep res entation&, to provide for generality (6).

The use of an adequate language for input and output, and for the internal represen­ tation of relevant information as well, is very attractive as a possible solution to the problem of generality. Similarly, one is also attracted by the pouibility of realizing a system which will accept directions (complete or partial) for solving problems in some language resembling a natural language (7), Obviously, such a sys­ tern will be open-ended in a very significant sense of the term, We start with these concepts and argue further that a general problem-solver should possess a general language-using capability. This capability should uniformly provide for input/output communication, for the internal representation of the totality of problem situa­ tions constituting the problem world, and for the communication and rep res entation of problem-solving techniques, including algorithms and heuristics, The approach reported here is further characterized by three features:

• (a) the requirement that the system be open-ended, in regard to the language used; it should be possible, at any stage, to add incrementally to the repertoire of the system,
• (b) the requirement that the system be similarly open-ended in regard to the class of questions answered, or the class of problems solved, and
• (c) the requirement that the capability of the system be enhanced in a simple and natural manner. Specifically, it is required that the system should enhance its capabilities automat­ ically when a worked-out example is supplied.

The first two requirements raise major questions regarding the nature of the language processor to be used, The following sections describe these questions and provide an answer for them, based on the concept of analogy directed behaviour, This concept is then extended to provide a basis for meeting the third requirement cited above - that the problem-solving should itself be example driven. It is argued that such a problem­ solver will cope with an open-ended problem world, in a sense, creatively.

z. The Basic Issues

One needs a theory of language to design any language-using system, a theory which covers syntax, semantics and pragmatics.

Designers have been quick to borrow from lin­ guistics whatever has been available in the way of syntax and it has been suggested that a for­ mal grammar of a language, such as a transfor­ mational generative grammar, could be used in conjunction with a syntax-directed parser to perform an analysis of natural language sentences (8, 9).

Another frequently suggested pos sibi­ lity is the use of a semantic processor which will map sentences of a natural language into strings in a formal language (say, a first order predicate calculus) using information obtained from syntax analysis, whenever necessary (1 0).

There are difficulties in adopting syn­ tax directed parsing methods for use in a problem-solver of the type visualized in the previous section. For example, it is algorith ­ mically impossible to produce a generative gra­ mmar for every given set of sentences (aee(ll) for a formal analysis). Making incremental additions to a generative grammar to extend the language is an equally demanding task, sharing many features with the task of program deTelo­ pment and debugging.

These limitations on automatic acqui­ sition are severe in view of the enormous effort required to create grammars manually. Machine-usable grammars for chunks of nat­ ural language large enough to be useful are not yet available.

A similar, if not worse, situation prevails in the area of semantics of useful chunks of natural language. The mapping of an input sentence into a formula in some logical calculus requires an algoritlun. There is no uniform procedure for arriving at such an algo­ ritlun which maps sentences in a given language into formulas in a chosen logical calculus. Any such algorithm will require considerable modi­ fication and debugging when the set of sentences it has to handle is enlarged in any significant manner.

3. The Case for Analogy

Is there any alternative, then, to the design of a language processor? Is it possible to avoid syntax-directed analysis, followed by a mapping of the input sentences into strings in a logical calculus ?

The alternative explored in the work reported here is based on the notion that hwnan language behaviour is analogy directed. One's response to a verbal stimulus is generally de­ termined by the similarity it has to a familiar stimulus. The response to the new stimulus resembles the response to the familiar one in certain ways. One is often taught the answer to a new kind of stimulus by being given an example.

To model this type of behaviour, one has to look for a programmable process which will carry out this analogizing and answer new questions on the basis of a set of question­ answer pairs used as examples. Each question­ answer pair that is supplied as an example would be accompanied by a set of sentences (the context). The processor would obviously use a store for factual information (say, in the form of sentences) which describes the class of situations about which it can be questioned. This store forms a kind of data-base. When presented with a new question, the processor creates a reply to it by recognizing its simila ­ rity to a question given earlier as an example. From the example, the processor would identi­ fy the form of the informative sentences rele­ vant to the question. Then the processor would identify such sentences in the data-base and create a reply.

Proceeding further, one could add t o the system being visualized to enable it t o handle inputs other than simple questions. Some inputs may be informative sentences which have to be analyzed in order to extract the informat­ ion they bring to the system. The extracted information is then incorporated into the data base.

Finally, one could imbed a language processor of this sort into a problem-solver.

The following sections show how these tasks are tackled. But, it is useful here t o swnmarize the motivations for investigating analogy as a principle directing natural language behaviour:

(a) Analogy appears attractive as one technique by which a language may be acquired, An analogy directed processor can be made t o tackle a new class of questions or statements by supplying it with an example. The process is inc rem ental.

(b) An analogy directed processor is not limited to any specific language, Depending upon the exa.Inples supplied, it tackles different languages,

(c) Recognizing a familiar structure under­ lying a new situation, and responding to it ace­ ordingly, appears to be an essential component of all intelligent behaviour, A language proce­ ssor used by a problem-solver will provide for such recognition at each step of problem­ solving. For instance, a simple question that arises at some step of problem-solving will be recognized by its familiar structure, even if it is new in certain respects, and be answered appropriately. In other words, a language processor which can handle new sentences by analogy provides the basis for a problemsolver which can handle new problems by analogy.

A detailed treatment of the role of languag.e learning in intelligent behavior may be found in (12). In this paper, Narasimhan argues that the use of a rigidly determined language denies a problem-solver the ability to cope with new classes of situations. (In McCarthy's words (7) a problem-solver using such a limited language cannot be 'told' about the new classes of situations, and therefore, it cannot also learn their relevant features by itself).

• {d) The approach prescribes a simpler structure for a language processor. Seemingly arbitrary compartmentalization of the process is avoided. Consider, for example, the syntax directed processors which fail to use semantic o r contextual clues in syntactic disambiguation. Analogy directed processors are not divided into such non-communicating sub-systems,

A detailed critique of language behavior models incorporating generative grammars has been written by Hockett {13), He also presents argwnents for recognizing the important role of analogy in human language behavior.

4. The Proposed Model for a Language Proces sor

The considerations described in the previous sectiOTJII lead to a model for a language processor having the following features:

• {a) The processor deals with situations, a situation being a stimulus (or input) in its

context.

The stimulus is a string of symbols (e. g., a question in a natural language, the words being treated as symbols here). The context is a set of strings of symbols (e. g., a set of sentences describing some aspect of the world that is being questioned).

(b) The response of the processor to any situation is based on pattern setting examples (or paradigms) given to it earlier.

A paradigm consists of a context ( a set of strings of symbols), an input ( a string of symbols) and a response {or output), The response is a sequence of strings of symbols (e. g., a sequence of sentences in a natural language),

(c) Paradigms are stored in a form that highlights their structure, de-emphasizing the particulars of the situation involved. A para­ digm stored in this form, called a schema, can be used by the processor to create responses to new situations by a process of extrapolation,

• (d) The processor has access to a store for sentential strings, constituting a data-base (see Fig.l).

Inputs to the processor are of two kinds. The first kind of inputs are paradigms labelled as such, The other kind of inputs are sentential strings (e. g., questions, commands or informational sentences in a natural langua~ The processor schematizes and stores the para­ digms for later use. The processor responds to sentential stimuli by extrapolating from an appropriate schematized paradigm, if such a paradigm is available. In any case, the sent­ ential input is added to the data-base, for pos s­ ible functioning as a contextual string for later inputs.

• (e) The suitability of a (schematized) para­ digm for determining the creation of a response to a given stimulus is based on two factors:
• structural similarity between the current stimulus and the stimulus component (or input component) of the paradigm,
• ii) the presence or absence in the data-base of a set of strings having specified structures (the processor obtains the specification for these structures by extrapolating from the schematized paradigm being tested for suitability).
• (f) Assume a suitable schema is found for determining the response in a given situation. The processor computes a response having a structure determined by the schema. Elements of the response (e. g., words, numbers and phrases) may be obtained by the processor from the sentential store and incorporated into the structure as specified by the schema.

Obviously, the processes referred to in paragraphs (c), (d), (e) and (f) above have to be described in detail. This is done in the following sections. Before proceeding further, it is, however, necessary to describe an impo­ rtant feature of the processor which provides for a problem-solving capability. The same facility enables the processor to respond to a stimulus which has a complex structure, with phrases nested inside other phrases at several

levels.

• (g) The extrapolation procedure referred to in paragraph (f) determines a series of str­ ings called 'the response'. In the case of cert­ ain classes of situations, the response may simply be printed out (e. g., a simple question is given a factual answer, w'ithout involving nested computation).

In the general case, however, the ext­ rapolated 'response' may function as a sequence of internal stimuli. In other words, in response to a given stimulus, the processor presents itself with a sequence of internal stimuli, The processor has appropriate provision to halt the main sequence of computation at one level to perform necessary subcomputations at a lower level, as necessitated by the internal stimuli. The processor can, in this manner, respond to internal stimuli precisely as it responds to an external one, choosing suitable schema to det­ ermine the responBe. Generally, the nesting extends only a finite number of levels and the process ultimately terminates.

The processor prints out each string in 'the response' at each level when it arises as an internal stimulus. Many such strings do not require any further processing, as the available schemata do not provide for it. Any such str­ ing just gets printed out and the processor moves on to the next internal stimulus. The complete print-out is the true record of respon­

ses at all the levels.

The machinery for nested computation of responses to a hierarchically organized set of stimuli is basically the GPS (3) machinery, involving push -down stacks, etc,

1. The Nature of the Paradigms Used

A simple paradigm is:

Context: The weight of the ship is

2.000 tons

Input

Output What is the weight of the ship?

2.000 tons

Given the new situation,

Context: The height of the boy is

four feet

Input What is the height of the boy?

Extrapolation at one level yields the answer: "Four feet".

On the other hand, a more complex paradigm would be something like this:

Context: The density of lead is 8 gm per cc

The volume of a sphere is 0. 75 x PIx radius **3

The radius of a sphere is O. 5 x the diameter

Find the weight of a lead sphere 6 em in diame1er

1. Find the volume of the sphere

Input

Output

1. Multiply the volume by the density
2. That is the weight of the sphere

Obviously, the three strings in the 'output' are internal stimuli which trigger off internal activity to create the final output.

The choice of these forms for paradi­ gms reflects certain beliefs regarding human verbal behavior. One belief is that the prese­ nting of a paradigmatic example of the desired behavior is most valuable when it is clearly separated from the preceding and succeeding activity. The paradigm should be well segmen­ ted from the background activity and be labelled as such. Secondly, when question-answering or problem-solving is taught, it is very useful, if not imperative, to draw attention to the re­ levant facts - the context,

6. The Paradigmatic Processor

6. 1 Schematization of Paradigms

C :>nsider a paradigm consisting of strings of words and symbols, these strings being statements, questions or commands occ­ urring in the paradigm. The paradigm is divi­ ded into a contextual component, consisting of the strings C 1 ,Cz, C3, ··· , Cn· an 'input' component consisting of one string Q and an 'output' component consisting of the strings A1 ,A2,A3, ... , Am

Let the ordered set of strings C 1 ,c 2 , c3' .... en be named c and the ordered set of strings A 1 ,A2 ,A 3 , ··· , Am be named A. A paradigm p is then a triple ( C, Q, A ] . Given a set of paradigms of this form, how does one extrapolate from them to compute the appropriate response to a new stimulus?

As mentioned earlier, paradigms sup­ plied to the processor are 'schematized' and stored. The schematization serves essentially to a sa ign a at ructure to the paradigm, facilitating extrapolation. Any input stimulus S, a string of words and symbols, triggers of! a search activity in the processor. The search is for the 1 schema 1 of a paradigm p (C,Q,A] which has an input component, Q, maximally resembling S. By a linear mapping of symbols of S onto matching symbols in Q, substrings of S are placed in one-to-one correspondence with substrings of Q (illustrated below}.

Substrings such as 1 the weight of the ship', 'the radius of the sphere', etc., are treated as integral units whenever necessary. This follows the conception of a sentence as a string of units in specified order, some units being words or single symbols, while others are phrases defined by sets of recursively app­ licable rules (Bobrow(S) and Weizenbaum (14) describe approaches which suggested this dev­ elopment. Leavenworth (15) and Woods (16) are also relevant papers).

Consider a paradigm p [ C,Q,A]. To assign a structure to this paradigm, we look for maximal substrings which occur in one or more places in one set of strings as well a11 in one or more places in another set of strings. For example, the maximal substrings common to C and Q below are (the cost of, is, 4, pencils)

C : The cost of one pen is 4 rupees The cost of two pencils is 1 rupee Q : What is the cost of 4 pens and 3 pencils

Let Seq be the set of maximal substrings com­ mon to Q on one hand and to C on the other. Saq is the set similarly defined with respect to ~and Q, The set of maximal substrings, each one of which occurs somewhere in A as well as somewhere in C, is called Sea. We define two new sets

The schematization of the paradigm p [~. Q, A] is performed by substituting uniformly for each substring in the set Sv· a corresponding formal variable, at each of it· occurrences in p. This requires the generation of a set of distinct formal variables Sf , such that IStl · lsv I . The schematization gives us the schema K [ Sq !_Scf !... C' , Q, A' ]where 'C 1 is obtained from C and A 1 from A by the substitution process described above. scf is a new set of variables obtained by substituting in Sea every occurrence of a variable in Sv by the corresponding formal variable from Sf. This process is illustrated by the following example:

Paradigm

C : G is 31.5 feet per second squared The ball is thrown vertically upward at 31 feet per second Q : Find how high the ball will go. A : v = 31 G"' 31. 5 Find ( V ** 2) I (2 * G) That gives the height reached by the ball Sq = { the ball } Sea= { 31, G, 31.5, the ball} Sv = ( 31, G, 31. 5 } sf = { oooo1, oooo2, oooo3 } scf = ( 00001, 00002, 00003, the ball

Schema

C 00002 is 0000 3 feet per second squared The ball is thrown vertically upward at 00001 feet per second Q Find how high the ball will go A V· 00001 00002 · 00003 Find (V ** 2) I (2 * 00002) That gives the height reached by the ball

6. 2 Extrapolation from Schemata

Given a stimulus, S, one may compare it with the input component of a schema K [Sq, S cf , C 1 , Q, A' ] · The comparison performed by the processor consists of two steps: (a) linear mapping of S onto Q, and (b) evaluation of the match. Consider two strings of words and symbols

The linear mapping of Y 1 Y 2 Y 3 ··· Y n onto zl z 2 z~ ·· zm is performed as follows:

1. The mapping should proceed from y 1 to y n ·
2. 2.. If it is otherwise permissible to. map yi onto either zj or zk, j < k, Y i should be mapped onto Zj ·
3. If Y i is mapped onto Z j, no mapping of the form yk- zl lS permitted if k> i while 1 < j.
4. Pursuant to the conditiona stated above, Yi may be mapped onto Zj if Yi and Z j are identical.
5. Pursuant to the first three conditions, Yi may be mapped onto Zj irrespe­ ctive of their being identical, if they are both nwnbers, neither being a formal variable.

The mapping will not be complete after the exhaustive application of the five rules list­ ed above. Considering the example referred to in Section 6. 1 , the part o'f the mapping pe rfo r­ med according to these rules is shown here:

However, it is possible at this stage to estimate the degree to which Q resembles S. A useful index of the match is found as follows:

1. Assign to every element in Q, but not in Sq, the weight 1.
2. As sign to every element in Sq the weight o. 25.
3. Make a weighted count of all elements of S successfully mapped onto some elements of Q at this stage. Let this be R 1 ·
4. Let a weighted count of all elements in Q be R 2 ·
5. R 1 IR2 is the match index.

By using this match criterion, the schemata most suitable to the task at hand are selected and tried one by one for applicability. For instance, if the task is to create a response to

'Find how high the stone will go 1

the paradigm listed in Section 6. 1 could be selected.

How does one use the paradigm in the new situation? The linear mapping of S onto Q creates a one-to-one correspondence between elements which occur inS with their substitute elements in Q. The mapping can now be comp­ leted by an interpolation process (see (1 7) for a flow-chart of this process, as well as for details in general. In certain places, however, (l 7) differs in formulation).

On completion of the mapping, a one­ to-one correspondence can be set up between strings in Sq which occur in Q and their substi­ tutes, Sq , which occur inS. For instance, in the above example, the single member of Sq · 'the ball', can be put in correspondence with 'the stone' inS. Uniformly substituting mem­ bers of Sq occurring inC' of the schema by corresponding members of Sq , a modified context C" is created. In the above example, t:'" consists of two strings:

00002 is 00003 feet per second squared The stone is thrown vertically upward at 00001 feet per second squared

The modified context C" shows the structure of sentences to be identified in the sentential store, if the chosen schema is to be useful in creating a response . The processor searches this store to locate sentences which match the strings of C" , using the linear mapp­ ing technique described above. If matching sentences are not found, the processor attempts t o use another paradigm. If matching sentences are found, the mapping technique described identifies substrings which occur in the place o! the formal variables Sf. A one-to-one cor­ respondence is created between elements of Sf and their substitutes, which constitute the set Su.

At this stage, the processor creates t~ response by uniformly substituting elements of Sf occurring in A' by the corresponding elements of the set Su·

If no suitable schema is found for a given stimulus 5, it is treated as informative input to be directly sent to the sentential store. On the other hand, if a schema is found, the computed response is output string by string. After each string is output in this manner, it is re-presented to the processor, as an .inter­ nal stimulus. For instance, if the computed response has the string 'V:or41' in it, it will be re-presented as an internal stimulus. Failing to find a suitable schematized paradigm to gui­ de the re ~ ponse to this new stimulus, the pro­ cess o r will file away 'V,.41 1 in the sentential store for later use.

If the command

becomes an internal stimulus, the processor could find a suitable schema to guide it in per­ forming this sub-task.

7. Design and hnplementation of the Problem­ solver

The simple examples presented in Section 6 show how the paradigmatic creation of a direct, simple response is possible at a very low level of operation. A stimulus of any complexity results in internal stimuli, and a whole hierarchy of schemata is brought into play. This is true not only in numerical prob­ lem-solving, but also in the interpretation of complex sentences, which is a kind of 'problem­ solving' in itself.

Fig. 2 shows the problem-solver whi::h consists of the rudimentary processor shown in Fig. 1 along with push-down stores necessary for the recursive application of schemata. The interpretf't" is a simple speedup device which responds to frequent forms of internal stimuli. Though whatever it does can, in principle, be performed in the paradigmatic mode, it increa­ ses efficiency and reduces storage requiremerts by interpreting a set of simple stimuli very economically. Some of the forms it handles, using a finite state grammar, are*

Step numbers may be incorporated in the strings constituting a paradigmatic responee. The 'aoto' statements of the interpreter's lan­ guage essentially allow jumping and looping within a sequence of internal stimuli essentially constituting a program.

The stimulus 'what is A 1 would be responded to by locating a 1 sentence 1 of the form 'A = -- · in the sentential store and keep­ ing the value ready for further use. The inter­ preter provides for the use of 1 that 1 , 1 the result', 1 it' and 'result' to refer to any such quantity arising from the preceding operation. The interpreter used incorporates many sophi­ stications, and descriptions of these. may be found in (1 7). For instance, the terms in the interpreted statements could be numbers such as 3. 61 or 4, or a string of words such as 'the weight of the stone'. In the last case, the num­ erical value auociated with the string would be searched for in the sentential store. Units may follow terms.

*Following standard linguistic convention, alt­ ernatives appear within braces, while optional fragments appear within brackets.

The sentential store and the store for schemata along with necessary indexes. are accommodated in nearly 500,000 words of a disc-file memory. A description of indexing and retrieval techniques specially developed for this work may be found in {18).

A number of problems solved by this system, along with the guiding paradigms may be found in (17). An example is listed here. (deletions, employed to save space here, are marked by '· ·· ').

PROBLEM SOLVED

C - 5 GRAM S OF SAND ARE AT 80 DEGREE S CENTIGRADE

60 GRAMS OF KERC\SENE ARE AT 10 DEGREE S CENTIGRADE

THE SPECIFIC HEAT OF SAND IS O. 2

THE SPECIFIC HEAT OF KERC\SENE IS 0.4

THE SAND AND THE KERC\SENE ARE BROUGHT TOGETHER

Q - WHAT IS THE FINAL TEMPERATURE ATTAINED

Final

Output -

FlliD THE HEAT IN THE KERC\SENE,

THAT IS THE HEAT IN THE KEROSENE THE HEAT IN THE KERC\SENE· 240.000

MULTIPLY 60 BY o. 4 MULTIPLY THE RESULT BY 10 FIND THE HEAT IN THE SAND

THE HEAT IN THE SAND= 80.000

ADD IT TO THE HEAT IN THE KEROSEN'E

THAT IS THE TOTAL HEAT

THE TOTAL HEAT= 3ZO. 000

FIND THE THERMAL CAPACITY OF THE KERC\SENE

MULTIPLY 60 BY O. 4

THAT lS THE THERMAL CAPACITY OF KERC\SENE

THE THERMAL CAPACITY OF KEROSE­ NE · 24.000

IGNORE THE TEMPERATURE - 10 DEG­ REE S CENTIGRADE

FlliD THE THERMAL CAPACITY OF THE

SAND

• IGNORE THE TEMPERATURE - 80 DEGRE­ E S CENTIGRADE
• ADD IT TO THE THERMAL CAPACITY OF THE KEROSENE
• THAT IS THE TOTAL THERMAL CAPAC­ ITY
• THE TOTAL THERMAL CAPACITY · 25.000

DIVIDE THE TOTAL HEAT BY THE TOT­ AL THERMAL CAPACITY

THE RESULT IS THE ANSWER, IN DEG­ REE S CENTIGRADE

THE ANSWER, IN DEGREE S CENTIGRA­ DE · ll. 800

PARADIGMS USED

• C - 75 GRAMS OF CLAY ARE AT lO DEGREE S CENTIGRADE

THE SPECIFIC HEAT OF CLAY IS 0, 5 Q- FIND THE HEAT IN THE CLAY

A - 1. MULTIPLY 75 BY 0, 5 Z. MULTIPLY THE RESULT BY lO 3. THAT IS THE HEAT IN THE CLAY

~ - 75 GRAMS OF METAL ARE AT ZO DEG­ REE S CENTIGRADE THE SPECIFIC HEAT OF METAL IS 0, 5

Q - FIND THE THERMAL CAPACITY OF THE METAL

• A - 1. MULTIPLY 75 BY 0, 5

Z. THAT IS THE THERMAL CAPACITY OF THE METAL

1. IGNORE THE TEMPERATURE - ZO DEGREE S CENTIGRADE

'C' - THE IRON FILINGS AND WATER ARE BROUGHT TOGETHER

Q - WHAT IS THE FINAL TEMPERATURE ATTAINED

• A - 1. FIND THE HEAT IN THE WATER

Z. FIND THE HEAT IN THE IRON FILINGS

3. ADD IT TO THE HEAT IN THE WATER

1. THAT IS THE TOTAL HEAT
2. FIND THE THERMAL CAPACITY OF THE WATER
3. 6, FIND THE THERMAL CAPACITY OF THE IRON FILING S
4. ADD IT TO THE THERMAL CAPACITY OF THE WATER
5. 8, THAT IS THE TOTAL THERMAL CAPACITY
6. DIVIDE THE TOTAL HEAT BY THE TOTAL THERMAL CAPACITY
7. 10, THAT IS THE ANSWER, IN DEGREES CENTIGRADE

8, Discussion

A number of questions can be raised about this approach, Some of these questions are answered here and certain lines for possi­ ble developments in consonance with this appro­ ach are discussed,

8, 1 Nature of the Language Provided for

Does the system at least provide for the use of phrase structure languages?

It will be apparent that we are not wor­ king with a slot-and-filler model, where the fillers are single words, Since a variable could be any string of words and symbols, there exists the possibility that such fillers themselves will have a complex structure, Fillers usually get transferred from the stim­ ulus to the internal responses, Incorporation of a filler with a complex structure modifies the internal response and increases the proce­ ssing it will go through. But eventually, any necessary breaking up of phrases does get carried out.

Further, it can be seen that there is provision for handling surface transformations. If the system can handle a question of the form 'Does N divide M? 1 1 we can provide a new paradigm that will transform an equivalent question to this form:

c

Q

X

Is M divisible by N?

Does N divide M?

8, z. Completeness and Contradictions

It is reasonable to ask of a problem­ solving system i! it guarantees the solution of any given problem belonging to some class of problems. Can it give answers which contra­ diet each other? Can the problem-solver go into an endless loop in response to any given problem?

The system described here can exec­ ute an algorithmic process and in that trivial sense, it can guarantee solutions to any problem in a class which is algorithmically solvable. Operating in areas which cannot be wrapped up in formal systems, it can give contradictory s elutions. It can go into an endless loop unless the paradigms provided indicate methods of avoiding such a possibility.

8. 3 Possible Developments

Useful minor additions would include a random number generator accessible in the interpreter's language and a name generator for creating arbitrary names for local variables. 'Let that be X', 'Let that beY' etc. are suffici­ ent for handling small problems, but one needs a name generator for larger problems.

The system presently handles words as units and cannot separate a word into its root and word-ending. A provision to handle this would be useful. It would also be useful to have a good evaluator for arithmetic expre­ ssions, instead of depending on the crude prog­ rarruning language of the interpreter. A very sophisticated addition would be a provision which will enable the system to write a few lines in a programming language such as

FORTRAN and have them executed.

It would be very useful to provide for on-line interaction between the system and a communicant. This ought to be implemented easily by incorporating two new primitives in the interpreter's repertoire, for on-line input and output.

Typical symbol manipulation by a stud ­ ent (for example, that involved in symbolic integration or algebraic factorization) is often performed using an external aid such as a blackboard, or pencil and paper. It would be useful to provide a two dimensional array on which the system could write, sense, and mani­ pulate alphanumeric expressions. With anum­ ber of manipulation primitives built into the interpreter's repertoire, this array could be

used as an internal blackboard.

Such a 'blackboard' will also enable the writing, examination and 'editorial' mani­ pulation of long sentences. This might, to some extent, bridge the difference in complexity between the sentences used by the system and those found in written human communication.

Many of the facilities mentioned here are available in standard programming langu­ ages, but it would be interesting to see them used by a paradigmatic problem-solver.

A more basic advance would be the development of paradigms which would lead the system to use trial and error as a learning device in solving a variety of problems. Trial episodes which end in success should be auto­ matically culled out as useful paradigms for schematization and storing. This will involve considerable addition to the system described.

Acknowledgment

This work owes much by way of guid­ ance to Professor R. Narasimhan, and without his collaboration it would not have been possible.

Professor J. R ·. Isaac provided const­ ant -encouragement and his critical interest put many ideas into perspective.

Comments of the referees on the orig­ inal draft are gratefully acknowledged.