Charles Petzold



Turing and the Halting Problem

November 26, 2007
New York, N.Y.

What is wrong with the following passage?

The association of Turing with the "halting problem" is an anachronism. Turing's original conception in his 1936 paper "On Computable Numbers, with an Application to the Entscheidungsproblem" was of machines that compute real numbers. Because real numbers (in general) have an infinite number of digits, these machines run forever. A machine that gets into a non-printing loop, or which enters a configuration that doesn't exist, will no longer compute digits of the real number and hence (in Turing's terms) is "unsatisfactory."

Even when Turing later lets his machines compute functions — in a sense, the Universal Machine performs a function, but in §10 of his paper, Turing describes machines that explicitly implement number-theoretic functions — the machines still run forever. The function machine calculates the function for an argument of 0, then 1, then 2, and so forth, encoding the integral results as runs of 1's separated by 0's, but still running forever.

As the concept of the Turing Machine was later generalized and applied to problems of computability, it became convenient to reformulate the machine. Instead of computing real numbers, these reformulated machines calculate a single value of a number-theoretic function and then halt. The satisfactory and unsatisfactory machines were swapped: In this new concept, machines that halted were "good" machines and machines that didn't halt were not.

According to Stephen Kleene, he reformulated the Turing Machine in this way in lectures he gave at the University of Wisconsin begnning in 1941.

Kleene's reformulation first appeared in print in Chapter XIII of his book Introduction to Metamathematics (Van Nostrand, 1952). Martin Davis believes that he first started using the term "halting problem" in connection with a similar reformulation of Turing Machines in lectures at the University of Illinois beginning in 1952. [B. Jack Copeland, The Essential Turing (Clarendon Press, 2004), pg. 40, footnote 61] The term was released into the wider world in Davis's book Computability and Unsolvability (McGraw-Hill, 1958):

It would be best for people writing about the Turing Machine to exercise a little more clarity in referring to Turing's original conception of his machines and these later formulations. One of the hopes I have for my forthcoming book The Annotated Turing is to make Turing's original conception better known. We can then appreciate the richness of the history behind the Turing Machine and how it has subsequently influenced ideas about mathematics, computability, the consciousness, and cosmology.

Coming May 19, 2008!

Available for Pre-Ordering
Wiley Amazon US Amazon Canada
Amazon UK Amazon Deutsch
Amazon Français Amazon Japan Blackwell