02178510

j

02178510 Zuo, Zhihong Zhou, Mingtian Some further theoretical results about computer viruses. Comput. J. 47, No. 6, 627-633 (2004). 2004 Oxford University Press, Oxford EN D.2.3 D.2.m

doi:10.1093/comjnl/47.6.627

Summary: 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 $\Pi_2$-complete. In general the set of computer viruses is $\Sigma_3$-complete.