Формальное определение

Нет общепринятого определения вируса. В академической среде термин был употреблён Фредом Коэном в его работе «Эксперименты с компьютерными вирусами», где он сам приписывает авторство термина Лену Эдлмэну

Формально вирус определён Фредом Коэном со ссылкой на машину Тьюринга^[13] следующим образом:

M: (S_M, I_M, O_M: S_M x I_M > I_M, N_M: S_M x I_M > S_M, D_M: S_M x I_M > d)

с заданным множеством состояний S_M, множеством входных символов I_M и отображений (O_M, N_M, D_M), которая на основе своего текущего состояния s ∈ S_M и входного символа i ∈ I_M, считанного с полубесконечной ленты, определяет: выходной символ o ∈ I_M для записи на ленту, следующее состояние машины s' ∈ S_M и движения по ленте d ∈ {-1,0,1}.

Для данной машины M, последовательность символов v: v_i ∈ I_M может быть сочтена вирусом тогда и только тогда, когда обработка последовательности v в момент времени t, влечёт за собой то, что в один из следующих моментов времени t, последовательность v′ (не пересекающаяся с v) существует на ленте, и эта последовательность v′ была записана M в точке t′, лежащей между t и t″:

∀ C_M ∀ t ∀ j:

S_M(t) = S_M0 ∧

P_M(t) = j ∧

{ C_M(t, j) … C_M(t, j + |v| - 1)} = v ⇒

∃ v' ∃ j' ∃ t' ∃ t":

t < t" < t' ∧

{j' … j' +|v'|} ∩ {j … j + |v|} = ∅ ∧

{ C_M(t', j') … C_M(t', j' + |v'| - 1)} = v' ∧

P_M(t") ∈ { j' … j' + |v'| - 1 }

где:

• t ∈ N число базовых операций «перемещения», осуществлённых машиной
• P_M ∈ N номер позиции на ленте машины в момент времени t
• S_M0 начальное состояние машины
• C_M(t, c) содержимое ячейки c в момент времени t

Данное определение было дано в контексте вирусного множества VS = (M, V) — пары, состоящей из машины Тьюринга M и множества последовательностей символов V: v, v' ∈ V. Из данного определения следует, что понятие вируса неразрывно связано с его интерпретацией в заданном контексте, или окружении.

Фредом Коэном было показано, что «любая самовоспроизводящаяся последовательность символов: одноэлементный VS, согласно которой существует бесконечное количество VS, и не- VS, для которых существуют машины, по отношению к которым все последовательности символов является вирусом, и машин, для которых ни одна из последовательностей символов не является вирусом, даёт возможность понять, когда любая конечная последовательность символов является вирусом для какой-либо машины». Он также приводит доказательство того, что в общем виде вопрос о том, является ли данная пара (M, X): X_i ∈ I_M вирусом, неразрешим (то есть не существует алгоритма, который мог бы достоверно определить все вирусы), теми же средствами, которыми доказывается неразрешимость проблемы остановки.

Другие исследователи доказали, что существуют такие типы вирусов (вирусы, содержащие копию программы, улавливающей вирусы), которые не могут быть безошибочно определены ни одним алгоритмом.