Вирусы и средства борьбы с ними


Обнаружение компьютерных вирусов


После определения компьютерного вируса естественным образом возникает вопрос об обнаружении такого рода программ, или о разрешимости множества компьютерных вирусов. Л. Адельман доказал следующую теорему.

Теорема 2.12. Для всех геделевских нумераций частичных рекурсивных функций

{\phi_i}
:
V = \{i\mid \phi_i \text{является вирусом}\} - \Pi_2
- полное множество

Теорема приводится без доказательства.

Здесь

\Pi_2
- класс множеств в арифметической классификации. Известно, что классы множеств
\Pi_n
с индексом 1 и выше являются неразрешимыми. Следовательно и множество вирусов является неразрешимым.




- Начало -  - Назад -  - Вперед -