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

НУМЕРАЦИЯ

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

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

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

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

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

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

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

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

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

Часть теории Н., связанная с изучением нумераций Клини и Поста, а также их подобъектов, наиболее разработана, т. к. в этих случаях использование методов теории алгоритмов наиболее эффективно. Здесь в первую очередь изучаются т. н. вычислимые Н. Если множествоА,напр., является семейством рекурсивно перечислимых множеств, то Н.этого семейства наз. вычислимой, если отношение само является рекурсивно перечислимым. Множество классов эквивалентных вычислимых Н. семейства Аобозначают . Это множество, как и , частично упорядочивается отношением сводимости Н.. Максимальный элемент множества , если он существует, наз. главной вычислимой нумерацией семействаА.В частности, нумерации Клини и Поста являются главными вычислимыми Н. для соответствующих семейств Ф (всех одноместных частично рекурсивных функций) и Р(всех рекурсивно перечислимых множеств). Большое число работ в теории Н. посвящено изучению множеств При этом нужно учесть, что многие свойства частично рекурсивных функций и рекурсивно перечислимых множеств, выявленные в теории алгоритмов, по существу являются отражениями алгебраич. свойств множеств и . Так, напр., легко укладываются в схему теории Н. изучаемые в теории алгоритмов и играющие там важную роль так наз. m-степени множеств. Если рассматривать семействоА,состоящее всего из двух множеств и , тот-степени множеств есть не что иное, как L(A),ат-степени рекурсивно перечислимых множеств суть Имеется полное алгебраич. описание устройства множеств (см. [4]).

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

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

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

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

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

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


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


  1. нумерация—НУМЕРАЦИЯ лат. numeratio от numerо считаю счисление совокупность примов наименования и обозначения чисел. См. Счисление Цифры. i Цифровое обозначение предметов располож...Большая советская энциклопедия
  2. нумерация—лат. numeratio от numero считаю счисление совокупность примов наименования и обозначения чисел. См. Счисление Цифры. Цифровое обозначение предметов расположенных в пос...Большая Советская энциклопедия II
  3. нумерация—ж. numerazione нумерация страниц paginatura f Итальянорусский словарь. Синонимы номерация нумерование нумеровка пагинация сигнатура счисление фолиация цифрация цифровка...Большой итальяно-русский и русско-итальянский словарь
  4. нумерация—жNumerierung f номерация нумерование нумеровка пагинация сигнатура счисление фолиация цифрация цифровка...Большой немецко-русский и русско-немецкий словарь
  5. нумерация—нумерация ж Numerierung f cСинонимы номерация нумерование нумеровка пагинация сигнатура счисление фолиация цифрация цифровка...Большой немецко-русский и русско-немецкий словарь
  6. нумерация—ж.numeracin fem paginacin fem foliacin fem страниц...Большой русско-испанский словарь
  7. нумерация—сущ. жен. рода только ед. ч....Большой русско-украинский словарь
  8. нумерация—ж. numrotage m pagination f foliotage m страницem...Большой русско-французский словарь
  9. нумерация—порядковые номера отпечатанные на полях типогр. и почт марочных листов блоков реже на самой марке или ее поле. Это могут быть номера листов печатных форм цилиндров пласт...Большой филателистический словарь
  10. нумерация—ж.numrotage m pagination f foliotage m страниц номерация нумерование нумеровка пагинация сигнатура счисление фолиация цифрация цифровка...Большой французско-русский и русско-французский словарь
  11. нумерация—от лат. numero считаю обозначение предметовпоследовательными номерами совокупность таких номеров напр. нумерациядомов страниц. Способ выражения и обозначения чисел. См...Большой энциклопедический словарь II
  12. нумерация—НУМЕРАЦИЯ от лат. numero считаю обозначение предметов последовательными номерами совокупность таких номеров напр. нумерация домов страниц. Способ выражения и обозначен...Большой энциклопедический словарь III
  13. нумерация—НУМЕРАЦИЯ от лат. numero считаю обозначение предметов последовательными номерами совокупность таких номеров напр. нумерация домов страниц. Способ выражения и обозначен...Большой Энциклопедический словарь V
  14. нумерация—согласно Федеральному закону О связи от . ФЗ цифровое буквенное символьное обозначение или комбинации таких обозначений в том числе коды предназначенные для однозначног...Делопроизводство и архивное дело
  15. нумерация—от лат. нищего считаю обозначение предметов последовав номерами совокупность таких номеров напр. Н. домов страниц. Способ выражения и обозначения чисел. См. Счисление....Естествознание. Энциклопедический словарь
  16. нумерация—Печать как правило при помощи специальных устройствнумераторов меняющихся номеров на оттисках например на ценных бумагах бланках билетах нумерованных изданиях и пр. Кратк...Краткий толковый словарь по полиграфии
  17. нумерация—Нумерация numeratio нумерация страниц paginatio...Латинский словарь
  18. нумерация—и ж.em Действие по знач. глаг.em нумеровать.Нумерация страниц.Совокупность приемов наименования и обозначения чисел счисление.Цифровое обозначение предметов расположенных...Малый академический словарь
  19. нумерация—корень НУМЕР суффикс АЦИ окончание Я Основа слова НУМЕРАЦИВычисленный способ образования слова Суффиксальный НУМЕР АЦИ Я Слово Нумерация содержит следующие морфем...Морфемный разбор слова по составу
  20. нумерация—Начальная форма Нумерация единственное число женский род именительный падеж неодушевленное...Морфологический разбор существительных
  21. нумерация—нумерация . ж. Действие по знач. глаг. нумеровать. Обозначение предметов последовательными номерами. . ж. Раздел арифметики излагающий способы обозначения всевозможных ...Новый толково-словообразовательный словарь русского языка
  22. нумерация—нумерация нумерация и...Орфографический словарь
  23. нумерация—u жu Р.u Д.u Пр.u нумерации номерация нумерование нумеровка пагинация сигнатура счисление фолиация цифрация цифровка...Орфографический словарь русского языка
  24. нумерация—нмрлеу...Орысша-қазақша «Жеңіл және тоқыма өнеркәсібі» терминологиялық сөздік
  25. нумерация—нмрлеу...Орысша-қазақша «Математика» терминологиялық сөздік
  26. нумерация—. нумерация цифровое буквенное символьное обозначение или комбинации таких обозначений в том числе коды предназначенные для однозначного определения идентификации сети с...Официальная терминология
  27. нумерация—numration...Политехнический русско-французский словарь
  28. нумерация—нумерация нумерации нумерации нумераций нумерации нумерациям нумерацию нумерации нумерацией нумерациею нумерациями нумерации нумерациях...Полная акцентуированная парадигма по Зализняку
  29. нумерация—Орфографическая запись слова нумерация Ударение в слове нумерация Деление слова на слоги перенос слова нумерация Фонетическая транскрипция слова нумерация [нмираа] Харак...Полный фонетический разбор слов
  30. нумерация—от нем. numeration lt лат. numeratio исчисление счет печатаниеi как правило при помощи специальных устройствнумераторов меняющихся номеров на оттискахi или на готовом и...Реклама и полиграфия
  31. нумерация—действие см. Нумеровка и действие и результат система нумераця. За циею за нумерами за числами. ция страниц пагнаця действие нумерування сторнок....Російсько-український словник (Українська академія наук)
  32. нумерация—нумерация иСинонимы номерация нумерование нумеровка пагинация сигнатура счисление фолиация цифрация цифровка...Русский орфографический словарь
  33. нумерация—Ж numerasiya . nmrlm . nmrlr sras....Русско-азербайджанский словарь
  34. нумерация—numbering...Русско-английский машиностроительный словарь
  35. нумерация—A new method of numbering strongsites is employed. Синонимы номерация нумерование нумеровка пагинация сигнатура счисление фолиация цифрация цифровка...Русско-английский научно-технический словарь
  36. нумерация—enumeration листовem foliation полигр.u numbering numeration нумерация ж.u .strong счисление number system .strong цифровое обозначение numbering enumerationнумерация да...Русско-английский политехнический словарь
  37. нумерация—нумерация ж.i. numeration . цифровое обозначениеi numbering...Русско-английский словарь
  38. нумерация—нумерация ж. numbering нумерованный numbered нумерованное место reserved seat нумерованные кадры кино numbered frames нумеровать пронумеровать вн. number smth. нумерова...Русско-английский словарь II
  39. нумерация—f.indexing numbering enumerationСинонимы номерация нумерование нумеровка пагинация сигнатура счисление фолиация цифрация цифровка...Русско-английский словарь математических терминов
  40. нумерация—ж. нумерация страниц нумерация уровней сквозная нумерация...Русско-английский словарь по физике
  41. нумерация—enumeration numbering...Русско-английский словарь по электронике
  42. нумерация—enumeration counting numbering numeration...Русско-английский строительный словарь
  43. нумерация—ampLTengin.ampGT enumeration indexing number system numbering quantization rating нумерация пряжи нумерация страницСинонимы номерация нумерование нумеровка пагинация сигн...Русско-английский технический словарь
  44. нумерация—numbering numeration...Русско-английский экономический словарь
  45. нумерация—N...Русско-армянский словарь
  46. нумерация—Нумарацыя...Русско-белорусский словарь
  47. нумерация—нумарацыя жен.i...Русско-белорусский словарь II
  48. нумерация—szmozs номерация нумерование нумеровка пагинация сигнатура счисление фолиация цифрация цифровка...Русско-венгерский словарь
  49. нумерация—нумера Синонимы номерация нумерование нумеровка пагинация сигнатура счисление фолиация цифрация цифровка...Русско-ивритский словарь
  50. нумерация—numeracin...Русско-испанский автотранспортный словарь
  51. нумерация—numeracin...Русско-испанский экономический словарь
  52. нумерация—ж. numerazione f арабская нумерация порядковая нумерация римская нумерация нумерация страниц...Русско-итальянский политехнический словарь
  53. нумерация—ж. см. нумеровать. белг белглеу десятичная нумерация онды белг. нмрлер нумерация домов йлерд нмрлер...Русско-казахский словарь
  54. нумерация—нмрлеу...Русско-казахский терминологический словарь «Горное дело и металлургия»
  55. нумерация—нмрлеу...Русско-казахский терминологический словарь «История»
  56. нумерация—ж. нумерация . номерд номер коюу номер салуу . номерлер системасы....Русско-киргизский словарь
  57. нумерация—действиеem см. нумеровать нумерация страниц цифровое обозначениеem hoshm shzдесятичная нумерация номерация нумерование нумеровка пагинация сигнатура счисление фолиа...Русско-китайский словарь
  58. нумерация—numercija numurana numercija pagincija...Русско-латышский словарь
  59. нумерация—skaiiuot...Русско-литовский словарь
  60. нумерация—напр. документов массивов данныхem Benummerung Bezifferung Numeration...Русско-немецкий политехнический словарь
  61. нумерация—ж. Numerierung f....Русско-немецкий словарь
  62. нумерация—Bezifferung атомов в молекулеem Chiffrierung Durchnumerierung Numerierung...Русско-немецкий словарь по химии и химической технологии
  63. нумерация—Bezifferung атомов в молекуле Chiffrierung Durchnumerierung Numerierung...Русско-немецкий химический словарь
  64. нумерация—Numerierung...Русско-немецкий экономический словарь
  65. нумерация—нумерацияж страниц....Русско-новогреческий словарь
  66. нумерация—numerasjon номерация нумерование нумеровка пагинация сигнатура счисление фолиация цифрация цифровка...Русско-норвежский словарь
  67. нумерация—...Русско-персидский словарь
  68. нумерация—жnumerao fu страницem paginao f номерация нумерование нумеровка пагинация сигнатура счисление фолиация цифрация цифровка...Русско-португальский словарь
  69. нумерация—нумерация раамгузор номергузор...Русско-таджикский словарь
  70. нумерация—ж .см. нумеровать .номерлар н. домов йлрне номерлары...Русско-татарский словарь
  71. нумерация—numaralama номерация нумерование нумеровка пагинация сигнатура счисление фолиация цифрация цифровка...Русско-турецкий словарь
  72. нумерация—матем. техн. физ. нумераця двоичная нумерация десятичная нумерация индоарабская нумерация нумерация контуров нумерация множества нумерация пряжи позиционная нумера...Русско-украинский политехнический словарь
  73. нумерация—numrotage...Русско-французский словарь по химии
  74. нумерация—numerace oznaen seln soustava slovn...Русско-чешский словарь
  75. нумерация—.strong nummerdamine.strong nummerdus...Русско-эстонский словарь
  76. нумерация—нумерация иСинонимы номерация нумерование нумеровка пагинация сигнатура счисление фолиация цифрация цифровка...Русское словесное ударение
  77. нумерация—НУМЕРАЦИЯ лат. numeratio от numerus число количество. указания как писать числа и как их выговаривать. означение нескольких однородных предметов последовательными нуме...Словарь иностранных слов русского языка
  78. нумерация—считаю обозначение предметов последовательными номерами совокупность таких номеров например Н. домов Н. страниц. Счисление....Словарь исторических терминов
  79. нумерация—нумерация перечисление фолиация сигнатура цифровка нумерование цифрация нумеровка пагинация счисление номерация Словарь русских синонимов. нумерация сущ. колво синонимов ...Словарь синонимов II
  80. нумерация—нумерация перечисление фолиация сигнатура цифровка нумерование цифрация нумеровка пагинация счисление номерация...Словарь синонимов
  81. нумерация—нумарацыя...Слоўнік бугальтэрскае тэрмінолёгіі
  82. нумерация—НУМЕРАЦИЯ от лат. numero считаю обозначение предметов последовательными номерами совокупность таких номеров напр. нумерация домов страниц. Способ выражения и обозначен...Современный энциклопедический словарь
  83. нумерация—обозначение последовательными номерами.Синонимы номерация нумерование нумеровка пагинация сигнатура счисление фолиация цифрация цифровка...Справочный коммерческий словарь
  84. нумерация—. Цифровое буквенное символьное обозначение или комбинации таких обозначений в том числе коды предназначенные для однозначного определения идентификации сети связи и или ...Телекоммуникационный словарь
  85. нумерация—НУМЕРАЦИЯ нумеровать нумер и пр. см. номер....Толковый словарь живого великорусского языка
  86. нумерация—нумерация [лат. numeratio] счи с л е н и е часть арифметики излагающая способы обозначения всевозможных чисел посредством немногих названий и знаков обозначение предм...Толковый словарь иностранных слов
  87. нумерация—НУМЕРАЦИЯ и ж. . см. нумеровать. . Цифровое обозначение предметоврасположенных в последовательном порядке. Н. домов....Толковый словарь Ожегова
  88. нумерация—НУМЕРАЦИЯ нумерации ж. книжн. . только ед. Действие по глаг. нумеровать. . Цифровое обозначение предметов расположенных в последовательном порядке. По правой стороне улиц...Толковый словарь русского языка II
  89. нумерация—нумерация нумерация и ж. см. нумеровать. Цифровое обозначение предметов расположенных в последовательном порядке. Н. домов....Толковый словарь русского языка II
  90. нумерация—НУМЕРАЦИЯ и ж. . см. нумеровать. . Цифровое обозначение предметов расположенных в последовательном порядке. Нумерация домов....Толковый словарь русского языка
  91. нумерация—Ударение в слове нумерацияУдарение падает на букву аБезударные гласные в слове нумерация...Ударение и правописание
  92. нумерация—Rzeczownik нумерация f numeracja f...Универсальный русско-польский словарь
  93. нумерация—нумерация нумерации нумерации нумераций нумерации нумерациям нумерацию нумерации нумерацией нумерациею нумерациями нумерации нумерациях Источник Полная акцентуированная п...Формы слова
  94. нумерация—Урема Урания Уран Унция Унр Уния Умница Уманец Рунец Руна Румянец Руина Руан Рия Рин Риман Рим Риа Реум Рем Рая Рация Рацея Ранец Рами Рам Раия Нумерация Нумер Ниц Нея Не...Электронный словарь анаграмм русского языка
  95. нумерация—Нумерация лат. numeratio приложение законов образования чисел в употребляемых системах счисления к выражению числа словом словеснаяi Н.i или письменными знаками письме...Энциклопедический словарь
  96. нумерация—НУМЕРАЦИЯ от лат. numero считаю обозначение предметов последовательными номерами совокупность таких номеров напр. нумерация домов страниц. Способ выражения и обозначе...Энциклопедический словарь естествознания
  97. нумерация—лат. numeratio приложение законов образования чисел в употребляемых системах счисления к выражению числа словом словесная Н.em или письменными знаками письменная Н.em ...Энциклопедический словарь Ф.А. Брокгауза и И.А. Ефрона
  98. нумерация—как и польск. numeracja из лат. numeratio....Этимологический русскоязычный словарь Фасмера
  99. нумерация—нумерация нумерациякак и польск. numeracja из лат. numerti....Этимологический словарь русского языка (М. Фасмер.)