1
$\begingroup$

I have been reading the following document about the undecidability of virus detection, available at:

https://enterprise.comodo.com/whitepaper/Impossibility_of_Virus_Detection_WP.pdf

the problem that I have is in the following part:

enter image description here

The part that I do not understand is the one that says:

Halts(P)=not(DetectVirus(MakeVirus(P)))

Because for what I read if P behaves like a virus, which is made by the function MakeVirus(P), then I suppose that DetecVirus() will detect it and because of that this program will halt. So I will end up with:

Halts(P)=(DetectVirus(MakeVirus(P)))=true

but why do they negate that term? is it because P is a virus, but DetectVirus failed to detect it, so their answer instead of being true is false because of:

Halts(P)=not(DetectVirus(MakeVirus(P)))= not(DetectVirus(MakeVirus(P)=returns virus)=false)=true

I am assuming that P is a virus, but DetectVirus() returns false because it failed to detect it; then the negation of this would be a true value, so in this case Halts(p) will also halt the program.

Could somebody explain me what am I doing wrong?

Thanks

$\endgroup$
  • 1
    $\begingroup$ I also think that there should be no negation there. $\endgroup$ – chi Jun 18 '18 at 10:00
1
$\begingroup$

Abstracting away the details of their argument, what they're saying is basically:

Suppose we have a Turing machine DoesItZork(P) that takes a program P and decides whether it zorks or not. Now we can build a Turing machine RunThenZork(P) = P() then Zork() which first runs its input, then zorks. Now, if DoesItZork(RunThenZork(P)) returns True (and P itself does not zork), then P must halt on the empty input. On the other hand, if it returns False, then P must not halt on the empty input. So we just invert the output: DoesItHalt(P) = not DoesItZork(RunThenZork(P)). So if we have a way to ensure that P never zorks on its own (which we do), then having DoesItZork gives us a solution to the Halting Problem. We know that there is no solution to the Halting Problem, therefore, there can be no DoesItZork.

As a matter of fact, this proof skips over some important details. For one, Turing machines have no concept of files, so there needs to be some mapping between Turing machines and actual computer programs. (Fortunately, such a thing does exist.)

In addition, there's an easier way to prove this, once you allow for the idea that a Turing machine can be a virus. Rice's Theorem effectively says that all non-trivial semantic properties of a program are undecidable, where a property is trivial if all Turing machines have it or no Turing machines have it, and a property is semantic if it has to do with the program's behavior rather than its encoding. Since there exist programs that are viruses, and programs that are not viruses, and viruses are defined by their behavior, it's undecidable which are which.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.