We discuss the problem of incorporating into a heuristic theorem prover a decision procedure for a fragment of the logic. An obvious goal when incorporating such a procedure is to reduce the search space explored by the heuristic component of the system, as would be achieved by eliminating from the system's data base some explicitly stated axioms. For example, if a decision procedure for linear inequalities is added, one would hope to eliminate the explicit consideration of the transitivity axioms. However, the decision procedure must then be used in all the ways the eliminated axioms might have been. The difficulty of achieving this degree of integration is more dependent upon the complexity of the heuristic component than upon that of the decision procedure. The view of the decision procedure as a black box is frequently destroyed by the need pass large amounts of search strategic information back and forth between the two components.

Most resolution theorem provers convert a theorem into clause form before attempting to find a proof. The conventional translation of a first-order formula into clause form often obscures the structure of the formula, and may increase the length of the formula by an exponential amount in the worst case. We present a non-standard clause form translation that preserves more of the structure of the formula than the conventional translation. This new translation also avoids the exponential increase in size which may occur with the standard translation. We show how this idea may be combined with the idea of replacing predicates by their definitions before converting to clause form.

This paper presents a body of program synthesis knowledge dealing with array operations, space reutilization, the divide-and-conquer paradigm, conversion from recursive paradigms to iterative paradigms, and ordered set enumerations. Such knowledge can be used for the synthesis of efficient and in-place sorts including quicksort, mergesort, sinking sort, and bubble sort, as well as other ordered set operations such as set union, element removal, and element addition. The knowledge is explicated to a level of detail such that it is possible to codify this knowledge as a set of program synthesis rules for use by a computer-based synthesis system. The use and content of this set of programming rules is illustrated by the methodical synthesis of bubble sort, sinking sort, quicksort, and mergesort.

It is essentially a Horn clause theorem prover augmented with a special inference rule for'dealing with

"Computing can change our ways of thinking about many things, mathematics, biology, engineering, administrative procedures, and many more. But my main concern is that it can change our thinking about ourselves: giving us new models, metaphors, and other thinking tools to aid our efforts to fathom the mysteries of the human mind and heart. The new discipline of Artificial Intelligence is the branch of computing most directly concerned with this revolution. By giving us new, deeper, insights into some of our inner processes, it changes our thinking about ourselves. It therefore changes some of our inner processes, and so changes what we are, like all social, technological and intellectual revolutions." This book, published in 1978 by Harvester Press and Humanities Press, has been out of print for many years, and is now online, produced from a scanned in copy of the original, digitised by OCR software and made available in September 2001. Since then a number of notes and corrections have been added. Atlantic Highlands, NJ: Humanities Press.

In English, "1ikewise", "too", "similarly", etc., followed optionally by a preposition and then by a noun phrase indicate that the role filled by the new noun phrase in a previously mentioned predicate is a non-subject one.

This view is nominalism, and leads to a quite different sort of semantic intuition, in which, for example, red denotes not a property of physical individuals, but the (rather disconnected) individual consisting of all pieces of red stuff in the world. Other similar confusions are also made. For example, logic is no worse (and no better) than Conceptual Dependency at representing warm, human facts about people hitting each other, (4) Logic doesn't give "the ultimate in decomposition of knowledge". Winograd, in his widely cited discussion [23] of the assertional/procedural controversy, draws a distinction between logic's atomistic view of knowledge, in which a representation is seen as a set of separate disconnected facts, and the proceduralist's holistic view in which interactions between procedures have prominence. But this is exactly the opposite of the truth.

Reprinted as Chapter 3 (pp.250-271) of Webber & Nilsson, Readings in Artificial IntelligenceElcock, E. W. and Michie, D. (Eds.), Machine Intelligence 8, pp. 94-€“138. Ellis Horwood.

Earlier work by Newell, Simon, Shaw, and Gelernter in the middle and late 1950s emphasized the heuristic approach, but the weight soon shifted to various syntactic methods culminating in a large effort on resolution type systems in the last half of the 1960s. It was about 1970 when considerable interest was revived in heuristic methods and the use of human supplied, domain dependent, knowledge. It is not my intention here to slight the great names in automatic theorem proving, and their contributions to all we do, but rather to show another side of it. For recent books on automatic theorem proving see Chang and Lee [19], Loveland [44], and Hayes [31]. Also see Nilsson's recent review article [61]. The word "resolution" has come to be associated with general purpose types of theorem provers which use very little domain dependent information and few if any special heuristics besides those of a syntactic nature. It has also connoted the use of clauses and refutation proofs. There was much hope in the late 60's that such systems, especially with various exciting improvements, such as set of support, model elimination, etc., would be powerful provers. But by the early 70's there was emerging a belief that resolution type systems could never really "hack" it, could not prove really hard mathematical theorems, without some extensive changes in philosophy.

EPISTEMOLOGICAL PROBLEMS OF ARTIFICIAL INTELLIGENCE John McCarthy Computer Science Department Stanford University Stanford, California 94305 Introduction In (McCarthy and Hayes 1969), we proposed dividing the artificial intelligence problem into two parts - an epistemological part and a heuristic part. This lecture further explains this division, explains some of the epistemological problems, and presents some new results and approaches. The epistemological part of Al studies what kinds of facts about the world are available to an observer with given Opportunities to observe, how these facts can be represented in the memory of a computer, and what rules permit legitimate conclusions to be drawn from these facts. It leaves aside the heuristic problems of how to search spaces of possibilities and how to match patterns. Considering epistemological problems separately has the following advantages: I. The same problems of what information is available to an observer and what conclusions can be drawn from information arise in connection with a variety of problem solving tasks. Recently we have found that introducing concepts as individuals makes possible a first order logic expression of facts usually expressed In modal logic but With important advantages over modal logic - and so far no disadvantages.