Just sharing some of my inconsequential lunch conversations with you... RSS  

Monday, November 26, 2007

Turing and the Halting Problem

Petzold has just posted about it. He argues:

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."

And continues:

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.

I'll probably have to read his Annotated Turing to clear this out, I also holded this as true.

No comments:

Development Catharsis :: Copyright 2006 Mário Romano