"Peter Alexander" <[email protected]> wrote in message
news:[email protected]...
On 24/07/10 12:43 PM, Jim Balter wrote:
I thought that this was exactly the halting problem.
A common misconception, but not so. The halting problem is to find an
algorithm that will, for every possible function and data as input,
correctly determine whether the function will terminate. Turing proved
that such an algorithm is impossible, but that's irrelevant to any
practical problem. Not only isn't it necessary to guarantee that the
functions you decide not to attempt CTFE on really don't terminate, but
no function in any real program looks anthing like the arcane function
that Turing proved will baffle your algorithm.
Walter is right.
No, he's not, and I explained why, and you have failed to rebut anything I
wrote.
Yes, Turing did prove it using an unrealistic example, but the only reason
he did so was to keep the proof simple.
You have no absolutely no idea what you're talking about; Turing's proof is
reductio ad absurdum based on a diagonalization argument -- the constructed
undeterminable function is dependent on the algorithm purported to be able
to decide it. See http://en.wikipedia.org/wiki/Halting_problem
There are plenty of practical examples of functions which are difficult
(or impossible) to determine whether or not they terminate.
The halting problem proof isn't about "diffiicult", only "impossible", and
you have failed to provide a function and a proof that it is *impossible* to
determine whether it terminates.
In particular, any recursion or unconstrained loops make it very difficult
to prove termination, and there's plenty of practical examples of those
e.g. quicksort.
Again, difficulty is not an issue, *impossibility* is -- *that* is what the
halting problem is, and if you don't understand that then you don't
understand the issue *at all*.
