Общая теория алгоритмов
Необходимость нумерации произвольных объектов вызвана, прежде всего, необходимостью анализа различных задач, которые должны обрабатывать
алгоритмы в качестве исходной информации. Следовательно, для
того, чтобы рассматривать алгоритмы над алгоритмами, необходимо представлять
алгоритм (в данной главе — машину Тьюринга) в виде натуральных чисел.
Геделевская нумерация объектов Считается, что введена система Геделевской нумерации для всех объектов A, принадлежащих некоторому множеству M, если выполняются следующие два требования: существует натуральное число ng(A), которое однозначно определяется по A; для всех n, принадлежащих множеству натуральных чисел N, выполняется одно из двух условий: либо не существует объекта A, принадлежащего множеству M, такого, что n = ng(A); либо существует единственный объект A, принадлежащий M, такой, что n =ng(A) и этот объект однозначно восстанавливается по n.