Why CTFE is context-sensitive?

[Simen Kjærås]

On 2014-01-27 21:37, "Ola Fosheim Grøstad" 
<ola.fosheim.grostad+dlang at gmail.com>"@puremagic.com 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.

My computer has 16GB of RAM. You try keeping track of all the possible 
states.

Now, I know DMD cannot use 16GB of RAM, so let's limit ourselves to 3GB 
or so. We then make a bit array for all permutations of 3*2^30 bits. 
That would take 2^(3*2^30) bits. All the hard drives in the world may be 
on the order of 10 zettabytes. When I ask Mathematica what multiple of 
this number we need to keep track of all the possible permutations of 
3GB, it gives up and calls me an asshole. Some jotting on a piece of 
paper indicates 2^3,221,225,399 is fairly close. Even if Kryder's Law[0] 
continues to hold, it will take 2.5 billion years before the entire 
world has enough storage capacity to do what you suggest, and even then, 
searching all that data will *still* be prohibitively expensive.

In simpler terms: Just because something is not theoretically 
impossible, it may still be so ridiculously computationally expensive it 
might as well be impossible. Stop making the argument that the halting 
problem does not apply to regular computers. It's technically true, yes. 
It also does not matter, for the reason described above.

Lastly, deadalnix didn't even bring up the halting problem, so why even 
mention it?


[0]: http://en.wikipedia.org/wiki/Mark_Kryder

--
   Simen