[Haskell-cafe] Limits of deduction

[Josiah Manson]

>
>
> 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.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.haskell.org/pipermail/haskell-cafe/attachments/20070514/80651e5a/attachment.htm