K.A.PATON 411 24 Centromere finding: some shape descriptors for small chromosome outlines.

Editors' note The essay by Alan Turing, which we reproduce here, was written in September 1947, when the world's first stored-program digital computers, to a significant degree his own conceptual creation, were about to become operational. The paper was submitted in 1948 to the National Physical Laboratory, where Turing was then employed, as a report on his year's sabbatical leave which he had spent at Cambridge. During the same period Turing achieved his demonstration of the unsolvability of the word problem for semi-groups with cancellation. A condensed version is to appear in the Collected Works of A.M.Turing which is forthcoming under Dr Gandy's editorship. We also thank Mr Michael Woodger, who incidentally helped Turing finish it by drawing the original diagrams, for an unforgettable account of the furore created by Turing at N.P.L. with his prognostications of intelligent machinery: 'Turing is going to infest the countryside' some declared'with a robot which will live on twigs and scrap iron!' The anticipation of the notion of a sub-routine on page 21 and of the device of doing machine problem-solving via theorem-proving algorithms (p. Abstract The possible ways in which machinery might be made to show intelligent behaviour are discussed. The analogy with the human brain is used as a guiding principle. It is pointed out that the potentialities of the human intelligence can only be realized if suitable education is provided. The investigation mainly centres round an analogous teaching process applied to machines. The idea of an unorganized machine is defined, and it is suggested that the infant human cortex is of this nature. Simple examples of such machines are given, and their education by means of rewards and punishments is discussed. I propose to investigate the question as to whether it is possible for machinery to show intelligent behaviour. It is usually assumed without argument that it is not possible. Common catch phrases such as'acting like a machine', 'purely mechanical behaviour' reveal this common attitude. It is not difficult to see why such an attitude should have arisen. Some of the reasons are: (a) An unwillingness to admit the possibility that mankind can have any rivals in intellectual power. This occurs as much amongst intellectual people as amongst others: they have more to lose. Those who admit the possibility all agree that its realization would be very disagreeable.

G.R.KIss 155 11 Will seeing machines have illusions?

K.A.PATON 411 24 Centromere finding: some shape descriptors for small chromosome outlines.

Both the analytical philosopher and the designer of intelligent software are doing what might be called'mental engineering': constructing precise, formal models of some aspects of intelligent thought or behaviour. There is a wide gap between them, but it is narrowing.

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

Rather, the program exists in a state of continual revision and extension, and that part of it which is running and yielding results at the moment is intended to form the nucleus of a much larger and more extensive automatic deduction system in the future. The program is being developed with a number of different questions and applications in mind. First of all, some of the present generation of deduction programs are already capable of proving the sort of theorem of an elementary mathematical theory that appears in the textbooks either as a basic theorem or standard exercise (sometimes as a'starred' exercise), and might reasonably be classified as'somewhat' tricky. We have in mind the theorems of algebra and number theory obtained by programs discussed by Wos, Robinson and Carson (1965), Wos et al. (1967), and Luckham (1968). In addition, it is reported by Guard et al. (1969) that an open problem in modular lattice theory was solved with the aid of an on-line program (and it is interesting to note that, with reference to the initial set of axioms and hypotheses, this seems not to be the most difficult theorem that has been proved by a program so far). We are thus motivated to ask if, by adding a flexible interactive facility to a good deduction program, it is possible to construct a system that would be useful in investigating some fairly basic mathematics.

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

In particular its task domain is the analysis of mass spectra, chemical data gathered routinely from a relatively new analytical instrument, the mass spectrometer. This collaboration of chemists and computer scientists has produced what appears to be an interesting program from the viewpoint of artificial intelligence and a useful tool from the viewpoint of chemistry. For this discussion it is sufficient to say that a mass spectrometer is an instrument into which is put a minute sample of some chemical compound and out of which comes data usually represented as a bar graph. This is what is referred to here as the mass spectrum. The x-points of the bar graph represent the masses of ions produced and the y-points represent the relative abundances of ions of these masses. The first, preliminary inference (or planning), obtains clues from the data as to which classes of chemical compounds are suggested or forbidden by the data.

INTRODUCTION The problem discussed in this paper, namely that of finding a function to satisfy a given argument-value table, is by no means new to computing science, or to mathematics. Thus, for example, the problem of fitting a curve to a set of points is a part of numerical analysis. However, I am concerned with finding a function over a non-metric space, and so my work is closer to that of Feldman et al. (1969) in what they call, 'grammatical inference' or to the automaton-synthesizing programs described by Fogel, Owens and Walsh (1966). There have been some applications of learning devices. Perhaps the best known is Samuel's checkers program (Samuel 1967), but Murray and Elcock (1968) have a system for describing generalized board states in Go-Moku that employs a much richer language to describe the concepts learnt.