The Undecidability Problem


I’m confident that nobody who has gone through a computer science degree program is unaware of the undecidability problem and the Turing Machine. Some excerpts from the Wikipedia entry sum up the matter:

In computability theory and computational complexity theory, an undecidable problem is a decision problem for which it is known to be impossible to construct a single algorithm that always leads to a correct yes-or-no answer.


In computability theory, the halting problem is a decision problem which can be stated as follows:

Given the description of an arbitrary program and a finite input, decide whether the program finishes running or will run forever.

Alan Turing proved in 1936 that a general algorithm running on a Turing machine that solves the halting problem for all possible program-input pairs necessarily cannot exist. Hence, the halting problem is undecidable for Turing machines.

In full disclosure, I took the course and made an A, but the matter is still hazy to me, and it’s not something I have lost a lot of sleep over. What did interest me was Alan Turing’s work in cracking the Enigma code used by the Germans in World War Two, and that was my reason for obtaining the motion picture about these events, The Imitation Game. A review will be posted on the fourth of May, but in the meantime I obtained a copy of the book that formed the basis for the movie. It’s Alan Turing: The Enigma, and it’s more about Turing and less about the German Enigma. The image above is from the Kindle edition of the book, and it appears to have been taken from the movie. The book also has a photo of an Enigma.


The naval Enigma machine with its lid raised to show the four rotors. Hodges, Andrew (2014-11-10). Alan Turing: The Enigma: The Book That Inspired the Film “The Imitation Game” (p. ix). Princeton University Press. Kindle Edition.

Andrew Hodges has delivered a masterful, some might say exhaustive, volume on the life and works of British mathematician Alan Turing. The book came out in 1983 after two years of presumably solid writing. I will only touch on some high points.

With his description of what is now called the Turing Machine, Alan Turning is often pointed out as the father, or else the godfather, of the modern computer industry. Others before and after made huge contributions. Charles Babbage, another Englishman, laid out the concept of a mechanical device that is the true forerunner of what we now call a computer, and Ada Lovelace, daughter of English poet George Lord Byron and also assistant to Babbage, is considered to be the first computer programmer. A computer programming language (Ada) is named after her. Arguably the first working computer is attributed to John Vincent Atanasoff, although the Atanasoff-Berry Computer was not programmable. Turing’s concept of a programmable computer is given credit for cracking the code of the German Enigma.

Turing’s early life does not give the picture of somebody about to break thresholds in mathematics and signal counterintelligence. As a child he was an uninspired student who at a point in his academic spiral showed a gift for mathematics. This earned him a place at Cambridge King’s College, and Hodges gives his American readers a guided tour of the British system of matriculation, another matter I have yet to comprehend.

A central part of the book is how Alan Turing’s interest in a peculiar field of mathematics set him onto a course to take on the German war machine. I’m familiar with some of the background, but I’m going to take care not to bore you with a lot of depth. Suffice it to say that in the early 20th century there were items of interest being fiercely pursed in one small corner.

In 1900 German mathematician David Hilbert set forth a number of mathematical issues that needed to be resolved. One statement of his was

that every definite mathematical problem must necessarily be susceptible of an exact settlement …

[Hodges, Andrew (2014-11-10). Alan Turing: The Enigma: The Book That Inspired the Film “The Imitation Game” (p. 118). Princeton University Press. Kindle Edition.]

In Vienna in 1931 Kurt Gödel

demonstrated that any non-contradictory formal system, which was comprehensive enough to include at least arithmetic, cannot demonstrate its completeness by way of its own axioms

thereby refuting Hilbert’s assertion. What Alan Turing did was to use his concept of a computing machine as a means for computing all possibilities of  “computable numbers.” He demonstrated the Turing Machine could not compute all numbers, therefore there must be a solution to some problem statement that could not be computed.

The major theme of this book is how the Turing Machine concept led to the cracking of the Enigma code. The German Enigma was not a secret machine. Prior to the war commercial copies had been sold and used by businesses wishing to keep their correspondence private. Particularly, the German Navy used a modified version. Enigma worked by translating a character entered from the keyboard into a different character, displayed by a lighted position in an array of letters. Additionally, every time a key was depressed, a set of rotors would advance and produce a different connection between the keyboard and the display. The German Navy upgraded the operation of their Enigma devices throughout the war by adding more rotors and patch-plug connections.

