НУМЕРАЦИЯ

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

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

Нумерованным множеством наз. пара НУМЕРАЦИЯ фото №2 где А- нек-рое счетное множество, а НУМЕРАЦИЯ фото №3 - некоторое отображение множества натуральных чисел НУМЕРАЦИЯ фото №4 на А. Отображение НУМЕРАЦИЯ фото №5 наз.нумерацией множества А. Если НУМЕРАЦИЯ фото №6 то пназ. номером объекта а при нумерации v. H. НУМЕРАЦИЯ фото №7 множества Асводится к Н. НУМЕРАЦИЯ фото №8 множества А(отношение сводимости Н. обозначается НУМЕРАЦИЯ фото №9 ), если существует с одноместная общерекурсивная функция f такая, что НУМЕРАЦИЯ фото №10 для всех НУМЕРАЦИЯ фото №11 . Нумерации НУМЕРАЦИЯ фото №12 и НУМЕРАЦИЯ фото №13 множества Аназ. эквивалентными, если НУМЕРАЦИЯ фото №14 и НУМЕРАЦИЯ фото №15 .С точки зрения теории Н. эквивалентные Н.

одного и того же множества неразличимы. По этой причине объектом исследования обычно является множество НУМЕРАЦИЯ фото №16 - множество классов эквивалентных Н. множества А, частично упорядоченное отношением сводимости Н. НУМЕРАЦИЯ фото №17 . Часто рассматривается и множество НУМЕРАЦИЯ фото №18 - множество классов эквивалентных Н. множества А, сводящихся к Н. НУМЕРАЦИЯ фото №19 . Множества НУМЕРАЦИЯ фото №20 и НУМЕРАЦИЯ фото №21 во многих случаях служат нек-рой "мерой сложности" множества А.

При сравнении Н. двух множеств Аи Восновным понятием является понятие морфизма. Морфизмом из нумерованного множества НУМЕРАЦИЯ фото №22 в нумерованное множество НУМЕРАЦИЯ фото №23 наз. всякое отображение НУМЕРАЦИЯ фото №24 из Ав В, для к-рого существует одноместная общере-курсивная функция НУМЕРАЦИЯ фото №25 такая, что НУМЕРАЦИЯ фото №26 для всех НУМЕРАЦИЯ фото №27 . Через НУМЕРАЦИЯ фото №28 обозначают множество всевозможных морфизмов из НУМЕРАЦИЯ фото №29 в НУМЕРАЦИЯ фото №30 . С изучением множеств Мог, в частности с выяснением возможности наделения этого множества "хорошими" Н., тесно связаны многие вопросы общей теории алгоритмов.

Категория НУМЕРАЦИЯ фото №31 нумерованных множеств состоит из нумерованных множеств и морфизмов. Исследование свойств этой категории НУМЕРАЦИЯ фото №32 является основной задачей теории Н. Исходным пунктом такого исследования часто является изучение связей нумерованных множеств с важнейшими конкретными Н.- нумерацией Клнни НУМЕРАЦИЯ фото №33 всех одноместных частично рекурсивных функций и нумераций Поста НУМЕРАЦИЯ фото №34 всех рекурсивно перечисли-мых множеств. В теории алгоритмов доказано существование двуместной частично рекурсивной функции НУМЕРАЦИЯ фото №35 универсальной для класса всех одноместных частично рекурсивных функций, т. е. такой, что для любой частично рекурсивной функции f(х)можно найти число НУМЕРАЦИЯ фото №36 такое, что НУМЕРАЦИЯ фото №37 Нумерация Клини j задается тогда следующим образом: НУМЕРАЦИЯ фото №38 Если НУМЕРАЦИЯ фото №39 обозначает область значений функции НУМЕРАЦИЯ фото №40 , то получаем нумерацию Поста НУМЕРАЦИЯ фото №41 всех рекурсивно перечислимых множеств.

Фундаментальную роль при исследовании категории НУМЕРАЦИЯ фото №42 играет введенное А. И. Мальцевым понятие полной Н., к-рое в самой общей форме синтезировало главные свойства нумераций Клини НУМЕРАЦИЯ фото №43 и Поста НУМЕРАЦИЯ фото №44 . Н. НУМЕРАЦИЯ фото №45 множества Аназ. полной, если среди элементов множества Аимеется такой выделенный элемент а, что для любой одноместной частично рекурсивной функции f существует одноместная общерекурсивная функция НУМЕРАЦИЯ фото №46 такая, что

НУМЕРАЦИЯ фото №47

Полные Н. играют роль "инъективных" элементов категории НУМЕРАЦИЯ фото №48 и наличие у Аполных Н. свидетельствует о значительной универсальности и важности класса объектов А.

В частности, и нумерация Клини НУМЕРАЦИЯ фото №49 частично рекурсивных функций, и нумерация Поста НУМЕРАЦИЯ фото №50 рекурсивно перечислимых множеств суть полные Н. (в первом случае выделенным элементом НУМЕРАЦИЯ фото №51 является нигде не определенная функция, а во втором - пустое множество). Важным направлением в исследовании категории НУМЕРАЦИЯ фото №52 является также выделение и изучение различных видов подобъектов нумерованных множеств (см. [4]).

