Нумерация

- основное понятие раздела теории алгоритмов - теории нумераций, изучающей общие свойства классов объектов, занумерованных с помощью каких-либо конструктивных объектов. В роли конструктивных объектов, служащих номерами элементов рассматриваемых классов, чаще всего выступают натуральные числа. Идея Н. объектов нечисловой природы (напр., ло-гич. формул) натуральными числами и перенесение содержательных утверждений об этих объектах в область формальной арифметики натуральных чисел впервые были использованы К. Гёделем [img: http://localhost:8080/file/031512-562.jpg] при доказательстве Гёделя теоремы о неполноте арифметики Пеано. В дальнейшем эти идеи были использованы для Н. фундаментальных объектов теории алгоритмов таких, как Тьюринга машин, частично рекурсивных функций и рекурсивно перечислимых множеств. Наделение этих классов объектов подходящими Н. позволило во многих случаях выяснить более отчетливо природу этих объектов, выявить ряд их важных и новых свойств. Так возникла идея о систематич. изучении Н. произвольных множеств. При реализации этой идеи было замечено, что многие известные результаты теории алгоритмов оказываются следствиями общих закономерностей теории Н. (о построении теории Н., создании ее специфич. понятий и методов, о формировании перспективных направлений в теории Н. см. [1] - [4]). В частности, был плодотворно использован язык теории категорий, позволивший взглянуть на проблематику теории Н. с новой точки зрения (см. [4]). Нумерованным множеством наз. пара [img: http://localhost:8080/file/031512-563.jpg] где А- нек-рое счетное множество, а [img: http://localhost:8080/file/031512-564.jpg] - некоторое отображение множества натуральных чисел [img: http://localhost:8080/file/031512-565.jpg] на А. Отображение [img: http://localhost:8080/file/031512-566.jpg] наз. нумерацией множества А. Если [img: http://localhost:8080/file/031512-567.jpg] то пназ. номером объекта а при нумерации v. H. [img: http://localhost:8080/file/031512-568.jpg] множества Асводится к Н. [img: http://localhost:8080/file/031512-569.jpg] множества А(отношение сводимости Н. обозначается [img: http://localhost:8080/file/031512-570.jpg]), если существует с одноместная общерекурсивная функция f такая, что [img: http://localhost:8080/file/031512-571.jpg] для всех [img: http://localhost:8080/file/031512-572.jpg]. Нумерации [img: http://localhost:8080/file/031512-573.jpg] и [img: http://localhost:8080/file/031512-574.jpg] множества Аназ. эквивалентными, если [img: http://localhost:8080/file/031512-575.jpg] и [img: http://localhost:8080/file/031512-576.jpg].С точки зрения теории Н. эквивалентные Н. одного и того же множества неразличимы. По этой причине объектом исследования обычно является множество [img: http://localhost:8080/file/031512-577.jpg] - множество классов эквивалентных Н. множества А, частично упорядоченное отношением сводимости Н. [img: http://localhost:8080/file/031512-578.jpg]. Часто рассматривается и множество [img: http://localhost:8080/file/031512-579.jpg] - множество классов эквивалентных Н. множества А, сводящихся к Н. [img: http://localhost:8080/file/031512-580.jpg]. Множества [img: http://localhost:8080/file/031512-581.jpg] и [img: http://localhost:8080/file/031512-582.jpg] во многих случаях служат нек-рой "мерой сложности" множества А. При сравнении Н. двух множеств Аи Восновным понятием является понятие морфизма. Морфизмом из нумерованного множества [img: http://localhost:8080/file/031512-583.jpg] в нумерованное множество [img: http://localhost:8080/file/031512-584.jpg] наз. всякое отображение [img: http://localhost:8080/file/031512-585.jpg] из Ав В, для к-рого существует одноместная общере-курсивная функция [img: http://localhost:8080/file/031512-586.jpg] такая, что [img: http://localhost:8080/file/031512-587.jpg] для всех [img: http://localhost:8080/file/031512-588.jpg]. Через [img: http://localhost:8080/file/031512-589.jpg] обозначают множество всевозможных морфизмов из [img: http://localhost:8080/file/031512-590.jpg] в [img: http://localhost:8080/file/031512-591.jpg]. С изучением множеств Мог, в частности с выяснением возможности наделения этого множества "хорошими" Н., тесно связаны многие вопросы общей теории алгоритмов. Категория [img: http://localhost:8080/file/031512-592.jpg] нумерованных множеств состоит из нумерованных множеств и морфизмов. Исследование свойств этой категории [img: http://localhost:8080/file/031512-593.jpg] является основной задачей теории Н. Исходным пунктом такого исследования часто является изучение связей нумерованных множеств с важнейшими конкретными Н.- нумерацией Клнни [img: http://localhost:8080/file/031512-594.jpg] всех одноместных частично рекурсивных функций и нумераций Поста [img: http://localhost:8080/file/031512-595.jpg] всех рекурсивно перечисли-мых множеств. В теории алгоритмов доказано существование двуместной частично рекурсивной функции [img: http://localhost:8080/file/031512-596.jpg] универсальной для класса всех одноместных частично рекурсивных функций, т. е. такой, что для любой частично рекурсивной функции f(х)можно найти число [img: http://localhost:8080/file/031512-597.jpg] такое, что [img: http://localhost:8080/file/031512-598.jpg] Нумерация Клини j задается тогда следующим образом: [img: http://localhost:8080/file/031512-599.jpg] Если [img: http://localhost:8080/file/031512-600.jpg] обозначает область значений функции [img: http://localhost:8080/file/031512-601.jpg], то получаем нумерацию Поста [img: http://localhost:8080/file/031512-602.jpg] всех рекурсивно перечислимых множеств. Фундаментальную роль при исследовании категории [img: http://localhost:8080/file/031512-603.jpg] играет введенное А. И. Мальцевым понятие полной Н., к-рое в самой общей форме синтезировало главные свойства нумераций Клини [img: http://localhost:8080/file/031512-604.jpg] и Поста [img: http://localhost:8080/file/031512-605.jpg]. Н. [img: http://localhost:8080/file/031512-606.jpg] множества Аназ. полной, если среди элементов множества Аимеется такой выделенный элемент а, что для любой одноместной частично рекурсивной функции f существует одноместная общерекурсивная функция [img: http://localhost:8080/file/031512-607.jpg] такая, что [img: http://localhost:8080/file/031512-608.jpg] Полные Н. играют роль "инъективных" элементов категории [img: http://localhost:8080/file/031512-609.jpg] и наличие у Аполных Н. свидетельствует о значительной универсальности и важности класса объектов А. В частности, и нумерация Клини [img: http://localhost:8080/file/031513-1.jpg] частично рекурсивных функций, и нумерация Поста [img: http://localhost:8080/file/031513-2.jpg] рекурсивно перечислимых множеств суть полные Н. (в первом случае выделенным элементом [img: http://localhost:8080/file/031513-3.jpg] является нигде не определенная функция, а во втором - пустое множество). Важным направлением в исследовании категории [img: http://localhost:8080/file/031513-4.jpg] является также выделение и изучение различных видов подобъектов нумерованных множеств (см. [4]). Часть теории Н., связанная с изучением нумераций Клини и Поста, а также их подобъектов, наиболее разработана, т. к. в этих случаях использование методов теории алгоритмов наиболее эффективно. Здесь в первую очередь изучаются т. н. вычислимые Н. Если множество А, напр., является семейством рекурсивно перечислимых множеств, то Н. [img: http://localhost:8080/file/031513-5.jpg] этого семейства наз. вычислимой, если отношение [img: http://localhost:8080/file/031513-6.jpg] само является рекурсивно перечислимым. Множество классов эквивалентных вычислимых Н. семейства Аобозначают [img: http://localhost:8080/file/031513-7.jpg]. Это множество, как и [img: http://localhost:8080/file/031513-8.jpg], частично упорядочивается отношением сводимости Н. [img: http://localhost:8080/file/031513-9.jpg]. Максимальный элемент множества [img: http://localhost:8080/file/031513-10.jpg], если он существует, наз. главной вычислимой нумерацией семейства А. В частности, нумерации Клини и Поста являются главными вычислимыми Н. для соответствующих семейств Ф (всех одноместных частично рекурсивных функций) и Р(всех рекурсивно перечислимых множеств). Большое число работ в теории Н. посвящено изучению множеств [img: http://localhost:8080/file/031513-11.jpg] При этом нужно учесть, что многие свойства частично рекурсивных функций и рекурсивно перечислимых множеств, выявленные в теории алгоритмов, по существу являются отражениями алгебраич. свойств множеств [img: http://localhost:8080/file/031513-12.jpg] и [img: http://localhost:8080/file/031513-13.jpg]. Так, напр., легко укладываются в схему теории Н. изучаемые в теории алгоритмов и играющие там важную роль так наз. m-степени множеств. Если рассматривать семейство А, состоящее всего из двух множеств [img: http://localhost:8080/file/031513-14.jpg] и [img: http://localhost:8080/file/031513-15.jpg], то т- степени множеств есть не что иное, как L(A), а т- степени рекурсивно перечислимых множеств суть [img: http://localhost:8080/file/031513-16.jpg] Имеется полное алгебраич. описание устройства множеств [img: http://localhost:8080/file/031513-17.jpg] (см. [4]). Пусть А- нек-рое семейство рекурсивно перечислимых множеств (для частично рекурсивных функций рассматриваемые понятия вводятся аналогично). Индексным (или номерным) множеством семейства Аназ. множество [img: http://localhost:8080/file/031513-18.jpg] номеров рекурсивно перечислимых множеств семейства Ав нумерации Поста. В теории Н. изучаются индексные множества [img: http://localhost:8080/file/031513-19.jpg] для различных семейств А. Так, теорема Раиса - Шапиро дает описание тех семейств А, для к-рых множество [img: http://localhost:8080/file/031513-20.jpg] рекурсивно перечислимо. Такие семейства в теории Н. носят название вполне перечислимых классов. Даны также описания других видов подобъектов нумерации Поста - специальных стандартных классов, факторизации и ретрактов. Большую роль играют т. н. стандартные классы. Семейство [img: http://localhost:8080/file/031513-21.jpg] рекурсивно перечислимых множеств наз. стандартным классом, если существует общерекурсивная функция [img: http://localhost:8080/file/031513-22.jpg] такая, что: [img: http://localhost:8080/file/031513-23.jpg] [img: http://localhost:8080/file/031513-24.jpg] при этом, если [img: http://localhost:8080/file/031513-25.jpg] Стандартные классы тесно связаны с полными Н. В настоящее время (1982) нет удовлетворительного описания стандартных классов. Такое описание могло бы пролить свет на многие вопросы теории алгоритмов. В теории Н. также рассматривались главные, эффективно-главные и другие виды подобъектов нумерации Поста (см. [4]). Алгоритмич. аналогом понятия алгебраической системы, т. е. множества с заданными на нем функциями и предикатами, является понятие нумерованной, или конструктивной, алгебраической системы. Идея состоит в следующем. Рассматриваемое множество Анаделяется Н. Вместо функций и предикатов, заданных на объектах множества А, рассматриваются "переводы" этих функций и предикатов, оперирующие соответствующим образом с натуральными числами как с номерами объектов множества А. Если при этом можно добиться того, чтобы эти "переводы" функций и предикатов были общерекурсивными, то говорят, что данная алгебраич. система конструктивизируема. Первое систематич. изучение теории конструктивных алгебраич. систем было предпринято А. И. Мальцевым [3]. Следует отметить два наиболее ярких применения теории Н. к задачам теории алгоритмов: завершение построения теории Майхилла об универсальных объектах и построение теории вычислимых функционалов конечных типов (см. [4]). Методы и результаты теории Н. могут быть использованы в смежных к математич. логике и теории алгоритмов науках, в частности в программировании. Так, с помощью теории Н. могут быть решены нек-рые вопросы семантики языков программирования.