From mboxrd@z Thu Jan 1 00:00:00 1970 X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on polar.synack.me X-Spam-Level: X-Spam-Status: No, score=-1.3 required=5.0 tests=BAYES_00,INVALID_MSGID autolearn=no autolearn_force=no version=3.4.4 X-Google-Language: ENGLISH,ASCII-7-bit X-Google-Thread: 10db24,77f71d0bde4c5bb4 X-Google-Attributes: gid10db24,public X-Google-Thread: 103376,86fd56abf3579c34 X-Google-Attributes: gid103376,public From: mab@dst17.wdl.loral.com (Mark A Biggar) Subject: Re: What good is halting prob? Date: 1995/04/19 Message-ID: <1995Apr19.204744.21914@wdl.loral.com>#1/1 X-Deja-AN: 101283252 sender: news@wdl.loral.com references: organization: Loral Western Development Labs newsgroups: comp.lang.ada,comp.edu Date: 1995-04-19T00:00:00+00:00 List-Id: In article cpp@netcom.com (Robin Rowe) writes: >In article , Robert Dewar 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