Department of Computer Science University of Western Ontario PART 1 In their book Mathematics and Logic Kac and Ulam (1971) comment: "The point of view as it has evolved through centuries is that one need not know what things are as long as one knows what statements about them one is allowed to make. Hilbert's famous Grundlagen der Geometrie begins with the sentence: 'Let there be three kinds of objects; the objects of the first kind shall be called "points", those of the second kind "lines", and those of third "planes". That is all, except that there follows a list of initial statements (axioms) that involve the words "point', "line" and "plane", and from which other statements involving those undefined words can now be deduced by logic alone. This permits geometry to be taught to a blind man and even to a computer!" Leaving aside the attitude implicit in Kac & Ulam's use of the word'even' in the phrase even to a computer', it has become clear that programs to prove theorems in ...

INTRODUCTION Further progress in the application of computers to many practical fields seems to depend heavily on the success in implementing learning and inductive processes within machines. For example, to develop a consultation system for medical or plant disease diagnosis, prognosis and decision making in general, it is very desirable, perhaps even necessary, to be able to'teach' the system through examples of correct and/or incorrect decisions, rather than by precisely describing the decision process in its full generality and then transforming this description into a computer program. A similar situation exists in computer chess. The development of computer programs playing at the master level (especially the end games) seems to be a formidable task if the programs are not eventually able to learn and improve on their decision making rules through the specific examples of games, rather than by being explicitly told all the rules. Due to easy access to human knowledge about chess and the relative simplicity of testing the results, chess is one of the most attractive testing domains for inductive inference programs. This report presents first results from an experiment on the application of an inductive learning program called AQVAL/1 developed at the University of Illinois, to chess end games.

I. INTRODUCTION Describing scientific theory formation as an information-processing problem suggests breaking the problem into subproblems and searching solution spaces for plausible items in the theory. A computer program called meta-DEN D RAL embodies this approach to the theory formation problem within a specific area of science. Scientific theories are judged partly on how well they explain the observed data, how general their rules are, and how well they are able to predict new events. The meta-D END RA L program attempts to use these criteria, and more, as guides to formulating acceptable theories. The problem for the program is to discover conditional rules of the form S-421, where the S's are descriptions of situations and the A's are descriptions of actions. The rule is interpreted simply as'When the situation S occurs, action A occurs'. The theory formation program first generates plausible A's for theory sentences, then for each A it generates plausible S's. At the end it must integrate the candidate rules with each other and with existing theory. In this paper we are concerned only with the first two tasks: data interpretation (generating plausible A's) and rule formation (generating plausible S's for each A). This paper describes the space of actions (A's), the space of situations (S's) and the criteria of plausibility for both. This requires mentioning some details of the chemical task since the generators and the plausibility criteria gain their effectiveness from knowledge of the task. The theory formation task As in the past, we prefer to develop our ideas in the context of a specific task area.

B.RANDELL 3 PROGRAM PROOF AND MANIPULATION 2 Some techniques for proving correctness of programs which alter data structures.

B.RANDELL 3 PROGRAM PROOF AND MANIPULATION 2 Some techniques for proving correctness of programs which alter data structures.

Oberuc 245, 249 see predicate calculus Occam's razor 271 London 24-5, 52

INTRODUCTION If let loose, resolution theorem-provers can waste time in many ways. They can continually rearrange the multiplication brackets of an associative multiplication operation or replace terms t by ones like f(f(f(t, e), e), e) where f is a multiplication function and e is its identity. Generally they continually discover and misapply trivial lemmas. Global heuristics using term complexity do not help much and ad hoc devices seem suspicious. On the other hand, one would like to evaluate terms when possible, for example we would want to replace 5 4 by 9. More generally one would like to have liberty to simplify, to factorise and to rearrange terms. The obvious way to deal with an associative multiplication would be to imitate people, and just drop the multiplication brackets. However used or abused the basic facts involved in such manipulations form an equational theory, T, that is, a theory all of whose sentences are universal closures of equations. Under certain conditions, we will be able to build the equational theory into the rules of inference. The resulting method will be resolution-like, the difference being that concepts are defined using provable equality between terms rather than literal identity. Therefore the set of clauses expressing the theory will not be among the input clauses, so no time will be wasted in the misapplication of trivial lemmas, since the rules will not waste time in this way.

