| Turing, Alan M. (1936), On computable
numbers, with an application to the Entscheidungsproblem, Proceedings
of the London Mathematical Society, Ser. 2-42, 230-265. |
| This quote from Tuning's 1936 paper
will give you some feel for the intuitions that guided Turing
in his formulation of the Turing machine In this quote the word
computer means the person that Turing is going to replace by
a machine. |
|
Computing is normally done by writing certain symbols on paper. We may suppose this paper is divided into squares like a child's arithmetic book. In elementary arithmetic the two-dimensional character of the paper is sometimes used. But such a use is always avoidable, and I think that it will be agreed that the two-dimensional character of paper is no essential of computation. I assume then that the computation is carried out on one-dimensional paper, i.e., on a tape divided into squares. I shall also suppose that the number of symbols which may be printed is finite. If we were to allow an infinity of symbols, then there would be symbols differing to an arbitrarily small extent.1 The effect of this restriction of the number of symbols is not very serious. It is always possible to use sequences of symbols in the place of single symbols. Thus an Arabic numeral such as 17 or 999999999999999 is normally treated as a single symbol. Similarly in any European language words are treated as single symbols (Chinese, however, attempts to have an enumerable infinity of symbols). The differences from our point of view between the single and compound symbols is that the compound symbols, if they are too lengthy, cannot be observed at one glance. This is in accordance with experience. We cannot tell at a glance whether 9999999999999999 and 999999999999999 are the same. The behavior of the computer at any moment
is determined by the symbols which he is observing, and his state
of mind at that moment. We may suppose that there is a bound
B to the number of symbols or squares which the computer can
observe at one moment. If he wishes to observe more, he must
use successive observations. We will also suppose that the number
of states of mind which need be taken into account is finite.
The reasons for this are of the same character as those which
restrict the number of symbols. If we admitted an infinity of
states of mind, some of them will be arbitrarily close and will
be confused. Again this restriction is not one which seriously
affects computation, since the use of more complicated states
of mind can be avoided by writing more symbols on the tape. |
|
Besides these changes of symbols, the simple operations must include changes of distribution of observed squares. The new observed squares must be immediately recognisable by the computer. I think it is reasonable to suppose that they can only be squares whose distance from the closest of the immediately previously observed squares does not exceed a certain fixed amount. Let us say that each of the new observed squares is within L squares of an immediately previously observed square. In connection with immediate recognisability, it may be thought that there are other kinds of squares which are immediately recognisable. In particular, squares marked by special symbols might be taken as immediately recognisable. Now if these squares are marked only by single symbols there can be only a finite number of them, and we should not upset our theory by adjoining these marked squares to the observed squares. If, on the other hand, they are marked by a sequence of symbols, we cannot regard the process of recognition as a simple process. This is a fundamental point and should be illustrated. In most mathematical papers the equations and theorems are numbered. Normally the numbers do not go beyond (say) 1000. It is, therefore, possible to recognise a theorem at a glance by its number. But if the paper was very long, we might reach Theorem 1577677334377; then further on in the paper, we might find ...hence (applying Theorem 1577677334377) we have .... In order to make sure which was the relevant theorem we should have to compare the two numbers figure by figure, possible ticking the figures off in pencil to make sure of their not being counted twice. If in spite of this it is still thought that there are other immediately recognisable squares, it does not upset my contention as long as these squares can be found by some process of which my tape machine is capable. The simple operations must therefore include: We may now construct a machine to do the work of this computer. To each state of mind of the computer corresponds an m -configuration of the machine. The machine scans B squares corresponding to the B squares observed by the computer. In any move the machine can change a symbol on a scanned square or can change any one of the scanned squares to another square distant not more than L squares from one of the other scanned squares. The move which is done, and the succeeding configuration, are determined by the scanned symbol and the m -configuration. The machines just described do not differ very essentially from computing machines as defined (previously) and corresponding to any machine of this type a computing machine can be constructed to compute the same sequence, that is to say the sequence computed by the computer. |
| 1 If we regard a symbol as literally printed on a square we may suppose that the square is 0 < x < 1, 0 < y <1. The symbol is defined as a set of points in this square, viz. the set occupied by printers ink. If these sets are restricted to be measurable, we can define the distance between two symbols as the cost of transforming one symbol into the other if the cost of moving a unit area of printers ink unit distance is unity, and there is an infinite supply of ink at x = 2, y = 0. With this topology the symbols form a conditionally compact space [Turing's note]. |
Machines |
Computational Approach |
|
| © Charles F. Schmidt | ||