20 ms·

Call me naive, but regarding: > why a perfect antivirus program is impossible What does TC have to do with a perfect antivirus program? Does it have something

• gwern 11y ago
  TC implies there's no such thing as a perfect antivirus program (which detects all and only viruses), or a perfect typechecker etc because if you had such a program, you could turn it into a halting-checker easily: for an AV program, if you want to know if program X halts, you simply put the virus at the end and run the whole thing through your perfect antivirus checker - by assumption, if it detects a virus, then the program X must halt (otherwise the virus would never be able to run and is just dead code) and if it doesn't detect a virus, then program X doesn't halt. Since we know you can't solve the halting problem... In more general terms, this brings us to Rice's theorem.
  • mjcohen 11y ago
    This was discussed in "Godel, Escher, Bach" in the form of trying to make a record player that can play any record.