Принятые обозначения
В дальнейшем изложении будет считаться, что данные и программы, во-первых, различимы, как это обычно и бывает в компьютерных системах, а во-вторых, могут быть закодированы натуральными числами. Поскольку и данные и программы всегда имеют ограниченный размер и ограниченный алфавит для их представления, принципиальная возможность взаимно однозначного кодирования натуральными числами сомнений не вызывает.
Исходя из сказанного, состояние некой вычислительной системы с точки зрения выполняющейся программы, может быть описано как набор доступных программе данных и других программ, что может быть выражено как наборы или последовательности натуральных чисел. Действие любой программы заключается в том, чтобы из одного набора данных и программ получить другой набор данных и программ.
Ниже везде неявно подразумевается описанная интерпретация вычислительной системы.
- Обозначим S - множество всех конечных последовательностей натуральных чисел, . Таким образом элемент S может обозначать либо набор файлов данных, либо набор файлов программ, закодированных при помощи натуральных чисел.
- Обозначим e - вычислимую инъективную функцию из S?S на с вычислимой обратной функцией, . По тому же принципу, что и программы и данные, натуральными числами могут кодироваться и состояния системы. Функция e взаимно однозначно ставит в соответствие набору данных и программ натуральное число. Иными словами e - однозначная нумерация состояний системы.
-
Нотация
предназначена для обозначения состояния системы и фактически является кодом этого состояния, представленным натуральным числом. - Для всех частичных функций Любая программа переводит систему из одного состояния в другое, учитывая, что состояния кодируются натуральными числами, можно считать любую программу функцией из в .
- Для всех частичных функций примем обозначение f(n) тттк f(n) определена
- Для всех частичных функций примем обозначение f(n) тттк f(n) не определена
Определение 2.26. Для всех частичных функций
тттк выполняется одно из условий:
- f(s,t) и g(s,t), либо
- f(s,t) и g(s,t) и f(s,t) = g(s,t)
Содержание Назад Вперед