INTRODUCTION In May 1971 the Mark 1.5 Edinburgh robot system went on-line as a complete hand-eye system. Two years earlier the Mark 1 device had been connected to the ic L 4130 computer of the Department of Machine Intelligence and Perception. The Mark 1 (Barrow and Salter 1970) had been little more than a semi-mobile T.V. camera, with coarse picture sampling (64 x 64 points, 16 levels), a limited range of movement over a three-foot diameter circular platform, and a pair of touch-sensitive bumpers. Within eighteen months we had developed suitable basic software, and a teachable' program capable of recognizing irregular objects via the However, the restrictions upon movement, the limited range of actions which could modify the'world', and the shortcomings of the video system, made more advanced work difficult. Plans were therefore laid for the construction of the Mark 2 device. The Mark 2 robot system will possess moderately sophisticated eyes and a hand which can manipulate objects with a reasonable degree of precision. The present equipment thus represents a useable system, not yet up to full Mark 2 specification, but considerably more useful than the Mark 1. DESIGN CONCEPTS It is important that the complete system should be as self-reliant as possible. If it depends much upon human assistance to pre-process information or to put things right when they go astray, it is all too easy in one's research to avoid the central issues of a problem, and produce a'solution' which does not survive when confronted by real situations. In the Mark 1 device we implemented a suggestion from Derek Healy that when a robot is complicated and linked to a fixed computer, and its world is simple, it is better to keep the robot still and move the world. From its own point of view, the robot cannot tell whether it or the world moves, and one can simulate free movement in a restricted area.

INTRODUCTION Research in machine vision is an important activity in artificial intelligence laboratories for two major reasons. First, understanding vision is a worthy subject for its own sake. The point of view of artificial intelligence allows a fresh new look at old questions and exposes a great deal about vision in general, independent of whether man or machine is the seeing agent. Second, the same problems found in understanding vision are of central interest in the development of a broad theory of intelligence. Making a machine see brings one to grips with problems like that of knowledge interaction on many levels and of large system organization. In vision these key issues are exhibited with enough substance to be nontrivial and enough simplicity to be tractable. Both goals are framed in terms of a world of bricks, wedges, and other simple shapes like those found in children's toy boxes. Good purposeful description is often fundamental to research in artificial intelligence, and learning how to do description constitutes a major part of our effort in vision research. This essay begins with a discussion of that part of scene analysis known as body finding. The intention is to show how our understanding has evolved away from blind fumbling toward substantive theory. Finding groups of objects and using the groups to get at the properties of their members illustrates concretely how some of the ideas about systems work out in detail. The topic of learning follows. Discussing learning is especially appropriate here not only because it is an important piece of artificial intelligence theory but also because it illustrates a particular use for the elaborate analysis machinery dealt with in the previous sections. Finally a scenario exhibits the flavor of the system in a situation where a simple structure is copied from spare parts. The body-finding story begins with an ad hoc but crisp syntactic theory and ends in a simple, appealing theory with serious semantic roots. In this the history of the body-finding problem seems paradigmatic of vision system progress in general. Adolfo Guzman started the work in this area (Guzman 1968). I review his program here in order to anchor the discussion and show how better programs emerge through the interaction of observation, experiment, and theory. The task is simply to partition the observed regions of a scene into distinct bodies.

An operator is characterized by a precondition statement describing the conditions under which it may be applied, and lists of statements describing its effects. Specifically, the effect of an operator is to remove from the model all statements matching forms on the operator's'delete list', and to add to the model all statements on the operator's'add list'.