Part 2 of Turing: a natural philosopher  (1997)

The Turing machine and the Entscheidungsproblem

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 [3]. 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.

The behaviour 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 to 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, the 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.

Let us imagine the operations performed by the computer to be split up into 'simple operations' which are so elementary that it is not easy to imagine them further divided. Every such operation consists of some change of the physical system consisting of the computer and his tape. We know the state of the system if we know the sequence of symbols on the tape, which of these are observed by the computer (possibly with a special order), and the state of mind of the computer. We may suppose that in a simple operation not more than one symbol is altered. Any other changes can be split up into simple changes of this kind. The situation in regard to the squares whose symbols may be altered in this way is the same as in regard to the observed squares. We may, therefore, without loss of generality, assume that the squares whose symbols are changed are always 'observed' squares.

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 square 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, however, 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 157767733443477; then, further on in the paper, we might find '...hence (applying Theorem 157767733443477) we have...' . In order to make sure which was the relevant theorem we should have to compare the two numbers figure by figure...

The simple operations must therefore include:

(a) Changes of the symbol on one of the observed squares.
(b) Changes of one of the squares observed to another square within L squares of one of the previously observed squares.

It may be that some of these changes necessarily involve a change of state of mind. The most general single operation must therefore be taken to be one of the following:

(A) A possible change (a) of symbol together with a possible change of state of mind.
(B) A possible change (b) of observed squares, together with a possible change of state of mind.

The operation actually performed is determined, as has been suggested [above], by the state of mind of the computer and the observed symbols. In particular, they determine the state of mind of the computer after the operation is carried out.

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 Numbers

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.

© 1997, Andrew Hodges.

CONTINUE to part 3

Quick Links:

A D V E R T I S I N G

Try us for digital cameras, computers, scanners, or monitors. Relax with a video game, pop CD, dvd, console, or relaxing experience. Escape it all with flights, a hotel, holidays in Europe, or short breaks.