K3 Th is a statement of facts and theories relevant to all the ei.

Spectra 70 / 46 and the IBM 360/50, that performs many second-order inferences in addition to carrying out first-order'resolutions' on Skolemized disjunctive formulae. The second-order aspect of the program is represented by an extended matching procedure, which operates in conjunction with rules for lambda abstraction and application, and for existential generalization and instantiation. These rules abstract properties from first-order formulae and apply axioms such as mathematical induction to these properties, thereby generating new second-order formulae as well as first-order formulae that could not have been produced by the resolution method alone. The mechanization of second-order logic is of potential usefulness in the areas of deductive question answering, illustrated by an example, and to the proving of formal properties of programs. Among the more interesting recent developments in the theory and practice of automatic theorem proving are the incorporation of formal techniques such as J. A. Robinson's resolution method into the'deductive sections' of question-answering and problem-solving systems (Chadwick et al. 1969, Green 1969), the solution of previously'open' problems (Guard et a/.

THE FRAME PROBLEM One of the central principles upon which intelligent devices seem to operate is that of maintaining internal models of their external environments. In artificial systems which have been constructed to date various representations for this internal model have been used; but in every nontrivial case the need arises to consider the effect, upon the structure of the model, of the performance by the system of actions in the external world, so that their potential consequences may be reckoned. How difficult this is, depends upon both the complexity of the model and its method of representation. In particular, it is usually easy when the problem is posed in the classical heuristic search paradigm, and the data structures used to represent static configurations of the puzzle are relatively unproblematic (arrays, lists, and so on). For in this case [see, for instance, Manna (1970) and Pikes (1970) for examples] one can use the ordinary device of assignment to model the changes in the world.which The lack of side-effects reflects the simplicity of the physics which such models embody. This limitation to elementary forms of interaction is not, of course, intrinsic to the heuristic search method; but when more complex models are constructed it becomes less trivial to pursue the consequences of performing an action. The use of assignment to portray the doing of actions does seem to presuppose a trivial physics. Another method of constructing microcosms is to use a logical language to describe the real world (McCarthy 1959, McCarthy and Hayes 1969). This approach is more general than the heuristic search method (but the latter -- when it has sufficient expressive power -- wins at present by its computational advantage). The key idea is to use expressions denoting situations to separate out assertions according to which (static) state of the world they purport to describe. Assertions mentioning several different situations can then be used to describe dynamical laws which move us from one situation to another. But in some ways the resulting sharp separations between states of affairs are an embarrassment. For if we distinguish two situations s1 and s2, then from the fact, if such it be, that a predicate p is true of Si, nothing whatever follows concerning s2. And this is true even when s2 is directly associated with sl. Say s2 results from s1 by the performance of some action: s2 do (a, si) then no matter how remote -- speaking intuitively -- the connection between the property p and the action a, it still does not follow that p is true of s2. If we want it to so follow we must state this explicitly. Now, unfortunately, there are innumerable facts which might remain unchanged when actions are performed. So instead of writing a law of motion' in the form A(s) B(do(a, s)) where A and B are fairly short expressions, we are apparently obliged to list systematically all conceivable facts which are not changed.

In particular, we consider situations where functional properties of a computer program are given in the form of explicit input-output correspondences, and the problem is to synthesize (to form) a program, in a given programming language, that satisfies the given correspondences. The motivation behind the work is twofold: (1) to explore and elucidate schemes for solving formation problems by machine, and (2) to gain further insight into questions of representation in problem solving, to examine their nature and significance in the context of formation procedures, and to clarify the role of models in the solution of formation problems. The present approach to program formation derives from work done several years ago (Amarel 1962a, 1962b), in which we found it conceptually fruitful to view the automatic formation of computer programs that is based on computational examples as a case of automatic theory formation. A theory in an empirical science emerges from a body of observed correspondences and has the function of an intellectual mechanism for explanation and prediction. The theory evolves from a succession of hypotheses that are tested against experience, and attains a degree of stability once it explains with reasonable consistency the given body of observations. The form of a hypothesis capable of emerging in a scientific culture depends on the language, the basic concepts, and the schemas that are available in the culture.

This paper describes a program for extracting an accurate outline of a man's head from a digital picture. The program accepts as input digital, grey scale pictures containing people standing in front of various backgrounds.

