D's treatment of values versus side-effect free nullary functions

[Peter Alexander]

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.