On 2014-01-27 21:37, "Ola Fosheim Grøstad"
<[email protected]>"@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
