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
