News for hackers. Stuff that matters.
Re:Surprisingly Turing-Complete by mholt on Friday October 02, 2015 @04:23PM (#10321055)
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 to do with the Halting problem?

Re:Surprisingly Turing-Complete by gwern on Friday October 02, 2015 @05:19PM (#10321404)
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.
Re:Surprisingly Turing-Complete by mjcohen on Friday October 02, 2015 @06:45PM (#10321774)
This was discussed in "Godel, Escher, Bach" in the form of trying to make a record player that can play any record.