Petzold has just posted about it. He argues:
And continues: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."
I'll probably have to read his Annotated Turing to clear this out, I also holded this as true.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.
No comments:
Post a Comment