Свойства вирусного множестваЕще одним важным свойством «вирусного множества» является возможность написания последовательности инструкций, которая строит на ленте данных копии для любой конечной последовательности символов. Пусть «машина Тьюринга» работает с алфавитом Доказательство первого из них — самого важного! — существует как для «машины Тьюринга», так и для «вируса», алгоритм работы которого оформлен на привычном для нас алгоритмическом языке. В своей очередной модели Ф. Коэн описал алгоритм работы простейшего вируса-«паразита» примерно так: К сожалению, Ф. Коэн предусмотрел в своем типичном вирусном алгоритме процедуру нанесения ущерба, что заложило «теоретический фундамент» под мнение о безусловной вредоносности всех вирусов и, возможно, даже спровоцировало возникновение в дальнейшем множества действительно опасных саморазмножающихся программ. Впрочем, сейчас речь не об этом.

Определив типичный вирусный алгоритм и предположив, что существует некая решающая процедура «ЯВЛЯЕТСЯ_ВИРУСОМ», способная отличать вирусные программы от невирусных, Коэн предложил к рассмотрению следующую модификацию этого алгоритма: Эта программа обращается к решающей процедуре «ЯВЛЯЕТСЯ_ ВИРУСОМ», которая должна возвращать значение «ИСТИНА», если аргумент, переданный ей для тестирования, инфицирует другие программы, то есть если он является вирусом. В противном случае процедура возвращает значение «ЛОЖЬ». Легко видеть, что если программа «ВИРУС_ИЛИ_НЕ_ВИРУС» сама не является вирусом, то выполняется специфическая вирусная процедура «ИНФИЦИРО — ВАТЬ_ПРОГРАММУ», и, таким образом, исходное предположение о «безобидности» программы ложно. И наоборот.

Из этого можно сделать простой и однозначный вывод: не существует и не может существовать алгоритма, способного отличить «вирус» от «невируса». Вывод легко обобщается не только на вирусов-«паразитов», но и на червей и, вообще, на любые саморазмножающиеся программы. Разумеется, он в полной мере справедлив только для абстрактной машины, обладающей бесконечно длинной лентой данных и неограниченной памятью для набора инструкций.

Еще интересные статьи :

Свойства вирусного множества
Свойства вирусного множества
Свойства вирусного множества
Свойства вирусного множества