When x is printed it is (3) and y when printed is (2, 3) rather than (2, 1) as it would have been had the last assignment left it undisturbed. How are we to prove assertions about such programs?

INTRODUCTION In this paper we compare three models of transformational grammar: the mathematical model of Ginsburg and Partee (1969) as applied by Salomaa (1971), the mathematical model of Peters and Ritchie (1971 and forthcoming), and the computer model of Friedman et al. (1971). All of these are, of course, based on the work of Chomsky as presented in Aspects of the Theory of Syntax (1965). We were led to this comparison by the observation that the computer model is weaker in three important ways: search depth is not unbounded, structures matching variables cannot be compared, and structures matching variables cannot be moved. All of these are important to the explanatory adequacy of transformational grammar. Both mathematical models allow the first, they each allow some form of the second, one of them allows the third. We were interested in the mathematical consequences of our restrictions. The comparison will be carried out by reformulating in the computer system the most interesting proofs to date of the ability of transformational grammars to generate any recursively enumerable set.

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

The frame problem in representing natural-language information is discussed. It is argued that the problem is not restricted to problem-solving-type situations, in which it has mostly been studied so far, but also has a broader significance. A new solution to the frame problem, which arose within a larger system for representing natural-language information, is described. The basic idea is to extend the predicate calculus notation with a special operator, Unless, with peculiar properties. Some difficulties with Unless are described. THE FRAME PROBLEM This paper proposes a method for handling the frame problem in representing conceptual, or natural-language-type information.

This paper documents an investigation into the role that the late Alan Turing played in the development of electronic computers. Evidence is presented that during the war he was associated with a group that designed and built a series of special purpose electronic computers, which were in at least a limited sense'program controlled', and that the origins of several post-war general purpose computer projects in Britain can be traced back to these wartime computers. INTRODUCTION During my amateur investigations into computer history, I grew intrigued by the lack of information concerning the role played by the late Alan Turing.

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

JUSTIFICATION OF CHESS PROGRAMS Young animals play games in order to prepare themselves for the business of serious living, without getting hurt in the training period. Game-playing on computers serves a similar function. It can teach us something about the structure of thought processes and the theory of struggle and has the advantage over economic modelling that the rules and objectives are clear-cut. If the machine wins tournaments it must be a good player. The complexity and originality of a master chess player is perhaps greater than that of a professional economist. The chess player continually pits his wits against other players and the precision of the rules makes feasible a depth of thinking comparable to that in mathematics. No program has yet been written that plays chess of even good amateur standard. A really good chess program would be a breakthrough in work on machine intelligence, and would be a great encouragement to workers in other parts of this field and to those ...

The formulation of the resolution principle by J. A. Robinson (1965a) has provided the impetus for a number of recent efforts in automatic theoremproving. In particular, the program PG1 (Wos et al. 1964, 1965), written by L. Wos, G. A. Robinson and D. F. Carson for the Control Data 3600, utilises the resolution principle in conjunction with a'unit preference strategy' and a'set of support strategy' to produce efficient proofs in first-order functional logic and group theory. 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 F(xi, x2,.-.., x) or its negation 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.

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