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


Принятые обозначения


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

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

Ниже везде неявно подразумевается описанная интерпретация вычислительной системы.

  1. Обозначим S - множество всех конечных последовательностей натуральных чисел,
    S = \Omega (\infty)
    . Таким образом элемент S может обозначать либо набор файлов данных, либо набор файлов программ, закодированных при помощи натуральных чисел.
  2. Обозначим e - вычислимую инъективную функцию из S?S на
    \infty
    с вычислимой обратной функцией,
    e: S \times S \to \infty
    . По тому же принципу, что и программы и данные, натуральными числами могут кодироваться и состояния системы. Функция e взаимно однозначно ставит в соответствие набору данных и программ натуральное число. Иными словами e - однозначная нумерация состояний системы.
  3. \forall s,t \in S : \langle s,t \rangle := e(s,t)

    Нотация

    \langle s,t \rangle
    предназначена для обозначения состояния системы и фактически является кодом этого состояния, представленным натуральным числом.
  4. Для всех частичных функций
    f : \infty \to \infty, \forall s,t \in S: f(s,t) := f(\langle s,t \rangle)
    Любая программа переводит систему из одного состояния в другое, учитывая, что состояния кодируются натуральными числами, можно считать любую программу функцией из
    \infty
    в
    \infty
    .
  5. Для всех частичных функций
    f : \infty \to \infty, \forall n \in \infty
    примем обозначение f(n)
    тттк f(n) определена
  6. Для всех частичных функций
    f : \infty \to \infty, \forall n \in \infty
    примем обозначение f(n)
    тттк f(n) не определена
Определение 2.26. Для всех частичных функций
f, g: \Gamma ' \to \Gamma ', \forall s,t \in S, f(s,t)=g(s,t)
тттк выполняется одно из условий:
  1. f(s,t)
    и g(s,t)
    , либо
  2. f(s,t)
    и g(s,t)
    и f(s,t) = g(s,t)




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