Fifteen Eighty Four

Foreword to the Centenary Edition

Sara Turing, a woman in her seventies mourning the death of Alan, her younger son, a man that she failed to understand on so many levels, wrote this remarkable biographical essay. She carefully pieced together his school reports, copies of his publications, and comments on his achievements by experts. But Alan Turing was a thoroughly unconventional man, whose method of dealing with life’s situations was to think everything through from first principles, ignoring social expectations. And she was trying to fit him into a framework that reveals more about her and her social situation than it does about him. Alan’s older brother John trying to fill in the gaps he saw in his mother’s account, also ends up revealing a good deal about his own attitudes.In these few pages I will discuss some of the questions that may occur to readers of these documents.

Alan Turing’s War

In 1940, after France had been defeated, Britain fought on mainly alone. The merchant shipping on which the island was dependent was being sunk by German submarines at a rate that threatened to force the UK to yield. The radio communications between the submarines and their base concerning their operational plans were being picked up in Britain. If these planswere known, attacks could be mounted against the submarines. Merchant ships could adjust their routes so as not to go where they would encounter enemy submarines. But of course the data was encrypted.

For the purpose of decrypting enemy communications, an assorted group of classics scholars, mathematicians, and hobbyists who were good at solving puzzles were brought together in an estate called Bletchley Park near the present-day town of Milton Keynes. For much military communication the Germans used an enhanced version of a commercial enciphering machine called Enigma. Some Polish mathematicians had worked out a technique for decrypting German military messages coded on their Enigma, and had passed their work on to the English. But by the time war broke out in 1939, the Germans had added additional complications and the Polish techniques were no longer of any use. Not only were there several disks on the machine whose rotational position could be altered, but there was also a plug-board into which cables could be plugged in various ways. In order to decrypt a message, these precise settings had to be known. Taking advantage of certain weaknesses in the design of the machines as well as carelessness on the part of German cipher clerks, the Bletchley park code-breakers could rule out a large number of possible settings. That still left a number of possibilities to be attacked by trial and error. Turing played a major role in developing these techniques, and in working out a method for automating them. He designed a machine that would systematically try various settings, rejecting those that contradicted what was already known. These machines, many of which were built, strangely called bombes, were highly effective. What is truly remarkable is that, constructed to Turing’s specifications, they worked as intended without the need for any fine tuning. Although Turing’s contributions, and indeed the entire project of decrypting German military communications, were kept secret long after the war, Turing was awarded an O.B.E. (Order of the British Empire) for his contributions to the war effort.

Alan Turing’s Universal Computer

Mathematical proofs use logical reasoning to get from assertions already accepted as true to statements called theorems, which thus achieve acceptance as mathematical truths. The work of logicians in the nineteenth and twentieth centuries showed how, in principle, the individual steps in such “proofs” could be replaced by the mechanical manipulation of symbols. This situation gave rise to the problem of finding a mechanical process, an algorithm, for deciding in advance whether from some given statements accepted as true, another desired statement could be obtained by such a sequence of steps. The great mathematician David Hilbert declared that this problem, he called the Entscheidungsproblem, was the main problem of mathematical logic. (The long German word simply translates into “decision problem,” but since many problems involve “decisions,” it has been customary to use the German name.) The game of chess provides a useful analogy. The individual moves in a chess game, like the individual steps in a logical proof, are simple and mechanical. The Entscheidungsproblem is then like the problem of how to tell for a given initial position of the chess pieces,whether white can achieve a check-mate regardless of black’s counter moves. As every chess player knows, this is very difficult if not impossible.

Alan Turing learned about the Entscheidungsproblem from lectures on the foundations of mathematics given by Max Newman at Cambridge University in 1935. People were not at all convinced that there could be an algorithm meeting Hilbert’s requirements. The mathematician G.H. Hardy, a professor at Cambridge, said it forcefully:

“There is of course no such [algorithm], and this is very fortunate, since if there were we should have a mechanical set of rules for the solution of all mathematical problems, and our activities as mathematicians would come to an end.”

Alan agreed, and considered how one could go about proving that no such algorithm exists. Apparently no one had ever provided a definition of “algorithm,” and indeed there had hardly been a need for such a definition. As children, we all learned algorithms for adding and multiplying numbers. Later many of us will have learned algorithms for solving equations, and even the algorithms from the differential calculus for computing derivatives. None of this required that we be told what an algorithm is. We recognized that the rules we used were explicit and mechanical. Once we learned them, we could carry them out without any creative thought. That was good enough. But to prove that there is no algorithm to carry out some task, more was needed than the words “explicit” and “mechanical.”

Thinking about what people do when they “compute,” that is carry out algorithms, Turing saw that it all seemed to amount to taking note of particular symbols and then writing other symbols. Although the work is done on a two-dimensional surface like a sheet of paper or a blackboard,Turing could see that, in principle, it could all be done on a paper tape in which the symbols are written as a linear string. He realized that it was crucial that no limit be placed in advance on the amount of space needed. Speaking somewhat metaphorically, the tape should be infinitely long to be sure that it doesn’t get all used up before the computation is complete. Next he saw that the behavior of the person doing the computation could be represented by a simple table that indicated the next step to be carried out, writing a symbol and moving left or right on the tape. Finally a machine could be constructed that does what the table instructs it to do. Such machines have come to be called Turing machines.