Tuesday, August 16, 2011

A note on Cohen's proof of undecidability of generic virus detection

Not so long ago I have re-read the Cohen's proof of undecidability of computer virus detection and both formal and informal ones smells fishy to me. This fish looks like the Russell's paradox. If Fred talk about viruses in a terms of viral sets (V) and implied that such set is constructed with is-virus predicate (which in turn reads as "v belongs to V set") it results with an impossible set. The same assumption (about undecidability of generic detection) could be proved by reducing it to algorithm equivalence: Cohen showed the viral set with the size of natural numbers; the equivalence of its elements (up to the additional symbol, i.e. the number) is undecidable either. This is more simple than proof by contradiction and stresses that "zeroing" (reducing to a single or a limited number of forms) of metamorphic viruses is undecidable, let alone that it has no chance to end up with a paradox.

No comments:

Post a Comment