# undecidability of virus detection

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: 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

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

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.