Часть теории Н., связанная с изучением нумераций Клини и Поста, а также их подобъектов, наиболее разработана, т. к. в этих случаях использование методов теории алгоритмов наиболее эффективно. Здесь в первую очередь изучаются т. н. вычислимые Н. Если множество А, напр., является семейством рекурсивно перечислимых множеств, то Н. НУМЕРАЦИЯ фото №53 этого семейства наз. вычислимой, если отношение НУМЕРАЦИЯ фото №54 само является рекурсивно перечислимым. Множество классов эквивалентных вычислимых Н. семейства Аобозначают НУМЕРАЦИЯ фото №55 . Это множество, как и НУМЕРАЦИЯ фото №56 , частично упорядочивается отношением сводимости Н. НУМЕРАЦИЯ фото №57 . Максимальный элемент множества НУМЕРАЦИЯ фото №58 , если он существует, наз. главной вычислимой нумерацией семейства А. В частности, нумерации Клини и Поста являются главными вычислимыми Н. для соответствующих семейств Ф (всех одноместных частично рекурсивных функций) и Р(всех рекурсивно перечислимых множеств). Большое число работ в теории Н. посвящено изучению множеств НУМЕРАЦИЯ фото №59 При этом нужно учесть, что многие свойства частично рекурсивных функций и рекурсивно перечислимых множеств, выявленные в теории алгоритмов, по существу являются отражениями алгебраич. свойств множеств НУМЕРАЦИЯ фото №60 и НУМЕРАЦИЯ фото №61 . Так, напр., легко укладываются в схему теории Н. изучаемые в теории алгоритмов и играющие там важную роль так наз. m-степени множеств. Если рассматривать семейство А, состоящее всего из двух множеств НУМЕРАЦИЯ фото №62 и НУМЕРАЦИЯ фото №63 , то т- степени множеств есть не что иное, как L(A), а т- степени рекурсивно перечислимых множеств суть НУМЕРАЦИЯ фото №64 Имеется полное алгебраич. описание устройства множеств НУМЕРАЦИЯ фото №65 (см. [4]).

Пусть А- нек-рое семейство рекурсивно перечислимых множеств (для частично рекурсивных функций рассматриваемые понятия вводятся аналогично). Индексным (или номерным) множеством семейства Аназ. множество

НУМЕРАЦИЯ фото №66

номеров рекурсивно перечислимых множеств семейства Ав нумерации Поста. В теории Н. изучаются индексные множества НУМЕРАЦИЯ фото №67 для различных семейств А. Так, теорема Раиса - Шапиро дает описание тех семейств А, для к-рых множество НУМЕРАЦИЯ фото №68 рекурсивно перечислимо. Такие семейства в теории Н. носят название вполне перечислимых классов. Даны также описания других видов подобъектов нумерации Поста - специальных стандартных классов, факторизации и ретрактов. Большую роль играют т. н. стандартные классы.

Семейство НУМЕРАЦИЯ фото №69 рекурсивно перечислимых множеств наз. стандартным классом, если существует общерекурсивная функция НУМЕРАЦИЯ фото №70 такая, что: НУМЕРАЦИЯ фото №71 НУМЕРАЦИЯ фото №72 при этом, если НУМЕРАЦИЯ фото №73 Стандартные классы тесно связаны с полными Н. В настоящее время (1982) нет удовлетворительного описания стандартных классов. Такое описание могло бы пролить свет на многие вопросы теории алгоритмов. В теории Н. также рассматривались главные, эффективно-главные и другие виды подобъектов нумерации Поста (см. [4]).

Алгоритмич. аналогом понятия алгебраической системы, т. е. множества с заданными на нем функциями и предикатами, является понятие нумерованной, или конструктивной, алгебраической системы. Идея состоит в следующем. Рассматриваемое множество Анаделяется Н. Вместо функций и предикатов, заданных на объектах множества А, рассматриваются "переводы" этих функций и предикатов, оперирующие соответствующим образом с натуральными числами как с номерами объектов множества А. Если при этом можно добиться того, чтобы эти "переводы" функций и предикатов были общерекурсивными, то говорят, что данная алгебраич. система конструктивизируема. Первое систематич. изучение теории конструктивных алгебраич. систем было предпринято А. И. Мальцевым [3].

Следует отметить два наиболее ярких применения теории Н. к задачам теории алгоритмов: завершение построения теории Майхилла об универсальных объектах и построение теории вычислимых функционалов конечных типов (см. [4]). Методы и результаты теории Н. могут быть использованы в смежных к математич. логике и теории алгоритмов науках, в частности в программировании. Так, с помощью теории Н. могут быть решены нек-рые вопросы семантики языков программирования.

Лит.:[1] Мальцев А. И., Алгоритмы и рекурсивные функции, М., 1965; [2] его же, "Успехи матем. наук", 1961, т. 16, в. 3, с. 3-60; [3] Успенский В. А.. Лекции о вычислимых функциях, М., 1960; [4] Ершов Ю. Л., Теория нумераций, М., 1977.

Синонимы:

номерация, нумерование, нумеровка, пагинация, сигнатура, счисление, фолиация, цифрация, цифровка

Смотреть больше слов в «Математической энциклопедии»

НУМЕРИЧЕСКИ ВЫРАЗИМЫЙ ПРЕДИКАТ →← НУЛЬСИСТЕМА

НУМЕРАЦИЯ

Синонимы слова "НУМЕРАЦИЯ":

Смотреть что такое НУМЕРАЦИЯ в других словарях:

Рекомендуем посмотреть: