This paper describes some recent experiments with a computer program which is capable of useful, or at least interesting, application to a number of different problems. The program, the Graph Traverser, has been described in detail in a previous paper (Doran & Michie 1966). However, we shall here need to view the basic algorithm from a rather more general standpoint, corresponding to an actual extension in the flexibility of the program, so that a restatement of what the program can do is desirable. The Graph Traverser, which is written in Elliott 4100 Algol, is potentially applicable to problem situations which can be idealised in the following way (see for comparison Newell and Ernst 1965). There is given a set of'states', which are connected by a set of'transformations', or, as I shall call them, 'operators'. An operator will be applicable to some, but not necessarily all, of the states and two distinct operators applied to either the same or distinct states may each give the same state as end -product. Most of the concepts to be used here which are related to the use of operators were discussed in a paper by Michie (1967). This type of problem situation is represented in Figure 1 by a graph (in the mathematical sense) to which have been added various labels.

"The purpose of this paper is to clarify some basic issues of choice of representation for problems of reasoning about actions. 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."In D.Michie (Ed.), Machine intelligence 3. New York: American Elsevier,131-171

Proceedings of the IFIP Congress (2), pp 1563-1569

Wiley is a global provider of content and content-enabled workflow solutions in areas of scientific, technical, medical, and scholarly research; professional development; and education. Our core businesses produce scientific, technical, medical, and scholarly journals, reference works, books, database services, and advertising; professional books, subscription products, certification and training services and online applications; and education content and services including integrated online teaching and learning resources for undergraduate and graduate students and lifelong learners. Founded in 1807, John Wiley & Sons, Inc. has been a valued source of information and understanding for more than 200 years, helping people around the world meet their needs and fulfill their aspirations. Wiley has published the works of more than 450 Nobel laureates in all categories: Literature, Economics, Physiology or Medicine, Physics, Chemistry, and Peace. Wiley has partnerships with many of the world's leading societies and publishes over 1,500 peer-reviewed journals and 1,500 new books annually in print and online, as well as databases, major reference works and laboratory protocols in STMS subjects.

In Hart, J. and Takasu, S. (Eds.), Systems and Computer Science. University of Toronto Press

A recognition algorithm is exhibited whereby an arbitrary string over a given vocabulary can be tested for containment in a given context-free language. A special merit of this algorithm is that it is completed in a number of steps proportional to the “cube” of the number of symbols in the tested string. As a byproduct of the grammatical analysis, required by the recognition algorithm, one can obtain, by some additional processing not exceeding the “cube” factor of computational complexity, a parsing matrix—a complete summary of the grammatical structure of the sentence. It is also shown how, by means of a minor modification of the recognition algorithm, one can obtain an integer representing the ambiguity of the sentence, i.e., the number of distinct ways in which that sentence can be generated by the grammar. The recognition algorithm is then simulated on a Turing Machine.

The fundamental texts of the great classical period in modern logic, some of them never before available in English translation, are here gathered together for the first time. Modern logic, heralded by Leibniz, may be said to have been initiated by Boole, De Morgan, and Jevons, but it was the publication in 1879 of Gottlob Frege's Begriffsschrift that opened a great epoch in the history of logic by presenting, in full-fledged form, the propositional calculus and quantification theory. Frege's book, translated in its entirety, begins the present volume. The emergence of two new fields, set theory and foundations of mathematics, on the borders of logic, mathematics, and philosophy, is depicted by the texts that follow. Peano and Dedekind illustrate the trend that led to Principia Mathematica.

Since mid-November 1966 a chess program has been under development at the Artificial Intelligence Laboratory of Project MAC at M.I.T. This paper describes the state of the program as of August 1967 and gives some of the details of the heuristics and algorithms employed.

A series of computer programs have been written to play the board game Go-Moku. Go-Moku is played on a 19 x 19 square mesh. Player b(w) has a supply of black (white) pieces. The players take it in turns to play a piece on a mesh point. The winner is the first player to complete a 5-pattern, that is, to make up a (horizontal, vertical or diagonal) line of five and only five adjacent pieces of his colour.

The formulation of the resolution principle by J. A. Robinson (1965a) has provided the impetus for a number of recent efforts in automatic theoremproving. These programs have generated proofs of some interesting propositions of number theory, in addition to theorems of first-order functional logic and group theory. A'literal' is an n-place predicate expression or its negation F(xi, x2,.-.., x) F(xi, x2,., x „) whose arguments are individual variables, individual constants, or functional expressions. Quantifiers do not occur in these formulae, since existentially quantified variables have been replaced by functions of universally quantified ones, and the remaining variables may therefore be taken as universally quantified. For example, the number-theoretic proposition'For all x and y, if x is a divisor of y then there exists some z such that x times z equals y' may be symbolised as D(x, y)v T(x, f(x, y), y) in which D(x, y)' stands for x is a divisor of y' and 7(x, y, z)' stands for'x times y equals z'.