Результат Фреда Коэна
В 1984 г. в своей работе "Computer Viruses - Theory and Experiments" Фред Коэн показал, что задача обнаружения компьютерных вирусов является неразрешимой. При этом он руководствовался следующими рассуждениями.
Отправной точкой был выбор определения вируса:
Определение 2.1. Компьютерным вирусом является программа, способная заражать другие программы изменяя их таким образом, чтобы они включали возможно измененную копию вируса.
Следовательно, чтобы определить, является ли программа P вирусом, необходимо выяснить заражает ли она другие программы. Предположим, существует процедура D, позволяющая по любой программе P сказать вирус это или нет. Но тогда можно составить программу V, которая будет включать процедуру D и будет заражать другие программы только в том случае, когда D не определит V как вирус и не будет заражать в противном случае.
Соответственно, если процедура D, будучи примененной к программе V, скажет, что это вирус, программа V на самом деле не будет заражать файлы и не будет вирусом согласно определению. И наоборот, если согласно процедуре D программа V не является вирусом, на самом деле она будет заражать другие программы, а значит будет вирусом.
Таким образом, гипотетическая процедура D оказывается противоречивой и, следовательно, не существует.
