440 A. M. TURING : round through 120 once a second, but may be stopped by 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 internal state of the machine (which is described by the position of the wheel) may be 99 or 9 There is an input signal i, 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 % % 10 9: % % Input 41 91 The output signals, the only externally visible indication of the internal state (the light) are described by the table State 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 posible to predict all future states. This is reminiscent of Laplace's view that from the complete 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 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,006, 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 digits from 0 to 9 are used as 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 10100x50x80, i.e. 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 contains 64 magnetic tracks each with a capacity of 2660, 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 (as 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 consi derations of speed apart, it is unnecessary to design various new machines to do various computing processes. They can all be - 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. 440 A. M. TURING : round through 120 once a second, but may be stopped by 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 internal state of the machine (which is described by the position of the wheel) may be 99 or 9 There is an input signal i, 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 % % 10 9: % % Input 41 91 The output signals, the only externally visible indication of the internal state (the light) are described by the table State 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 posible to predict all future states. This is reminiscent of Laplace's view that from the complete 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 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,006, 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 digits from 0 to 9 are used as 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 10100x50x80, i.e. 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 contains 64 magnetic tracks each with a capacity of 2660, 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 (as 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 consi derations of speed apart, it is unnecessary to design various new machines to do various computing processes. They can all be - 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