Zhihong Zuo, Mingtian Zhou
The Computer Journal, Vol. 47, No. 6
ISSN 0010-4620
2004
Download PDF (1.63Mb) (You need to be registered on forum)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.