Осв. понятиями Н. т. являются понятия нумерованного мн-ва и морфизма нумерованных множеств. Если S не более чем счетное мн-во, N — мн-во натуральных чисел, то всякое отображение v мн-ва N на
нумерацией мн-ва S. Пара
, где v — нумерация мн-ва
нумерованным мн-вом. Морфизмом из нумерованного мн-ва
в нумерованное мн-во
всякое отображение р, из
для которого существует одноместная общерекурсивная функция
такая, что для всех
. В частном случае, когда
тождественное отображение, говорят о сводимости нумерации
к нумерации
Иногда рассматривают более широкое понятие нумерованного мн-ва, а именно: нумерация v отображает не все мн-во натуральных чисел N в a S, а некоторое его подмн-во. Во многих важных случаях (вычислимые нумерации, нумерации конечно порожденных алгебр и др.) такое расширение понятия оказывается ненужным, т. к. легко сводится к исходному определению. Некоторая трудность возникает при определении сводимости таких нумераций (возможны несколько естественных, но не эквивалентных определений) Из исследований, в которых именно такой попягие нумерации существенно важно, следует указать работы по различным иерархиям в алгоритмов теории, где используют такие нумерации ординалов и исследования по эффективным операциям.
Результаты, полученные в Н. т., разбиваются на три раздела: общая Н. т., вычислимые нумерации, нумерованные алгебры и модели.
Осн. задачей общей Н. т. является выработка и изучение осн. понятий и методов Н. т. Одним из наиболее важных понятий является понятие полно нумерованного мн-ва. Это понятие позволило с единой точки зрения осознать такие важные в теории рекурсивных функций результаты, как теорема Майхилла о креативных мн-вах и теорема Роджерса об изоморфизме гёделевских нумераций частичнорекурсивных ф-ций. С каждым нумерованным мн-вом
связывается частично-упорядоченное мн-во
классов эквивалентных нумераций, сводящихся к v. точнее: элементами мн-ва
являются следующие семейства нумераций мн-ва S. если
, то
нумерация мн-ва
Отношение частичного порядка на
задается так
для
тогда и только тогда, когда
Оказывается, что
является верхней иолурешеткой, т. е. любые два элемента из
имеют точную верхнюю грань;
есть наибольший элемент
. Полурешетка
интересна как некоторая характеристика «сложности» нумерованного мн-ва у. Определяется и изучается ряд других структур, связанных с самим нумерованным мв-вом и со всем классом (категорией) нумерованных множеств.
Наиболее разработанным разделом Н. т. является раздел вычислимые нумерации. Осн. объектом изучения служат классы рекурсивно-перечислимых множеств или частично-рекурсивных функций, снабженных вычислимой нумерацией. Определим понятие вычислимой нумерации для семейства
рекурсивно-перечислимых множеств. Пусть
нумерация, тогда v — вычислима, если мн-во пар
рекурсивно-перечислимо. Если v — такая вычислимая нумерация семейства R, что любая другая вычислимая нумерация R сводится к v, то
главной вычислимой нумерацией R. Этот раздел рассматривает вопросы существования у тех или иных семейств различного рода специальных нумераций (однозначных, позитивных, главных и т. п.), изучает полурешетки
для конкретных важных нумерованных множеств. Изучение последних тесно связано с исследованиями
-степеней. Например, если R состоит из двух множеств — пустого и одноэлементного,
главная вычислимая нумерация, то полурешетка
изоморфна полурешетке рекурсивно-перечислимых
-степеней. Сложность строения
для главных вычислимых нумераций семейства рекурсивно-перечислимых множеств является характеристикой сложности этого семейства в целом, в отличие от др
характеристик сложности, которые изучаются в теории алгоритмов и характеризуют только сложность отдельно взятого мн-ва (функции).
Раздел нумерованные алгебры и модели может быть отнесен к применениям Н. т. Осн. объектом изучения служат алгебраические системы (алгебры, модели), снабженные нумерациями. Классические алгоритмические проблемы алгебры находят естественную формулировку на языке нумерованных алгебр. Другие естественные проблемы этого раздела: существование и единственность нумерации алгебры с заданными свойствами, возможность распространения нумерации R подалгебры на всю алгебру, нумерации подалгебр и многие другие.
Понятие нумерации впервые было использовано К. Гёделем при доказательстве знаменитых теорем о неполноте (см. Гёделя теоремы о неполноте). По предложению А. Н. Колмогорова было начато систематическое изучение нумерованных множеств. Много сделал для систематизации понятий Н. т. А. И. Мальцев, которому принадлежит, в частности, понятие полно нумерованного мн-ва.
Лит.: Успенский В. А. Лекции о вычислимых функциях. М., 1960 [библиогр. с. 476—481]; Мальцев А. И. Конструктивные алгебры. I. «Успехи математических наук», 1961, т. 16, в. 3; Мальцев А. И. Алгоритмы и рекурсивные функции. М., 1965 [библиогр. с. 375—381]; Ершов Ю. Л. Теория нумераций, ч. 1-2. Новосибирск, 1969—73.
Ю. Л. Ершов.