Path: utzoo!utgpu!jarvis.csri.toronto.edu!mailrus!cs.utexas.edu!samsung!gem.mps.ohio-state.edu!wuarchive!udel!haven!mimsy!tank!eecae!netnews.upenn.edu!vax1.cc.lehigh.edu!sei.cmu.edu!krvw
From: OSPWD%EMUVM1.BITNET@VMA.CC.CMU.EDU (Peter W. Day)
Newsgroups: comp.virus
Subject: virus problem undecidability
Message-ID: <0005.8911091541.AA08370@ge.sei.cmu.edu>
Date: 8 Nov 89 21:32:00 GMT
Sender: Virus Discussion List <VIRUS-L@IBM1.CC.Lehigh.EDU>
Lines: 9
Approved: krvw@sei.cmu.edu

A note to the virus-l digest of 6-Nov-89 said that "the virus problem (at
least detection anyway) is undecidable."  Does anyone know if there are
any papers where this result is proved? Or where the problem is
shown to not be NP complete? Or even where the problem is stated
precisely?

Thanks,
Peter Day
Emory University