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

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'.

We describe how to design simple contentaddressable memories, functioning in parallel, which can do this and which, in some sense, can generalise about the stored data. Secondly, we consider how certain graphical representations of data may be suitable for use in efficient serial search strategies. We indicate how such structures can be used in diagnosis when the availability or cost of tests to be applied cannot be determined in advance. The type of parallel system to be considered is to store descriptions of a set of patterns, and is then to be used to supplement an incomplete description of a newly presented pattern by matching it against those in store. If this partial description matches one or more of the stored patterns then we would like the memory to provide us with the partial description that these patterns share. If the new pattern does not match any in store then we expect that the information supplied will be according to the relationships between the pattern presented and those in store. The information that we require our memory to provide when given an incomplete description as an address is therefore more than just the response'yes' or'no'. In this respect our type of system differs from content-addressable parallel memories used in computer technology, and for the same reason its capabilities exceed that of a switching network which is designed to respond positively when the states of its input channels attain one of a number of combinations of binary values (Richards 1971, Renwick and Cole 1971). This paper generalises the work of Willshaw (1972) to ensembles which conform to few or no logical constraints.

And-or graphs and theorem-proving graphs determine the same kind of search space and differ only in the direction of search: from axioms to goals, in the case of theorem-proving graphs, and in the opposite direction, from goals to axioms, in the case of and-or graphs. Bi-directional search strategies combine both directions of search. We investigate the construction of a single general algorithm which covers uni-directional search both for and-or graphs and for theorem-proving graphs, bi-directional search for path-finding problems and search for a simplest solution as well as search for any solution. We obtain a general theory of completeness which applies to search spaces with infinite or-branching. In the case of search for any solution, we argue against the application of strategies designed for finding simplest solutions, but argue for assigning a major role in guiding the search to the use of symbol complexity (the number of symbol occurrences in a derivation).

C. COOPER 21 3 Data representation--the key to conceptualisation: D. B. VIGOR 33 MECHANISED MATHEMATICS 45 4 An approach to analytic integration using ordered algebraic expressions: L. I. HODGSON 47 5 Some theorem-proving strategies based on the resolution principle: J. L DARLINGTON 57 MACHINE LEARNING AND HEURISTIC PROGRAMMING 73 6 Automatic description and recognition of board patterns in Go-Moku: A. M. MURRAY and E. W. Etcomc

The two outstanding figures in the history of computer science are Alan Turing and John von Neumann, and they shared the view that logic was the key to understanding and automating computation. In particular, it was Turing who gave us in the mid-1930s the fundamental analysis, and the logical definition, of the concept of'computability by machine' and who discovered the surprising and beautiful basic fact that there exist universal machines which by suitable programming can be made to t This essay is an expanded and revised version of one entitled The Role of Logic in Computer Science and Artificial Intelligence, which was completed in January 1992 (and was later published in the Proceedings of the Fifth Generation computer Systems 1992 Conference). Since completing that essay I have had the benefit of extremely helpful discussions on many of the details with Professor Donald Michie and Professor I. J. Good, both of whom knew Turing well during the war years at Bletchley Park. Professor J. A. N. Lee, whose knowledge of the literature and archives of the history of computing is encyclopedic, also provided additional information, some of which is still unpublished. Further light has very recently been shed on the von Neumann side of the story by Norman Macrae's excellent biography John von Neumann (Macrae 1992). Accordingly, it seemed appropriate to undertake a more complete and thorough version of the FGCS'92 essay, focussing somewhat more on the interesting historical and biographical issues. I am grateful to Donald Michie and Stephen Muggleton for inviting me to contribute such a'second edition' to the present volume, and I would also like to thank the Institute for New Computer Technology (ICOT) for kind permission to make use of the FGCS'92 essay in this way. 1 LOGIC, COMPUTERS, TURING, AND VON NEUMANN

EBL systems 117 see also non-deterministic finite see also explanation-based learning automata device malfunction data 165 ECG interpretation 306-7 description length of propositions Eckert, J.P. 4, 11 obtained 164 Eckert-Mauchly computers 11 Diagram Configuration (DC) model, EDSAC computer 11 perceptual chunks used EDVAC computer 11 420

When you lose a game of chess to a computer then don't pretend that you didn't think at the game.

Bayesian inference nets 190 algorithms, structure-moving task 209-17 Kononenko's treatment 201-2 ALG(SIG, E) 50

Perhaps the most promising and yet most difficult application of machine learning is in the area of scientific discovery: 'the most technically gripping challenge,... will be how to spread the computer wave from the front end of the scientific process, the telescopes, microscopes,... spark chambers, and the like, back to recognition and reasoning processes by which the chaos of data is finally consolidated into orderly discovery' (Michie 1982). For scientific discovery, machine learning is viewed as a tool to aid working scientists in forming theories from data.