Alan Turing: The Enigma The Centenary Edition

by Andrew Hodges

  However, the typewriter had a further feature which was essential to its function. Its typing point could move, relative to the page. Its typing action would be independent of the position of this point on the page. Alan incorporated this idea too into his picture of the more general machine. It was to have internal ‘configurations’, and a variable position on a printing line. The action of the machine would not depend upon its position.

  Neglecting details as to margins, line control, and so forth, these ideas would suffice to give a complete description of the nature of a typewriter. An exact account of the configurations and positions allowed, and of how the character keys determined the symbols printed, the shift key the change of configuration from ‘lower’ to ‘upper’, and the space bar and backspace the printing position, would bring out the features most relevant to its function. If an engineer took this account, and created a physical machine which met its specifications, the result would be a typewriter, regardless of its colour, weight, or other attributes.

  But a typewriter was too limited to serve as a model. It dealt with symbols, but it could only write them, and it required a human operator to choose the symbols and changes of configuration and position, one at a time. What, Alan Turing asked, would be the most general kind of machine that dealt with symbols? To be a ‘machine’ it would have to retain the typewriter’s quality of having a finite number of configurations, and an exactly determined behaviour in each. But it would have to be capable of much more. And so he imagined machines which were, in effect, super-typewriters.

  To simplify the description he imagined his machines working with just one line of writing. This was only a technicality, which allowed margins and line control to be forgotten. But it was important that the supply of paper was to be assumed unlimited. In his picture, the typing point of his super-typewriter could progress indefinitely to left or right. For the sake of definiteness, he imagined the paper as being in the form of a tape, marked off into unit squares, such that just one symbol could be written on any one square. Thus his machines were to be finitely defined, but they would be allowed an unlimited amount of space on which to work.

  Next, the machine would be able to read, or using his word, to ‘scan’ the square of tape on which it rested. It would still of course be able to write symbols, but now also to erase them. But it would only be able to move one place to the left or the right at a time. What role remained to the human operator of the typewriter? He did mention the possibility of what he called ‘choice machines’, in which an external operator would have the job of making decisions at certain points. But the thrust of his argument was directed at what he called automatic machines, in which human intervention would play no part. For the goal of his development was the discussion of what Hardy had called ‘a miraculous machine’ – a mechanical process which could work on Hilbert’s decision problem, reading a mathematical assertion presented to it, and eventually writing a verdict as to whether it was provable or not. The whole point was that it should do so without the interference of human judgment, imagination or intelligence.

  Any ‘automatic machine’ would work away by itself, reading and writing, moving to and fro, all in accordance with the way in which it was constructed. At every step its behaviour would be completely determined by the configuration it was in and the symbol it had read. To be precise, the construction of the machine would determine, for each combination of configuration and symbol scanned:

  whether to write a new (specified) symbol in a blank square, to leave the existing one unchanged, or to erase it and leave a blank square

  whether to remain in the same configuration, or to change to some other (specified) configuration

  whether to move to the square on the left, or to the right, or to stay in the same position.

  If all this information, defining an automatic machine, were written out, it would form a ‘table of behaviour’ of a finite size. It would completely define the machine in the sense that whether physically constructed or not, the table would hold all the relevant information about it. From this abstract point of view, the table was the machine.

  Every different possible table would define a machine with a different kind of behaviour. There would be infinitely many possible tables, corresponding to infinitely many possible machines. Alan had rendered the vague idea of a ‘definite method’ or a ‘mechanical process’ into something very precise: a ‘table of behaviour’. And so now he had a very precise question to answer: was there or was there not one of these machines, one of these tables, that could produce the decision that Hilbert asked for?

  An example machine: The following ‘table of behaviour’ completely defines a machine with the character of an adding machine. Started with the ‘scanner’ somewhere to the left of two groups of 1’s, separated by a single blank space, it will add the two groups, and stop. Thus, it will transform

  into

  The task of the machine is to fill in the blank space, and to erase the last ‘1’. It will therefore suffice to provide the machine with four configurations. In the first it moves along the blank tape looking for the first group of Ts. When it moves into the first group, it goes into the second configuration. The blank separator sends it into the third configuration, in which it moves along the second group until it encounters another blank, which acts as the signal to turn back, and to enter the fourth and final configuration in which it erases the last ‘1’ and marks time for ever.

  The complete table is:

  Even a very simple machine of this kind, as shown in the example, would be doing more than sums. The machine would effect acts of recognition, such as ‘finding the first symbol to the right’. A rather more complicated machine could perform multiplication, by repeated acts of copying out one group of 1’s, while erasing one at a time of another group of 1’s, and recognising when it had finished..Such a machine could also effect acts of decision, as for instance in deciding whether one number was divisible by another, or whether a given number was prime or composite. Clearly there was scope for exploiting this principle to mechanise a vast range of ‘definite methods’. But could there be such a machine that could decide Hilbert’s question about provability?

  This was much too hard a problem to approach by trying to write a ‘table’ to solve it. But there was an approach which led to the answer by a back door route. Alan hit on the idea of the ‘computable numbers’. The crucial notion was that any ‘real number’ which was defined by some definite rule could be calculated by one of his machines. For instance, there would be a machine to calculate the decimal expansion of π, rather as he had done at school. For it would require no more than a set of rules for adding, multiplying, copying, and so forth. being an infinite decimal, the work of the machine would never end, and it would need an unlimited amount of working space on its ‘tape’. But it would arrive at every decimal place in some finite time, having used only a finite quantity of tape. And everything about the process could be defined by a finite table, left alone to work on a blank tape.

  This meant that he had a way of representing a number like π, an infinite decimal, by a finite table. The same would be true of the square root of three, or the logarithm of seven – or any other number defined by some rule. Such numbers he called the ‘computable numbers’.

  More precisely, the machine itself would know nothing about decimals or decimal places. It would simply produce a sequence of digits. A sequence that could be produced by one of his machines, starting on a blank tape, he called a ‘computable sequence’. Then an infinite computable sequence, prefaced by a decimal point, would define a ‘computable number’ between 0 and 1. It was in this more strict sense that any computable number between 0 and 1 could be defined by a finite table. It was important to his argument that the computable numbers would always be expressed as infinite sequences of digits, even if these were all 0 after a certain point.

  But these finite tables could now be put into something like alphabetical order, beginning at
