Why CTFE is context-sensitive?

[Simen Kjærås]

On 2014-01-27 23:18, Tofu Ninja wrote:
> On Monday, 27 January 2014 at 21:37:58 UTC, Ola Fosheim Grøstad wrote:
>> On Monday, 27 January 2014 at 21:12:30 UTC, deadalnix wrote:
>>> lolwut ? How do you make the difference between a program that won't
>>> terminate ever and one that will terminate eventually (say, in
>>> several years) ?
>>
>> 1. The halting problem does not apply to finite resources. The proof
>> is trivial: just record all state. You are in an infinite loop when
>> you revisit a state your program already has been in. The halting
>> problem only applies if you have non-finite storage.
>>
>> 2. You can set a timeout and use heurististics (and profiling) for
>> what computations you want to try to precompute. Perfectly doable.
>
> I don't think that is quite right, you can have an infinite loop without
> there being any repeated states. Simple example is
>
> for( i = 1; i>0 ; i++) {...}
>
> This will run forever while still never repeating state, assuming that i
> never wraps around. After all you said that we don't have finite
> resources which is the same as saying we have unlimited resources.

I assume i is a bigint then, and that you have infinite memory for it. 
Otherwise, you'll have repeated state when i overflows.

--
   Simen