The frame problem in representing natural-language information is discussed. It is argued that the problem is not restricted to problem-solving-type situations, in which it has mostly been studied so far, but also has a broader significance. A new solution to the frame problem, which arose within a larger system for representing natural-language information, is described. The basic idea is to extend the predicate calculus notation with a special operator, Unless, with peculiar properties. Some difficulties with Unless are described.

A paradigm enabling heuristic problem solving programs to exploit an analogy between a current unsolved problem and a similar but previously solved problem to simplify it s search for a solu­tion is outlined. It is developed in detail for a first-order resolution logic theorem prover. Descriptions of the paradigm, implemented LISP programs, and preliminary experimental results are presented. This is believed to be the firs t system that develops analogical information and exploits it so that a problem-solving program can speed its search.IJCAI-71, British Computer Society, London, 1971. Revised version in Artificial intelligence 2(2):147- 178, fall, 1971.

Session No. 2 Applications 59 CHALLENGE TO ARTIFICIAL INTELLIGENCE: PROGRAMMING PROBLEMS TO BE SOLVED Abstract J. E. Sammet IBM Corporation Cambridge, Mass. U. S. A. This paper is in the nature of a challenge to artificial intelligence experts. It suggests that the techniques of artificial intelligence should be applied to some realistic problems which exist in the programming and data processing fields. After a brief review of the little related existing work which has been done, the characteristics of programming problems which make them suitable for the application of artificial intelligence techniques are given. Specific illustrations of problems are provided under the broad categories of data structure and organization, program structure and organization, improvements and corrections of programs, and language. Descriptors artificial intelligence applications programming heuristic techniques I. INTRODUCTION It has been over 15 years since computers were first used for anything resembling "artificial intelligence". The pioneering work of Newell, Shaw, and Simon on proving theorems in the propositional calculus is so well known as not to need discussion for the people knowledgeable in the field of artificial intelligence.

Ph.D. thesis, Edinburgh University. This thesis is concerned with algorithms for generating generalisations-from experience. These algorithms are viewed as examples of the general concept of a hypothesis discovery system which, in its turn, is placed in a framework in which it is seen as one component in a multi-stage process which includes stages of hypothesis criticism or justification, data gathering and analysis and prediction. Formal and informal criteria, which should be satisfied by the discovered hypotheses are given. In particular, they should explain experience and be simple. The formal work uses the first-order predicate calculus. These criteria are applied to the case of hypotheses which are generalisations from experience. A formal definition of generalisation from experience, relative to a body of knowledge is developed and several syntactical simplicity measures are defined. This work uses many concepts taken from resolution theory (Robinson, 1965). We develop a set of formal criteria that must be satisfied by any hypothesis generated by an algorithm for producing generalisation from experience. The mathematics of generalisation is developed. In particular, in the case when there is no body of knowledge, it is shown that there is always a least general generalisation of any two clauses, in the generalisation ordering. (In resolution theory, a clause is an abbreviation for a disjunction of literals.) This least general generalisation is effectively obtainable. Some lattices induced by the generalisation ordering, in the case where there is no body of knowledge, are investigated. The formal set of criteria is investigated. It is shown that for a certain simplicity measure, and under the assumption that there is no body of knowledge, there always exist hypotheses which satisfy them. Generally, however, there is no algorithm which, given the sentences describing experience, will produce as output a hypothesis satisfying the formal criteria. These results persist for a wide range of other simplicity measures. However several useful cases for which algorithms are available are described, as are some general properties of the set of hypotheses which satisfy the criteria. Some connections with philosophy are discussed. It is shown that, with sufficiently large experience, in some cases, any hypothesis which satisfies the formal criteria is acceptable in the sense of Hintikka and Hilpinen (1966). The role of simplicity is further discussed. Some practical difficulties which arise because of Goodman's (1965) "grue" paradox of confirmation theory are presented. A variant of the formal criteria suggested by the work of Meltzer (1970) is discussed. This allows an effective method to be developed when this was not possible before. However, the possibility is countenanced that inconsistent hypotheses might be proposed by the discovery algorithm. The positive results on the existence of hypotheses satisfying the formal criteria are extended to include some simple types of knowledge. It is shown that they cannot be extended much further without changing the underlying simplicity ordering. A program which implements one of the decidable cases is described. It is used to find definitions in the game of noughts and crosses and in family relationships. An abstract study is made of the progression of hypothesis discovery methods through time. Some possible and some impossible behaviours of such methods are demonstrated. This work is an extension of that of Gold (1967) and Feldman (1970). The results are applied to the case of machines that discover generalisations. They are found to be markedly sensitive to the underlying simplicity ordering employed.

It is shown that any recognition problem solved by a polynomial time-bounded nondeterministic Turing machine can be "reduced" to the problem of determining whether a given propositional formula is a tautology. Here "reduced" means, roughly speaking, that the first problem can be solved deterministically in polynomial time provided an oracle is available for solving the second. From this notion of reducible, polynomial degrees of difficulty are defined, and it is shown that the problem of determining tautologyhood has the same polynomial degree as the problem of determining whether the first of two given graphs is isomorphic to a subgraph of the second. A method of measuring the complexity of proof procedures for the predicate calculus is introduced and discussed.

The problem we consider in this paper is that of discovering formal rules which will enable us to decide when a question posed in English can be answered on the basis of one or more declarative English sentences. To illustrate how this may be done in very simple cases we give rules which translate certain declarative sentences and questions involving the quantifiers'some', 'every', 'any', and'no' into a modified first-order predicate calculus, and answer the questions by comparing their translated forms with those of the declaratives. We suggest that in order to capture the meanings of more complex sentences it will be necessary to go beyond the first-order predicate calculus, to a notation in which the scope of words other than quantifiers and negations is clearly indicated. We conclude by describing a notational form for connected sentences, which seems to be a natural extension of Chomsky's'deep structures'.

Given P {P1,.. P„} as input, set j 0, 00 8 (the identity substitution),

In this paper, we develop the algorithm, given in Plotkin (1970), for findingthe least generalization of two clauses, into a theory of inductive generalization.The types of hypothesis which can be formed are very simple. They allhave the form: (x)Px --> Qx.We have been guided by ideas from the philosophy of science, followingBuchanan (1966). There is no search for infallible methods of generatingtrue hypotheses. Instead we define (in terms of first-order predicate calculus)the notions of data and evidence for the data. Next, some formal criteria areset up for a sentence to be a descriptive hypothesis which is a good explanationof the data, given the evidence. We can then look for the best such hypothesis.Machine Intelligence 6

In Linguaggi nella Societ`a e nella Tecnica, pp. 189– 224. Edizioni di Comunit`a.

Kuhn (1962) has persuasively argued that science progresses by means of its paradigms--its models of the general nature of a research area--and that at the frontiers of research the primary quest is for a good paradigm. The small frontier outpost of language data processing has been characterized by an intensive seeking for a paradigm suitable to guide its researchers as they survey the complex topography of natural language structures. The earliest paradigm--one that led mechanical translators and early information retrievalists into a hopeless cul-de-sac--was that words (i.e.