All Al programs are essentially reasoning programs. And, to the extent that they reason well about a problem area, all exhibit some expertise at problem solving. Programs that solve the Tower of Hanoi puzzle, for example, reason about the goal state and the initial state in order to find'expert-level' solutions. Unlike other programs, however, the claims about expert systems are related to questions of usefulness and understandability as well as performance. We can distinguish expert systems from other Al programs in the following respects: Utility Performance Transparency Designers of expert systems are motivated to build useful tools in addition to constructing programs that serve as vehicles for AI research.

Machine intelligence, more commonly known by the misnomer artifical intelligence, is now about twenty-five years old as a scientific field. In contrast with early predictions, its practical applicability has been frustratingly slow to develop. It appears, however, that we are now (finally!) on the verge of practicality in a number of specialities within machine intelligence more or less simultaneously. This can be expected to result in the short term in a qualitative shift in the nature of the field itself, and to result in the longer term in a shift in the way certain industries go about their business. Machine Intelligence Corporation (MIC) was founded in 1978 as a vehicle for bringing the more practical aspects of the field into widespread use.

We propose a computational model for interpreting line drawings as threedimensional surfaces, based on constraints on local surface orientation along extremal and discontinuity boundaries. Specific techniques are described for two key processes: recovering the three-dimensional conformation of a space curve (e.g., a surface boundary) from its two-dimensional projection in an image, and interpolating smooth surfaces from orientation constraints along extremal boundaries.

A programming language based on sets; motivation and examples.

A programming language based on sets; motivation and examples.

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

A technique that has proved useful in shortest path and other discrete optimization computations has been bi-directional search. The method has been well tested in the two-node shortest-path problem providing substantial computational savings. A natural impulse is to extend its benefits to heuristic search. In the uni-directional algorithms, the search proceeds from an initial node forward until the goal node is encountered. Problems for which the goal node is explicitly known can be searched backward from the goal node. An algorithm combining both search directions is bi-directional. This method has not seen much use because book-keeping problems were thought to outweigh the possible search reduction. The use of hashing functions to partition the search space provides a solution to some of these implementation problems.

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.