the most simple, and working through larger and larger ones. They could be put in a list, or counted; and this meant that all the computable numbers could be put in a list. It was not a practical proposition actually to do it, but in principle the idea was perfectly definite, and would result in the square root of three being say 678th in order, or the logarithm of π being 9369th. It was a staggering thought, since this list would include every number that could be arrived at through arithmetical operations, finding roots of equations, and using mathematical functions like sines and logarithms – every number that could possibly arise in computational mathematics. And once he had seen this, he knew the answer to Hilbert’s question. Probably it was this that he suddenly saw on the Grantchester meadow. He would have seen the answer because there was a beautiful mathematical device, ready to be taken off the shelf.

  Fifty years earlier, Cantor had realised that he could put all the fractions – all the ratios or rational numbers – into a list. Naively it might be thought that there were many more fractions than integers. But Cantor showed that, in a precise sense, this was not so, for they could be counted off, and put into a sort of alphabetical order. Omitting fractions with cancelling factors, this list of all the rational numbers between 0 and 1 would begin:

  1/2 1/3 1/4 2/3 1/5 1/6 2/5 3/4 1/7 3/5 1/8 2/7 4/5 1/9 3/7 1/10…

  Cantor went on to invent a certain trick, called the Cantor diagonal argument, which could be used as a proof that there existed irrational numbers. For this, the rational numbers would be expressed as infinite decimals, and the list of all such numbers between 0 and 1 would then begin:

  5000000000000000000.…

  3333333333333333333.…

  2500000000000000000.…

  6666666666666666666.…

  2000000000000000000.…

  1666666666666666666.…

  4000000000000000000.…

  7500000000000000000.…

  1428571428571428571.…

  6000000000000000000.…

  1250000000000000000.…

  2857142857142857142.…

  8000000000000000000.…

  1111111111111111111.…

  4285714285714285714.…

  1000000000000000000.…

  . .....

  . .....

  The trick was to consider the diagonal number, beginning

  .5306060020040180.…

  and then to change each digit, as for instance by increasing each by 1 except by changing a 9 to a 0. This would give an infinite decimal beginning

  .6417171131151291.…

  a number which could not possibly be rational, since it would differ from the first listed rational number in the first decimal place, from the 694th rational number in the 694th decimal place, and so forth. Therefore it could not be in the list; but the list held all the rational numbers, so the diagonal number could not be rational.

  It was already well-known – it was known to Pythagoras – that there were irrational numbers. The point of Cantor’s construction was actually rather different from this. It was to show that no list could possibly contain all the ‘real numbers’, that is, all infinite decimals. For any proposed list would serve to define another infinite decimal which had been left out. Cantor’s argument showed that in a quite precise sense there were more real numbers than integers. It opened up a precise theory of what was meant by ‘infinite’.

  However, the point relevant to Alan Turing’s problem was that it showed how the rational could give rise to the irrational. In exactly the same way, therefore, the computable could give rise to the uncomputable, by means of a diagonal argument. As soon as he had made that observation, Alan could see that the answer to Hilbert’s question was ‘no’. There could exist no ‘definite method’ for solving all mathematical questions. For an uncomputable number would be an example of an unsolvable problem.

  There was still much work to do before his result was clear. For one thing, there was something paradoxical about the argument. The Cantor trick itself would seem to be a ‘definite method’. The diagonal number was defined clearly enough, it appeared – so why could it not be computed? How could something that was constructed in this mechanical way be uncomputable? What would go wrong, if it were attempted?

  Suppose one tried to design a ‘Cantor machine’ to produce this diagonal uncomputable number. Roughly speaking, it would start with a blank tape, and write the number 1. It would then have to produce the first table, and then execute it, stopping at the first digit that it wrote, and adding on one. Then it would start again, with the number 2, produce the second table, executing it as far as the second digit, and writing this down, adding on one. It would have to continue doing this for ever, so that when its counter read ‘1000’, it would produce the thousandth table, execute it as far as the thousandth digit, add on one to this and write it down.

  One part of this process could certainly be done by one of his machines. For the process of ‘looking up the entries’ in a given table, and working out what the corresponding machine would do, was itself a ‘mechanical process.’ A machine could do it. There was a difficulty in that the tables were naturally thought of in two-dimensional form, but then it was only a technical matter to encode them in a form in which they could be put on a ‘tape’. In fact, they could be encoded as integers, rather as Gödel had represented formulae and proofs as integers. Alan called them ‘description numbers’, so that there was a description number corresponding to each table. In one way this was just a technicality, a means of putting tables on to the tape, and arranging them in an ‘alphabetical order’. But underneath there lay the same powerful idea that Gödel had used, that there was no essential distinction between ‘numbers’ and operations on numbers. From a modern mathematical point of view, they were all alike symbols.

  With this done, it followed that one particular machine could simulate the work done by any machine. He called it the universal machine. It would be designed to read description numbers, decode them into tables, and execute them. It could do what any other machine would have done, if it were provided with the description number of that machine on its tape. It would be a machine to do everything, which was enough to give anyone pause for thought. It was, furthermore, a machine of perfectly definite form. Alan worked out an exact table for the universal machine.

  This was not the trouble with mechanising the Cantor process. The difficulty lay in the other requirement, that of producing the tables, in their ‘alphabetical order’, for the computable numbers. Suppose that the tables were encoded as description numbers. In practice, they would not use up all the integers; in fact, the system Alan devised would encode even the simplest tables into enormous numbers. But that would not matter. It would be essentially a ‘mechanical’ matter to work through the integers in turn, and to pass over those which did not correspond to proper tables. That was a technicality, almost a matter of notation. The real problem was more subtle. The question was this: given (say) the 4589th properly defined table, how could one tell that it would produce a 4589th digit? Or indeed, that it would produce any digits at all? It might trundle back and forth in a repeated cycle of operations for ever, without producing more figures. It this were the case, the Cantor machine would be stuck, and could never finish its job.

  The answer was that one could not tell. There was no way of checking in advance that a table would produce an infinite sequence. There might be a method for some particular table. But there was no mechanical process – no machine – that could work on all instruction tables. There was nothing better than the prescription: ‘take the table and try it out’. But this procedure would take an infinite time to find out whether infinitely many digits emerged. There was no rule that could be applied to any table, and be guaranteed to produce the answer in a finite time, as was required for the printing of the diagonal number. The Cantor process, therefore, could not be mechanised, and the uncomputable diagonal number could not be computed. There was no paradox after all.

  Alan called the des