Prior to the war the British became concerned about being able to read German signal traffic in the event of hostilities, and they worked with the Poles, who had obtained a purloined copy of a military Enigma and had developed a way to crack the code. Bare days before the Germans invaded Poland the Polish copy and accompanying cryptanalysis technology were spirited out and into British hands.

The movie shows Alan Turing being interviewed for a position on the cryptanalysis team by Commander Alastair Denniston, director of the British Government Code and Cypher School (GC and CS). Denniston was a real character, but the interview is a fake. Turing began working with GC and CS prior to the war and never was a reluctant candidate. Neither was he the abrasive co-worker who deigned to work with others as depicted in the movie.

The connection between the Turing Machine, none of which was ever constructed, and the cracking of the Enigma is that the concept of the Turing Machine is an automaton that can be adapted to perform a multiplicity of tasks by modifying its collection of control states. The concept of a collection of states has since morphed into what we now call a computer program, and it was the idea of constructing a machine controlled by a variable program that enabled the defeat of Enigma.

The team at Bletchley Park, where the British carried out cryptanalysis during the war, was able to crack Enigma codes by feeding message intercepts into an automaton devised by Turing and trying different rotor settings until the output contained legible verbiage. What assisted them throughout the war was incompetence on the part of the German operators. The careless inclusion of expected words allowed the code breakers to vastly narrow their search. Turing’s variable control set allowed adapting the search without reconstructing the machine whenever the Germans made a change in their Enigma.

A parallel theme that runs throughout the book is Turing’s homosexuality. As a boy he realized he found male bodies more attractive than females, and the book is a life-long tale of Turing dealing with his homosexuality. In England at the time homosexual acts were criminal, but nothing came from Turing’s homosexual lifestyle until years after the war, even though he never went to lengths to hide his orientation. Remarkably, Turing was throughout his life almost fatally honest, and he was casual in disclosing his homosexuality to co-workers and friends.

Someone watching the movie may get the idea that Turing’s arrest in 1952 (the movie has it 1951) for “gross indecency” with a male lover was his downfall. This was not the case. Turing admitted all details once the facts were reported to the police, and he and his partner entered guilty pleas at their trials. Turing did not lose his job at the University of Manchester. He served a one-year probationary sentence, which required he receive estrogen treatments to effect chemical castration. He continued to pursue his new interests in scientific research up until 7 June 1954, when he apparently dipped an apple in cyanide solution and bit into it. He left no suicide note.

Hodges introduces the term “imitation game,” the title of the movie. It has a double meaning. On the one it’s the science of cryptology, the masking of messages. On the other it’s Turing living and working as a homosexual in plain sight within a society that criminalizes his lifestyle.

Hodges takes what could otherwise be a great spy thriller and turns it into an English prose tour de force. His analysis in depth is little matched by the likes of Gustave Flaubert and D.H. Lawrence. For example:

He had clung to the simple amidst the distracting and frightening complexity of the world. Yet he was not a narrow man. Mrs Turing was right in saying, as she did, that he died while working on a dangerous experiment. It was the experiment called life – a subject largely inducing as much fear and embarrassment for the official scientific world as for her. He had not only thought freely, as best he could, but had eaten of two forbidden fruits, those of the world and of the flesh. They violently disagreed with each other, and in that disagreement lay the final unsolvable problem. In this sense his life belied his work, for it could not be contained by the discrete-state machine. At every stage his life raised questions about the connection (or lack of it) between the mind and the body, thought and action, intelligence and operations, science and society, the individual and history. But these were questions on which, except in the most special ways, he went out without a word of comment. Russell and Forster, Shaw and Wiener and Blackett held forth on such subjects; Alan Turing played the humble pawn.

Hodges, Andrew (2014-11-10). Alan Turing: The Enigma: The Book That Inspired the Film “The Imitation Game” (p. 659). Princeton University Press. Kindle Edition.

That, in combination with stringent attention to detail, runs to 663 pages of narrative. Following are 63 more pages of notes and index. It’s a lot to digest, and the casual reader will at times wish for a Cliff’s Notes. As a research into the life and works for Alan Turing it may be unmatched.

3 thoughts on “The Undecidability Problem

  1. Pingback: Prime Suspect | Skeptical Analysis

  2. Pingback: Bad Movie Wednesday | Skeptical Analysis

  3. Pingback: Women Who Won the War | Specular Photo of San Antonio

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.