[BruceIV]

Odd that an article so nit-pickily concerned with the accuracy of the mathematics of Turing's work would over-generalize the actual computation he proved to be impossible, which was deciding if an arbitrary algorithm terminates on all possible inputs (i.e. there are no infinite loops), to "there are no bugs".

The Annotated Turing is a great book though, I highly reccomend it (Turing's original paper is _very_ dense).

[j2kun]

What do you mean by over-generalization? If you could solve the problem of determining if a program has a bug, you could solve the Halting problem. So it's just a generalization. Maybe it could be formalized more technically, but that makes it imprecise, not inaccurate.

[svantana]

Halting has nothing to do with being bug-free -- lots of buggy programs halt, and some obviously bug-free programs may not halt (e.g. a brute force search to determine Goldbach's conjecture)

[j2kun]

Of course it does: checking for halting reduces to checking for bug-freeness. See the other comment in this thread.

[mikeash]

The formalized generalization is called Rice's Theorem:

http://en.wikipedia.org/wiki/Rice%27s_theorem

It's pretty easy to figure out informally. If you had a program to figure out whether the output of a program is always correct for any definition of correctness, you could then write a trivial function around it that solves the halting problem:

    halts(program) {
        testFunction() {
            program()
            return correctImplementation()
        }
        return isCorrect(testFunction)
    }

In short, make a function that runs the candidate program and ignore its output, then correctly perform whatever task you have a checker for. That function is correct iff the program halts. Since you can't determine whether an arbitrary program halts, and you can use any working isCorrect() implementation to determine whether an arbitrary program halts, there's no working isCorrect() implementation.