On Sat, Dec 03, 2005 at 12:22:17PM +1300, Nick FitzGerald wrote: > Ahh, no... > > http://en.wikipedia.org/wiki/Halting_problem > > Basically (and simplifying a lot), the Halting Problem means that you > cannot write a computer program to determine if some other program > exhibits "function X", _in finite time_.
I don't think this is what the Halting Problem means. My understanding is that it means you can't write a program to determine if *any* other program exhibits "function X", in finite time. For a particular program, however, this may be quite feasible. > Thus, you cannot write a > program to detect all viruses, you cannot write a program to detect key > loggers, you cannot write a prorgram to detect all spyware, etc, etc. How do you know that the problem of detecting all keystroke loggers is equivalent to the Halting Program? Is there a proof somewhere that keystroke loggers do not share some characteristic that makes them detectable? <-- I am not being sarcastic; this is an earnest question. My formal CS background is weak, but I don't think the problem of programmatically detecting compromised machines of a given OS (not the general case of "compromised machines of any sort) has been proven to be undecidable in the strong way that the Halting Problem has. I may be wrong, though, which is why I ask. --Foofus. _______________________________________________ Full-Disclosure - We believe in it. Charter: http://lists.grok.org.uk/full-disclosure-charter.html Hosted and sponsored by Secunia - http://secunia.com/
