Математическая энциклопедия - нумерация

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

Идея Н. объектов нечисловой природы (напр., ло-гич. формул) натуральными числами и перенесение содержательных утверждений об этих объектах в область формальной арифметики натуральных чисел впервые были использованы К. Гёделем при доказательстве Гёделя теоремы о неполноте арифметики Пеано. В дальнейшем эти идеи были использованы для Н. фундаментальных объектов теории алгоритмов таких, как Тьюринга машин, частично рекурсивных функций и рекурсивно перечислимых множеств. Наделение этих классов объектов подходящими Н. позволило во многих случаях выяснить более отчетливо природу этих объектов, выявить ряд их важных и новых свойств. Так возникла идея о систематич. изучении Н. произвольных множеств. При реализации этой идеи было замечено, что многие известные результаты теории алгоритмов оказываются следствиями общих закономерностей теории Н. (о построении теории Н., создании ее специфич. понятий и методов, о формировании перспективных направлений в теории Н. см. [1] [4]). В частности, был плодотворно использован язык теории категорий, позволивший взглянуть на проблематику теории Н. с новой точки зрения (см. [4]).

Нумерованным множеством наз. пара где Анек-рое счетное множество, а некоторое отображение множества натуральных чисел на А. Отображение наз. нумерацией множества А. Если то пназ. номером объекта а при нумерации v. H.множества Асводится к Н. множества А(отношение сводимости Н. обозначается ), если существует с одноместная общерекурсивная функция f такая, что для всех . Нумерации и множества Аназ. эквивалентными, если и .С точки зрения теории Н. эквивалентные Н.

одного и того же множества неразличимы. По этой причине объектом исследования обычно является множество множество классов эквивалентных Н. множества А, частично упорядоченное отношением сводимости Н.. Часто рассматривается и множество множество классов эквивалентных Н. множества А, сводящихся к Н. . Множества и во многих случаях служат нек-рой "мерой сложности" множества А.

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

Категория нумерованных множеств состоит из нумерованных множеств и морфизмов. Исследование свойств этой категории является основной задачей теории Н. Исходным пунктом такого исследования часто является изучение связей нумерованных множеств с важнейшими конкретными Н.нумерацией Клнни всех одноместных частично рекурсивных функций и нумераций Поста всех рекурсивно перечисли-мых множеств. В теории алгоритмов доказано существование двуместной частично рекурсивной функции универсальной для класса всех одноместных частично рекурсивных функций, т. е. такой, что для любой частично рекурсивной функции f(х)можно найти число такое, что Нумерация Клини j задается тогда следующим образом: Если обозначает область значений функции , то получаем нумерацию Поста всех рекурсивно перечислимых множеств.

Фундаментальную роль при исследовании категории играет введенное А. И. Мальцевым понятие полной Н., к-рое в самой общей форме синтезировало главные свойства нумераций Клини и Поста . Н. множества Аназ. полной, если среди элементов множества Аимеется такой выделенный элемент а, что для любой одноместной частично рекурсивной функции f существует одноместная общерекурсивная функция такая, что

Полные Н. играют роль "инъективных" элементов категории и наличие у Аполных Н. свидетельствует о значительной универсальности и важности класса объектов А.

В частности, и нумерация Клини частично рекурсивных функций, и нумерация Поста рекурсивно перечислимых множеств суть полные Н. (в первом случае выделенным элементом является нигде не определенная функция, а во втором пустое множество). Важным направлением в исследовании категории является также выделение и изучение различных видов подобъектов нумерованных множеств (см. [4]).