The solution to this simple problem would then guide the solution of the original problem. Minsky (1961) has discussed complex planning of this'homomorphic model' type, and has stressed the potential reduction in total search effort to be won. In the same paper he has also considered the use of semantic models' as a form of complex planning in a mathematical context. The successful geometry theorem-proving program of Gelernter (1959), which used a diagram' to test the validity of propositions, is a wellknown example of this form of planning. Recently Sandewall (1969) has defined a Planning Problem Solver (P P This is an attempt to explore in detail complex planning of the homomorphic model' type as applied to the

A formal description is given of GT 4, a revised and extended version of the Graph Traverser. Methods are described whereby GT4 can improve its performance at run time (a) by automatic optimization of parameters used by the evaluation function and (b) by dynamic re-ordering of operators. Neither method depends upon there being any successful searches in the program's past experience of a given problem. The essential feasibility of both approaches has been validated in experimental tests using sliding block puzzles. Two planned extensions, 'local smoothing' and'regionalization' are described. INTRODUCTION The Graph Traverser (Doran and Michie 1966), and subsequent work based on it, represents an attempt to adapt game-playing methods, particularly those of Samuel (1959), to automatic problem-solving. The design objective is not the simulation of human problem-solving as a study in psychology, but rather to provide an efficient general-purpose search procedure appropriate to non-numerical problem domains. There is a parallel with the development of direct search techniques for numerical function minimization, for example pattern search (Hooke and Jeeves 1961), simplex (Spendley, Hext and Himsworth 1962, Nelder and Mead 1965).

The equivalence problem for program schemes, or for programs, is reduced to the proving of a theorem in second-order logic. This work extends Manna's first-order logic reductions. Some examples of the technique are given together with a suggested method for obtaining proofs in special cases by firstorder methods. INTRODUCTION Several workers in recent years have considered using techniques and ideas of various mathematical theories of computation for proving interesting results about computer programs. This paper is concerned with two of these approaches.

F(n,$) as introduced here corresponds to A.N.Prior's (1957, 1968) expression Fir.

R.M.BURSTALL 373 23 Assertions: programs written without specifying unnecessary order.

INTRODUCTION Attempts to write'intelligent' computer programs have commonly involved the choice for attack of some particular aspect of intelligent behaviour, together with the choice of some relevant task, or range of tasks, which the program must perform. The emphasis is sometimes on the generality of the program's ability, sometimes on the importance of the particular task which it can perform. Well-known examples of such programs are Newell, Shaw, and Simon's General Problem Solver (1959; see also Ernst and Newell, 1967), which is applicable to a wide range of simple problems, Samuel's checker (draughts) playing program (1959, 1967), and the program written by Evans (1964), which solves geometric analogy problems. However, there is another approach to the goal of machine intelligence which stresses the relationship of an organism to its environment and which sets out from the start to understand what is involved in this relationship. Long ago Grey Walter (1953) experimented with mechanical'tortoises' which could range over the floor in a lifelike manner. Toda (1962), in a whimsical and illuminating paper, has discussed the problems facing an automaton in a simple artificial environment. Friedman (1967), a psychologist, has described a computer simulation of instinctive behaviour involving an automaton equipped with sensory and motor systems. Sandewall (1967) has gone deeply into an automaton/environment relationship with a rather more formal approach. This list is far from complete. In particular, robots of various kinds are under construction at a number of research centres, notably at the Stanford Research Institute (Nilsson and Raphael, 1967). The reader may find it helpful to meditate on the situation of, say, a rat in a cage, as seen by the rat.

The general problem of re-Presentation is concerned with the relationship between different ways of formulating a problem to a problem solving system and the efficiency with which the system can be expected to find a solution to the problem. An understanding of the relationship between problem formulation and problem solving efficiency is a prerequisite for the design of procedures that can automatically choose the most appropriate' representation of a problem (they can find a point of view' of the problem that maximally simplifies the process of finding a solution). Many problems of practical importance are problems of reasoning about actions. In these problems, a course of action has to be found that satisfies a number of specified conditions. A formal definition of this class of problems is given in the next section, in the context of a general conceptual framework for formulating these problems for computers. Everyday examples of reasoning about actions include planning an airplane trip, organizing a dinner party, etc. There are many examples of industrial and military problems in this category, such as scheduling assembly and transportation processes, designing a program for a computer, planning a military operation, etc. The research presented in this paper was sponsored in part by the Air Force Office of Scientific Research, under Contract Number A F49(638)-1184. Part of this work was done while the author was on a visiting appointment at the Computer Science Department of the Carnegie Institute of Technology, Pittsburgh, Pa.

Networks as models of word storage: G. R. Kiss

I shall discuss automatic methods of search for solutions in problems susceptible of a particular formal representation, namely that on which the Graph Traverser program (Doran & Michie 1966, and see Doran p. 105) has been based. In this representation which is essentially that of Newell, Shaw & Simon (1960) a problem consists of a set of states, one or more of which is labelled'goal', together with a rule-book. The rule-book lays down for each state what moves may be made from it to reach other, neighbouring, states. Solution consists in a demonstration that a goal state can be reached from some given initial state via a sequence of intermediate states, sometimes with the additional requirement that an actual sequence, or path, be demonstrated as part of the solution; in this last case, as in the sliding block problem discussed later, the goal (or goals) is typically specified in full as part of the statement of the problem. In other cases, where the goal is only specified in terms of some defining property (such as cost in a transportation problem, or simplicity in a problem of algebraic manipulation) we are interested solely in discovering states possessing this property, and not at all interested in the particular paths leading to them.

A digital computer program, the Graph Traverser (Doran & Michie 1966), can seek a solution to any problem which may be interpreted as that of finding a path from one specified node of a graph to another. Emphasis is placed Upon the evaluation of intermediate states of the problem (nodes of the graph) according to the extent to which they resemble the'goal' state. Sample results from first applications of the program, and possible future developments, are discussed. The program is related to other problemsolving programs. INTRODUCTION: PROBLEMS AND PROBLEM-SOLVING PROGRAMS How to travel from London to Birmingham may, in some circumstances, be a'problem'.