НУМЕРАЦИЙ ТЕОРИЯ

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

Осв. понятиями Н. т. являются понятия нумерованного мн-ва и морфизма нумерованных множеств. Если 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.

Ю. Л. Ершов.