Part 2 of Turing: a natural philosopher (1997)
The Turing machine and the EntscheidungsproblemWhen, in the spring of 1935, Turing attended the advanced lectures on the Foundations of Mathematics given by the Cambridge topologist M. H. A. Newman, he was not making a career move. Mathematical logic was a small, abstruse, technically difficult area devoid of applications, and unrepresented in the undergraduate curriculum. Turing's work was a labour of love.
Newman's lectures brought Turing to the point reached by Gödel in his now-famous 1931 Incompleteness theorem. The underlying problem here addressed is how we can grasp the truth of a statement about infinitely many instances: such as that for all a, b, c, (a+b) x c = a x c + b x c, or that there is no largest prime number. An apparently reasonable response might be that statements such as these do not in fact involve infinitely many instances at all, but are only finite sentences with words like 'all' in them, deduced by finitely many rules of deductive logic. Mathematical logicians in the late nineteenth century had tried to make this argument explicit, but Bertrand Russell, showing how finite descriptions like 'set of all sets' could be self-contradictory, had discovered the unavoidable difficulties that arose through self-referential terms. Since then the mathematician David Hilbert had made more precise demands of any proposed finite scheme in the famous terms: consistency, completeness and decidability. In 1931 Gödel had shown that consistency and completeness could not both be attained: there were statements about numbers, indubitably true, which could not be proved from finite axioms by finitely many rules. Goedel's proof rested on the idea that statements about numbers could be coded as numbers, and constructing a self-referential statement to defeat Hilbert's hopes.
Gödel's work left outstanding Hilbert's question of decidability, the Entscheidungsproblem, namely the question of whether there exists a definite method which, at least in principle, can be applied to a given proposition to decide whether that proposition is provable. In a restricted calculus there may indeed be such a method: for example, the truth-table technique for deciding whether a formula in elementary propositional logic is a tautology. Could there be such a decision procedure for mathematical propositions? This question had survived Gödel's analysis because its settlement required a precise and convincing definition of method. Giving precise definitions is the meat and drink of pure mathematics, but in this case, something more than precision was called for — it had to be something unassailable in its generality, which would not be superseded by a more powerful class of methods. There had, in fact, to be some philosophical as well as some mathematical analysis.
This, working by himself for the year until April 1936, Turing achieved; his idea, now known as the Turing machine, was to be published at the very end of 1936 in a paper On Computable Numbers, with an Application to the Entscheidungsproblem . It is characteristic of Turing that he refreshed Hilbert's question by casting it in terms not of proofs, but of computing numbers. The reformulation staked a clearer claim to have found an idea central to mathematics. As his title said, the Entscheidungsproblem was only an application of a new idea, that of computability. There are no surviving drafts or correspondence relating to its formation; no later accounts of his intellectual journey; just the story he told to his later student Robin Gandy that he had the main idea while lying in Grantchester meadows. Newman only saw the work when it was fully formed.
His paper starts with the line of thought already mentioned: how can we specify the infinite in finite terms? In particular, how can we specify the infinite sequence of digits in a 'real number', such as &pi = 3.141592653... ? What does it mean to say that there is a definite method for calculating such a number? Turing's answer lies in defining the concept of the Turing machine.
We may compare a man in the process of computing a real number to a machine which is only capable of a finite number of conditions... which will be called 'm-configurations'. The machine is supplied with a 'tape' (the analogue of paper) running through it, and divided into sections (called 'squares') each capable of bearing a 'symbol'. At any moment there is just one square ... which is 'in the machine'. We may call this square the 'scanned square'. The symbol on the scanned square may be called the 'scanned symbol'. The 'scanned symbol' is the only one of which the machine is, so to speak, 'directly aware'...
Turing then specifies precisely the repertoire of action available to the imagined machine. The action is totally determined by the 'configuration' it is in, and the symbol it is currently scanning. It is this complete determination that makes it 'a machine'. The action is limited to the following: at each step it (1) either erases the symbol or prints a specified symbol, (2) moves one square either to left or right (3) changes to a new configuration. Slightly different versions of Turing's idea are given in different textbooks, and the precise technical form he originally gave is not important; the essence is that the action is completely given by what Turing calls a 'table of behaviour' for the machine, dictating what it will do for every configuration and every symbol scanned: this determination is what makes it 'mechanical.' Each 'table of behaviour' is a different Turing machine.
The actions are highly restricted in form, but Turing's thesis is that they form a set of atomic elements out of which all mathematical operations can be composed. In fact, in a style very unusual for a mathematical paper, argument is given in very general terms, justifying the Turing machine actions as sufficient to encompass the most general possible method:
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. [A footnote gives a topological argument for this.] 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... This is in accordance with experience. We cannot tell at a glance whether 9999999999999999 and 999999999999999 are the same.
Turing thus claims that a finite repertoire of symbols actually allows a countable infinity of symbols, but not an infinity of immediately recognisable symbols. Note that the tape also has to be of unlimited length, although at any time the number of symbols on it is finite. In the next paragraph note that the word 'computer' then meant a person doing computing. Turing's model is that of a human mind at work.
Turing now continues 'We may now construct a machine to do the work of this computer' — that is, specify a Turing machine to do the work of this human calculator. Note, for its later significance, that Turing does not here raise the question of whether the mind might be capable of other actions which are not a 'process of calculation'.
Turing was very bold and untypical of mathematicians in placing this analysis of mental activity at the forefront. He added a less contentious argument:
... we avoid introducing the 'state of mind' by considering a more physical and definite counterpart of it. It is always possible for the computer to break off from his work, to go away and forget all about it, and later to come back and go on with it. If he does this he must leave a note of instructions (written in some standard form) explaining how the work is to be continued. This note is the counterpart of the 'state of mind.' We will suppose that the computer works in such a desultory manner that he never does more than one step at a sitting. The note of instructions must enable him to carry out one step and write the next note. Thus the state of progress of the computation at any one stage is completely determined by the note of instruction and the symbols on the tape...
But note that this calls for the method to be consciously known in every detail, whereas the 'state of mind' argument could be held to apply to a person who can reliably perform a process without being able to describe it explicitly.
Uncomputable NumbersThe computable numbers are then defined as those infinite decimals which can be printed by a Turing machine starting with a blank tape. He sketches a proof that π is a computable number, along with every real number defined by the ordinary methods of equations and limits in mathematical work. But armed with this new definition, it is now easy to show that uncomputable numbers exist. The crucial point is that the table of behaviour of any Turing machine is finite. Hence, all the possible tables of behaviour can be listed in an alphabetical order: this shows that the computable numbers are countable. Since the real numbers are uncountable, it follows that almost all of them are uncomputable. We can refine this idea to exhibit a particular uncomputable number. Before showing the construction, a point has to be noted: a table of behaviour may have the property of running in a loop and never producing more than a finite number of digits.
With this in mind, we again place all Turing machines in an alphabetical order of their tables of behaviour. We discard those which fail to produce an infinite series of digits, leaving only the Turing machines which produce infinite strings of digits — the computable numbers. Let us suppose that binary notation is being used, so that the digits are either 0 or 1. Now define a new number so that its nth digit is different from the nth digit produced by the nth machine. This new number differs in at least one place from every computable number; therefore it cannot be computable.
As Turing puts it, this seems a paradox. If it can be described finitely, why can it not be computed? Inspection shows that the problem comes in identifying those Turing machines which fail to produce infinitely many digits. This is not a computable operation: that is, there is no Turing machine which can inspect the table of any other machine and decide whether it will produce infinitely many digits or not. This can be seen more directly: if there were such a machine, it could be applied to itself, and this idea can be used to get a contradiction. Nowadays this is known as the fact that the halting problem cannot be decided by a Turing machine. From this discovery of a problem that cannot be decided by a machine, it is not a difficult step to employ the formal calculus of mathematical logic, and to answer Hilbert's Entscheidungsproblem in the negative.
A point which Turing stressed, however, is that there is no inconsistency involved in defining uncomputable numbers; in modern computability theory they are the subject of rigorous manipulation and logical argument. It may even be that every digit of an uncomputable number may be calculated; the point is, however, that infinitely many different methods are required to work them out. Nevertheless the property of computability rests on mathematical bedrock: this was Turing's claim at the time and it has never since been challenged.A. M. Turing. 'On computable numbers, with an application to the Entscheidungsproblem,'
Proc. Lond. Math. Soc. ser. 2, 42 (1936) pp. 230-65. correction ibid. 43 (1937) pp. 544-6.
(See the Bibliography on this site.)
© 1997, Andrew Hodges.