Robert Dewar wrote:
> Daniel Berlin wrote:
>
>>> The chain of inferences that the compiler would need to do to properly
>>> diagnose this case is beyond the scope of the mechanical
>>> transformations. The reasoning you need to implement to catch these
>>> cases could even be reduced to the halting problem.
>>>
>>>
>>
>> I hate to bring this up, because it's a "half-troll", but the halting
>> problem is *not* undecidable on the machines we use everyday, because
>> they have finite memory.
>>
>>
> This is theoretically true, but quite irrelevant, any "solution" to such
> problems is likely exponentional and totally out of the question.
You could probably make an entropy based theoretical-limits-of-computation
argument to prove that the restriction isn't just a matter of practicalities.
Even a CBM-64 has 2^524328 possible states. That's not the kind of number you
can even enumerate, let alone have an array with that much storage, even if
you assume you can store a bit on each quark throughout the universe.
Plus, of course, the whole notion of regarding every bit in the computer's
entire memory plus registers as one long bit vector, regarding that as the
state of a state machine, working out how each one transforms to the next
state, and then looking for cycles in the graph of all possible states,
entirely disregards the highly relevant fact that the transformation from one
state to the next is, in almost every real system, non-deterministic, owing to
the presence of asynchronous and unpredictable inputs from the environment.
Consider the following program:
int main (int argc, const char **argv)
{
while (ERR == getch ()) { };
return 0;
}
I really don't see how the stopping problem could be _decided_ for that one!
cheers,
DaveK
--
Can't think of a witty .sigline today....