cription numbers which gave rise to infinite decimals the ‘satisfactory numbers’. So he had shown that there was no definite method of identifying an ‘unsatisfactory number’. He had pinned down a clearly specified example of something Hilbert said did not exist – an unsolvable problem.

  There were other ways of demonstrating that no ‘mechanical process’ could eliminate the unsatisfactory numbers. The one he himself favoured was one which brought out the connection with self-reference in the question. For supposing that such a ‘checking’ machine did exist, able to locate the unsatisfactory numbers, it could be applied to itself. But this, he showed, led to a flat contradiction. So no such checking machine could exist.

  Either way, he had found an unsolvable problem, and it required only a technical step to show that this settled Hilbert’s question about mathematics, in the exact form in which it had been posed. Alan Turing had dealt the death-blow to the Hilbert programme. He had shown that mathematics could never be exhausted by any finite set of procedures. He had gone to the heart of the problem, and settled it with one simple, elegant observation.

  But there was more to what he had done than a mathematical trick, or logical ingenuity. He had created something new – the idea of his machines. And correspondingly, there remained a question as to whether his definition of the machine really did include everything that could possibly be counted as a ‘definite method’. Was this repertoire of reading, writing, erasing, moving and stopping enough? It was crucial that it was so, for otherwise the suspicion would always lurk that some extension of the machine’s faculties would allow it to solve a greater range of problems. One approach to this question led him to demonstrate that his machines could certainly compute any number normally encountered in mathematics. He also showed that a machine could be set up to churn out every provable assertion within Hilbert’s formulation of mathematics. But he also gave some pages of discussion37 that were among the most unusual ever offered in a mathematical paper, in which he justified the definition by considering what people could possibly be doing when they ‘computed’ a number by thinking and writing down notes on paper: