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.
Yes, Turing did prove it using an unrealistic example, but the only
reason he did so was to keep the proof simple. There are plenty of
practical examples of functions which are difficult (or impossible) to
determine whether or not they terminate.
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.