We have written a program which will recognize a range of objects including a cup, a wedge, a hammer, a pencil, and a pair of spectacles. A visual image, represented by a 64.x 64 array of light levels, is first partitioned into connected regions. These regions are chosen to have welldefined edges. Having chosen the regions, the program then computes properties of and relations between regions. Properties include shape as defined by Fourier analysis of the s--tfr equation of the bounding curve. A typical relation between regions is the degree of adjacency. Finally, the program matches the actual relational structure of the regions of the picture with ideal relational structures representing various objects, using a heuristic search procedure, and selects that object whose relational structure best matches the actual picture. INTRODUCTION In November 1969, a Mark i robot device (Barrow and Salter 1970) was connected on-line to the ICI, 4130 computer of the Department of Machine Intelligence and Perception, University of Edinburgh.

We describe the analysis of visual scenes consisting of black on white drawings formed with curved lines, depicting familiar objects and forms: houses, trees, persons, and so on; for instance, drawings found in coloring books. The goal of such analysis is to recognize (by computer) such forms and shapes when present in the input scene; that is, to name (correctly) as many parts of the scene as possible: finger, hand, girl, dance, and so on. Complications occur because each input scene contains several such objects, partially occluding each other and in varying degrees of orientation, size, and so on. The analysis of these line drawings is an instance of'the context problem', which can be stated as'given that a set (a scene) is formed by components that locally (by their shape) are ambiguous, because each shape allows a component to have one of several possible values (a circle can be sun, ball, eye, hole) or meanings, can we make use of context information stated in the form of models, in order to single out for each component a value in such manner that the whole set (scene) is consistent or makes global sense?' Thus, shape drastically limits the values that a component could have, and further disambiguation is possible only by using global information (derived from several components and their inter-relations or inter-connections) under the assumption that the scene as a whole is meaningful. This paper proposes a way to solve'the context problem' in the paradigm of coloring book drawings. We have not implemented this approach; indeed, a purpose of this paper is to collect criticisms and suggestions. INTRODUCTION 1.1 Statement of the problem An input picture is read into a computer. We would like to analyze it. The input picture The input picture consists of a line drawing (black curved thin lines on white paper) containing familiar objects [figure 1(a)]; one could think of drawings in coloring books for children. The objects forming the picture should be drawn correctly and accurately: no intentional distortions, caricatures, or humanizations of animals (figure 2) will be allowed. Figure 2. Line drawings containing distortions, caricatures, comic strips, humanized animals, and so on, will not be accepted. Thus, it can be said that the class of input pictures we want to analyze is that found in coloring books, except distortions. We could think of a person looking at the input data [figures 1(a) or 1(b)] and saying: there is a straight line from point (30, 40) to point (67, --18.5), The input picture [figure 1(a)] is stored initially in the memory of the computer as a collection of black points (specified by their two-dimensional coordinates) closely spaced along each black line [figure 1(b)]. We will assume that: (a) The points are uniformly spaced along the lines of the drawing.

As a minimum we should at least be better able to decide when sentences from a'polyhedral language' or'smooth language' are

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'. INTRODUCTION In this paper we shall consider the problem of when an English sentence, or a series of sentences, provides enough information to answer a question, also posed in English.

In order to be able to view the situation objectively we feel that it would be useful to preface this with a historical review of the development of ideas in this twenty-year-old field. By considering the most important ideas and techniques that are employed in the (currently) best program available, we hope to convince the reader that progress has been very slow despite the multiplicity of programs (and their associated literature) which have appeared since 1950. HISTORICAL REVIEW The most important paper that has appeared on the subject of computer chess is one written by Claude Shannon in 1948 and published two years later (Shannon 1950). Shannon's paper does not describe an actual program, but offers many suggestions for those who are interested in writing one. In this respect Shannon's paper may be compared with one by Jack Good which was also full of sound ideas which could well be included in a successful chess program (Good 1967). Shannon stressed the importance of having a good evaluation function. The features which he considers necessary for inclusion in the evaluation function included material, mobility, five aspects of pawn-structure, four of the positions of pieces, and four of commitments of pieces, attacks and options. He appreciated that such an evaluation function should be used only in the middle-game, and that different principles applied to the opening and endgame phases of chess. He suggested that the values of the coefficients of the function should be determined by'some experimental procedure', and the fact that this statement has never been followed in practice is very surprising.