438 A.M. TURING : Now obey the instruction stored in position 5606, and con- tinue from there may be encountered, or again If position 4505 contains 0 obey next the instruction stored in 6701, otherwise continue straight on.' Instructions of these latter types are very important because they make it possible for a sequence of operations to be repeated over and over again until some condition is fulfilled, but in doing so to obey, not fresh instructions on each repetition, but the same ones over and over again. To take a domestic analogy. Suppose Mother wants Tommy to call at the cobbler's every morning on his way to school to see if her shoes are done, she can ask him afresh every morning. Alternatively she can stick up a notice once and for all in the hall which he will see when he leaves for school and which tells him to call for the shoes, and also to destroy the notice when he comes back if he has the shoes with him. The reader must accept it as a fact that digital computers can be constructed, and indeed have been constructed, according to the principles we have described, and that they can in fact mimic the actions of a human computer very closely. The book of rules which we have described our human computer as using is of course a convenient fiction. Actual human com puters really remember what they have got to do. If one wants to make a machine mimic the behaviour of the human computer in some complex operation one has to ask him how it is done, and then translate the answer into the form of an instruction table. Constructing instruction tables is usually described as "pro- gramming To programme a machine to carry out the opera tion A' means to put the appropriate instruction table into the machine so that it will do A. An interesting variant on the idea of a digital computer is a digital computer with a random element'. These have instructions involving the throwing of a die or some equivalent electronic process; one such instruction might for instance be, Throw the die and put the resulting number into store 1000'. Sometimes such & machine is described as having free will (though I would not use the phrase myself). It is not normally possible to determine from observing a machine whether it has a random element, for a similar effect can be produced by such devices as making the choices depend on the digits of the decimal for . Most actual digital computers have only a finite store. There is no theoretical difficulty in the idea of a computer with an un limited store. Of course only a finite part can have been used at any one time. Likewise only a finite amount can have been COMPUTING MACHINERY AND INTELLIGENCE 439 constructed, but we can imagine more and more being added 18 required. Such computers have special theoretical interest and will be called infinitive capacity computers. The idea of a digital computer is an old one. Charles Babbage, Lacasian Professor of Mathematics at Cambridge from 1828 to 1839, planned such a machine, called the Analytical Engine, but it was never completed. Although Babbage had all the essential ideas, his machine was not at that time such a very attractive prospect. The speed which would have been available would be definitely faster than a human computer but something like 100 times slower than the Manchester machine, itself one of the slower of the modern machines. The storage was to be purely mechanical, using wheels and cards. The fact that Babbage's Analytical Engine was to be entirely mechanical will help us to rid ourselves of a superstition. Import- ance is often attached to the fact that modern digital computers are electrical, and that the nervous system also is electrical. Since Babbage's machine was not electrical, and since all digital com- puters are in a sense equivalent, we see that this use of electricity cannot be of theoretical importance. Of course electricity usually comes in where fast signalling is concerned, so that it is not surprising that we find it in both these connections. In the nervous system chemical phenomena are at least as important as electrical. In certain computers the storage system is mainly acoustic. The feature of using electricity is thus seen to be only very superficial similarity. If we wish to find such similarities we should look rather for mathematical analogies of function. 5. Universality of Digital Computers. The digital computers considered in the last section may be classified amongst the discrete state machines. These are the machines which move by sudden jumps or clicks from one quite definite state to another. These states are sufficiently different for the possibility of confusion between them to be ignored. Strictly speaking there are no such machines. Everything really moves continuously. But there are many kinds of machine which can profitably be thought of as being discrete state machines. For instance in considering the switches for a lighting system it is a convenient fiction that each switch must be definitely on or definitely off. There must be intermediate positions, but for most purposes we can forget about them. As an example of a discrete state machine we might consider a wheel which cliclos A. M. TURING: 440 round through 120 once a second, but may be stopped by a lever which can be operated from outside; in addition a lamp is to light in one of the positions of the wheel. This machine could be described abstractly as follows. The interal state of the machine (which is described by the position of the wheel) may be 9. or 9. There is an input signal, or (position of lever). The internal state at any moment is determined by the last state and input signal according to the table Last State 91 91 % i 92 93 91 Input 4 98 99 The output signals, the only externally visible indication of the interal state (the light) are described by the table State 49: % Output 0 0 0 This example is typical of discrete state machines. They can be described by such tables provided they have only a finite number of possible states It will seem that given the initial state of the machine and the input signals it is always possible to predict all future states. This is reminiscent of Laplace's view that from the completo state of the universe at one moment of time, as described by the positions and velocities of all particles, it should be possible to predict all future states. The prediction which we are considering is, however, rather nearer to practicability than that considered by Laplace. The system of the universe as a whole' is such that quite small errors in the initial conditions can have an overwhelming effect at a later time. The displacement of a single electron by a billionth of a centimetre at one moment might make the difference between a man being killed by an avalanche a year later, or escaping. It is an essential property of the mechanical systems which we have called 'discrete state machines that this phenomenon does not occur. Even when we consider the actual physical machines instead of the idealised machines, reasonably accurate knowledge of the state at one moment yields reasonably accurate knowledge any number of stepe later. COMPUTING MACHINERY AND INTELLIGENCE 441 As we have mentioned, digital computers fall within the class of discrete state machines. But the number of states of which such a machine is capable is usually enormously large. For instance, the number for the machine now working at Manchester it about 218,000, i.e. about 100,000. Compare this with our example of the clicking wheel described above, which had three states. It is not difficult to see why the number of states should be so immense. The computer includes a store corresponding to the paper used by a human computer. It must be possible to write into the store any one of the combinations of symbols which might have been written on the paper. For simplicity suppose that only digita from 0 to 9 are used a symbols. Variations in handwriting are ignored. Suppose the computer is allowed 100 sheets of paper each containing 50 lines each with room for 30 digits. Then the number of states is 10100x50x30.6. 10150,000 This is about the number of states of three Manchester machines put together. The logarithm to the base two of the number of states is usually called the storage capacity of the machine. Thus the Manchester machine has a storage capacity of about 165,000 and the wheel machine of our example about 16. If two machines are put together their capacities must be added to obtain the capacity of the resultant machine. This leads to the possibility of statements such as The Manchester machine containa 64 magnetic tracks each with a capacity of 2560, eight electronic tubes with a capacity of 1280. Miscellaneous storage amounts to about 300 making a total of 174,380. Given the table corresponding to a discrete state machine it is possible to predict what it will do. There is no reason why this calculation should not be carried out by means of a digital computer. Provided it could be carried out sufficiently quickly the digital computer could mimic the behaviour of any discrete state machine. The imitation game could then be played with the machine in question (ns B) and the mimicking digital computer (as A) and the interrogator would be unable to distinguish them. Of course the digital computer must have an adequate storage capacity as well as working sufficiently fast. Moreover, it must be programmed afresh for each new machine which it is desired to mimic. This special property of digital computers, that they can mimie any discrete state machine, is described by saying _that they are universal machines. The existence of machines with this property has the important consequence that, Conai derations of speed apart, it is unnecessary to design various new machines to do various computing processes. They can all be A A. M. TURING : 442 done with one digital computer, suitably programmed for each CARD. It will be seen that as a consequence of this all digital com- puters are in a sense equivalent. We may now consider again the point raised at the end of $3. It was suggested tentatively that the question, 'Can machines think?' should be replaced by 'Are there imaginable digital computers which would do well in the imitation game !! If we wish we can make this superficially more general and ask Are there discrete state machines which would do well ?' But in view of the universality property we see that either of these questions is equivalent to this, Let us fix our attention on one particular digital computer C. Is it true that by modifying this computer to have an adequate storage, suitably increasing its speed of action, and providing it with an appropriate programme, C can be made to play antisfactorily the part of A in the imitation game, the part of B being taken by a man?' 6. Contrary Views on the Main Question. We may now consider the ground to have been cleared and we are ready to proceed to the debate on our question, 'Can machines think I' and the variant of it quoted at the end of the last section. We cannot altogether abandon the original form of the problem, for opinions will differ as to the appropriateness of the substitu- tion and we must at least listen to what has to be said in this connexion It will simplify matters for the reader if I explain first my own beliefs in the matter. Consider firat the more accurate form of the question. I believe that in about fifty years'time it will be possible to programme computers, with a storage capacity of about 10, to make them play the imitation game so well that an average interrogator will not have more than 70 per cent chance of making the right identification after five minutes of questioning. The original question, 'Can machines think?' I believe to be too meaningless to deserve discussion. Nevertheless I believe that at the end of the century the use of words and generaleducated opinion will have altered so much that one will be able to speak of machines thinking without expecting to be contradicted. I believe further that no useful purpose is served by concealing these beliefs. The popular view that scientists proceed inexorably from well- established fact to well-established fact, never being influenced by any unproved conjecture, is quite mistaken. Provided it is made clear which are proved facts and which are conjectures, no harm can result. Conjectures are of great importance since they suggest useful lines of research. COMPUTING MACHINERY AND INTELLIGENCE 443 I now proceed to consider opinions opposed to my own. (1) The Theological Objection. Thinking is a function of man's immortal soul. God has given an immortal soul to every man and woman, but not to any other animal or to machines. Hence no animal or machine can think. I am unable to accept any part of this, but will attempt to reply in theological terms. I should find the argument more convincing if animals were classed with men, for there is a greater difference, to my mind, between the typical animate and the inanimate than there is between man and the other animals The arbitrary character of the orthodox view becomes clearer if we consider how it might appear to a member of some other religious community. How do Christiane regard the Moslem view that women have no souls? But let us leave this point aside and return to the main argument. It appears to me that the argument quoted above implies a serious restriction of the omni potence of the Almighty. It is admitted that there are certain things that He cannot do such as making one equal to two, but should we not believe that He has freedom to confer a soul on an elephant if He sees fit? We might expect that He would only exercise this power in conjunction with a mutation which provided the elephant with an appropriately improved brain to minister to the needs of this soul. An argument of exactly similar form may be made for the case of machines. It may seem different because it is more difficult to "swallow". But this really only means that we think it would be less likely that He would con- sider the circumstances suitable for conferring a soul. The cir- cumstances in question are discussed in the rest of this paper. In attempting to construct such machines we should not be irreverently uurping His power of creating souls, any more than we are in the procreation of children: rather we are, in either case, instruments of His will providing mansions for the souls that He creates However, this is mere speculation. I am not very impressed with theological argumenta whatever they may be used to support. Such arguments have often been found unsatisfactory in the past. In the time of Galileo it was argued that the texts, " And the sun stood still ... and hasted not to go down about a whole day" (Joshua x. 13) and "He laid the foundations of the earth, 1 Possibly this view is heretical. St. Thomas Aquinas (Summa Theologica, quoted by Bertrand Russell, p. 480) states that God cannot make a man to have no soul. But this may not be a real restriction on His powers, but only result of the fact that men's souls are immortal, and therefore indestructible. Problem 2.2 [10 points] Purpose: Draw/describe deterministic finite automata. Read Section 5, pp. 439-442, of Turing's famous "Computing Machinery and Intelligence" paper, available in this linked pdf scan. For the machine at the top of p. 440: a. Give its 5-tuple description. b. Draw the automaton. Assume the start state is 91 and that the lit lamp (01) indicates an accept/final state. In other words, when the lamp is lit it indicates acceptance