Re: What good is halting prob?

[mab@dst17.wdl.loral.com (Mark A Biggar)]

In article <cppD786FM.1u9@netcom.com> cpp@netcom.com (Robin Rowe) writes:
>In article <dewar.798172270@gnat>, Robert Dewar <dewar@cs.nyu.edu> wrote:
>>...problems isomorphic to the halting
>>problem come up all the time. One quick example, the other day, someone 
>>asked why compilers refused to detect undefined variables, and some people
>>seem to think that this is actually possible, while of course it is provably
>>impossible (you can detect some simple casees, but not all cases
>>statically).
>I don't normally write compilers, so I haven't encountered this question. 
>This seems like it could be a very good example, thanks! One thing though, I 
>don't see how you can prove that this is equivalent to the halting 
>problem for any compiler that might be written. Can you show this in the 
>general case? If not, what language of compiler do you have a proof for, 
>and how did you construct it?

It turns out that the compiler doesn't matter at all here, it's the language
you are trying to compile that determines if uninitializized variable
detection, dead code elimination, several kinds of erroneous execution, etc.
in that language is equivalent to the Halting Problem.  The language just 
has be sufficiently complex for this to be a necessary consideration.
I believe that, for example, that any language with unbounded loops or 
unbounded recursion is sufficient.

Another example: determining if changing the parameter passing method from
by-refernece to copy-in-copy-out and vis-versa changes the behaviour of
your program is also equivalent to the Halting Problem.  The Ada83 LRM
says that such programs are erroneous, but the above result means that
detecting such programs at compile time is not possible in gerneral.

Someone once said: "All interesting problems in CS are either trivial,
NP-Complete or equivalent to the Halting Problem".  I would like to track
down this quote so I can attribute it correctly in the furture, can anyone
help?

--
Mark Biggar
mab@wdl.loral.com