If a virus is defined as a self-reproducing program, then Rice's theorem implies there can be no infallible virus-detecting algorithm.
Can we take that one step further, as follows? If you have the source code for a virus-detecting program, could you use it to produce a virus that the program will fail to detect?
Following the reasoning of the Halting Problem, you can indeed make a "virus" that performs the following action:
if (this very virus will not be flagged)
infect everything in sight
else
do nothing
This is practically possible: you just would have to bundle the entire antivirus with your program in order to perform that check.
However, this will not be helpful, because the antivirus can just flag it anyway, despite the fact that in that case it's actually harmless. After all, actual virus-detecting programs are allowed to have false positives, as opposed to that ideal detector from Rice's theorem.
So, in summary: this trick is possible, but it doesn't actually give you any advantage against the antivirus.
That line of reasoning demonstrates that if you have a virus-detecting program, there exists a virus that the program will fail to detect.
But it says nothing about how easy or hard it might be to actually construct (find) such a virus. Such matters are beyond the scope of computability theory. If you care about the running time of an algorithm to solve some problem, that gets into complexity theory, which is beyond the scope of Rice's theorem, computability, the halting problem, etc.
If you care about the difficulty of constructing such a virus in practice, then this turns out to be more of an engineering matter, that depends on systems and implementation details. Computability theory and complexity theory are not terribly informative.
