Charles Petzold

What is wrong with the following passage?

Turing found that he could phrase his version of the question in terms of the problem of deciding whether or not the n^th Turing machine would actually ever stop when acting on the number m. This problem was referred to as the halting problem.
— Roger Penrose, The Emperor's New Mind (Oxford University Press, 1989), pg. 57

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.

While fully honoring Turing's conception of what his machines could do, I was skeptical that his was the easiest way to apply them in the computation of number-theoretic functions. — S.C. Kleene, "Origins of Recursive Function Theory," Annals of the History of Computing, Vol. 3, No. 1 (Jan. 1981), pg. 61

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):

Theorem 2.2. There exists a Turing machine whose halting problem is recursively unsolvable. [pg. 70]

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