the halting problem is very technical and i'm certainly not going to do the technical aspects of it any justice here (and the technically minded really aren't the audience i'm writing this for anyways)... the short version is that the halting problem tells us what is not possible in the computing world...
the basic idea goes like this: there is no set of steps a person or computer can follow that will always determine if an arbitrary program will halt (terminate/exit/stop running)...since following steps (instructions) is all a computer can do, this is significant for computers and computer software...
the reason this is interesting and useful to us is that we can apply it to other things - by that i mean that if we can show that doing X is reducible to the halting problem then we've effectively proven that it is impossible to do X...
now, lets follow a simple progression... creating a set of steps that will always determine if an arbitrary program performs function Y is reducible to the halting problem - all you have to do is say that function Y is a halt function and you'll see it's trivially true... there's nothing special about code that causes a program to exit that would make it difficult to find, the problem is determining if it will ever get executed...
creating a set of steps that will always determine if an arbitrary program is a virus is redcuible to the halting problem.... to be a virus the program has to perform the function of self-replication and since you can't always determine (by following a set of steps) if an arbitrary program performs that function, therefore you can't always determine if that program is a virus...
creating a set of steps that will always determin if an arbitrary program performs any other virus-like functions is reducible to the halting problem... i'm sure by now you can guess why...
this probably looks pretty bad... it seems like we can't tell very much at all about arbitrary programs - and not only is that absolutely true, that's also the point... that's why the halting problem is important; it shows us what can't be done so that we can separate the impossible claims from the possible ones, so that we can understand what is preventing anti-virus developers from finding all possible viruses, and so that when someone comes along and says "well why can't it just look at the code to find out what it does" we can know why that won't work... knowing what isn't possible is probably the best tool there is when it comes to weeding out the hype and identifying snake-oil in the anti-virus field...
0 comments:
Post a Comment