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

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

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

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

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

Нотация
$\langle s,t \rangle$
предназначена для обозначения состояния системы и фактически является кодом этого состояния, представленным натуральным числом.
Для всех частичных функций
$f : \infty \to \infty, \forall s,t \in S: f(s,t) := f(\langle s,t \rangle)$
Любая программа переводит систему из одного состояния в другое, учитывая, что состояния кодируются натуральными числами, можно считать любую программу функцией из
$\infty$
в
$\infty$
.
Для всех частичных функций
$f : \infty \to \infty, \forall n \in \infty$
примем обозначение f(n)
тттк f(n) определена
Для всех частичных функций
$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)$

тттк выполняется одно из условий:

f(s,t)
и g(s,t)
, либо
f(s,t)
и g(s,t)
и f(s,t) = g(s,t)

Содержание Назад Вперед