Can somebody explain to me exactly what the halting problem says? As I understand it, it doesn't say "you can't tell if this program halts", it says "you cannot write an algorithm which can tell whether *every* program halts or not". (Similar to the way that Galios dude didn't say "you can't solve high-order polynomials", he said "you can't solve all possible Nth order polynomials *with one formula* [involving only a specific set of mathematical operators]". As in, you *can* solve high-order polynomials - just not with a single formula for all of them. Or not just with the specified operators.)
I'm not an expert, but as I understand it, you can construct a Turing machine to run a number of other Turing machines in parallel. In the case of the halting problem, you would then be able to construct a machine that simulates as many halting problem solutions as you want in parallel and return the decision of the first simulated machine that finishes. This parallel machine (still a Turing machine) will also be unable to decide the halting problem. Thus, no combination of algorithms is able to decide the halting problem.
_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
