Some Further Theoretical Results about Computer Viruses

In this paper we give some general definitions of computer viruses which comply with our common understanding of computer viruses. Based on these definitions, we prove theoretically that there may exist some special kinds of computer viruses that have not been found in the real world yet. Furthermore, we prove that the set of computer viruses with the same kernel is ∏2-complete. In general the set of computer viruses is ∑3-complete.