Алгебраические и структурные свойства полурешеток Роджерса в иерархии Ершова

• Автор: Оспичев, Сергей Сергеевич
• Шифр специальности: 01.01.06
• Научная степень: Кандидатская
• Год защиты: 2013
• Место защиты: Новосибирск
• Количество страниц: 72 с.

Оглавление
Введение
Определения
Иерархия Ершова
Вычислимые нумерации
1 Общие свойства вычислимых нумераций и мощность полурешеток Роджерса
1.1 Вычислимые нумерации классов Е”1 и Д~
1.2 Двухэлементные семейства
1.3 Бесконечное семейство Ец ^-множеств с единственной вычислимой
нумерацией
1.4 Семейства без главных нумераций
2 Минимальные нумерации
2.1 Нумерации семейств множеств конечных уровней иерархии Ершова
2.2 Фридбергова нумерация семейства всех Е^-множеств
2.3 Бесконечные Е~1-вычислимые семейства без
фридберговых нумераций
Список литературы

Введение
Теория нумераций была развита для исследования алгоритмических свойств классов абстрактных объектов методами классической вычислимости, кодированием информации о них и их связей через свойства их номеров (имен). Впервые эффективность этого подхода была продемонстрирована в классической работе К. Геделя о неполноте арифметики.
В дальнейшем, С. К. Клини [1] построил универсальную частично вычислимую функцию (другими словами, вычислимую нумерацию всех частично вычислимых функций). Результат Клини имеет огромное значение для теории вычислимости.
Понятие нумерации, как математического объекта, было введено А.Н. Колмогоровым [2], а его ученик, В. А. Успенский занимался изучением вычислимых нумераций частично вычислимых функций [3], [4].
X. Роджерс [5], [6] исследовал вычислимые нумерации семейства всех частично вычислимых функций и вычислимо перечислимых множеств. Именно им было введено понятие Com(S) всех вычислимых нумераций семейства S. Отношение сводимости ^ между вычислимыми нумерациями определяет предпорядок на классе всех вычислимых нумераций. Факторизация по отношению эквивалентности = , определяемому данным предпорядком, позволяет построить частично упорядоченное множество 7Z(S) = (Com(S)/=,=$), образующее верхнюю полурешетку вычислимых нумераций семейства S. Роджерс рассматривал только те вычислимые нумерации, степени которых соответствовали наибольшему элементу описанной полурешетки. Минимальные элементы 7^(5), а также некоторые другие свойства были позднее представлены Р. Ф. Фрндбергом (R. F. Friedberg) [7], А. И. Мальцевым [8] и М. Б. Пур-Эль (М. В. Pour-El) [9].
Дальнейшее изучение и развитие теории вычислимых нумераций было продолжено Ю.Л. Ершовым [10]-[13], А. X. Лахланом (А.Н. Lachlan) [14],
A. Б. Хуторсцким [15]-[18], С. С. Марченковым [19], [20], В. В. Выогиным [21]-[23],
B. Л. Селивановым [24], [25], С. С. Гончаровым [26]-[30], С. А. Бадаевым [31]-(35],

М. Куммером (М. Кшпшег) [36], А. Сорби (А. БогЫ) [37], С.Ю. Подзоровым [38], Ж. Т. Таласбаевой [39] и другими.
Результаты классической теории вычислимых нумераций нашли наибольшее применение в рекурсивной математике [40],[41]. Так, метод построения семейств вычислимо перечислимых множеств с конечным числом вычислимых фридберговых нумераций, предложенный С. С. Гончаровым в [26], послужил отправной точкой для исследования алгоритмических размерностей рекурсивных моделей [28], [29], [42].
Теория нумераций нашла применение и в классической рекурсивной теории. Например, используя упомянутую теорему Гончарова [26] о числе вычислимых фридберговых нумераций семейств вычислимо перечислимых множеств, М. Куммер [43] нашел решение известной задачи о типах рекурсивных изоморфизмов частично вычислимых функций ([5],глава 4). Точнее, он доказал, что для любого к € ш существует вычислимая функция, обладающая ровно к типами рекурсивных изоморфизмов.
Далее в работе мы приведем обзор результатов но вычислимым нумерациям в известных иерархиях множеств, таких как иерархия Ершова (разностная иерархия) и арифметическая иерархия. В работе С. С. Гончарова и А. Сорби [37] был предложен новый общий подход к введению понятия вычислимого семейства конструктивных объектов, имеющих описание в языке, допускающем геделевскую нумерацию формул. В рамках подхода Гончарова - Сорби оказалось возможным подойти с единых позиций к понятию вычислимости семейств таких конструктивных объектов, как вычислимо перечислимые множества, конструктивные модели, семейства вычислимых морфизмов и т. д. Этот подход также позволяет ввести единообразное понятие вычислимого семейства множеств для иерархий Ершова и Клини - Мостовского (арифметической), а также понятие полурешетки Роджерса для подобных семейств. Согласно подходу Гончарова - Сорби, вычислимость нумерации а семейства множеств из данного класса К, эквивалентна определимости ее универсального множества {(ж, тг)|.т £ сг(?1)} в терминах класса /С.
В случае семейств вычислимо перечислимых множеств (1С = Е|), такой подход

Следствие 1.15. Если семейство 5 С Д® включает в себя Е“1 -направленное вычислимое подсемейство О С Б и не содержит объединетм [^Я, если е(а) = 1 (пересечение ("10, если е(а) = 0), а ф 0, то семейство Б не обладает Е^“1-вычислимой главной нулюрацией, Ь 6 О.
Предложение 1.16. Существует вычислимое семейство Т и вычислимое множество Т, такие что для семейства Т не существует Е“1 -вычислимой главной нумерации, но для семейства Т[^{Т) такая нумерация существует.
Доказательство. В качестве семейства Т возьмем семейство собственных начальных сегментов натурального ряда, точнее:
Г = {0, {0}, {0,1},... }.
А в качестве Т возьмем ш.
То, что для семейства Т не существует Е~ '-вычислимой главной нумерации следует из 1.15. Перейдем ко второй части.
Пусть ;/ - ЕШвычислимая главная нумерация семейства всех ЕШмножеств 11 (ртф) - Е“1-аппроксимация нумерации и. Покажем, что Т' = Т[]Т является п-подсемейством в Е“1 относительно нумерации V. Для этого предъявим вычислимую функцию к, такую что:
1- 1/!,(,:) £ Т'
2. ие £ 7 +* ^Тт(е) — г'е-
Мы будем строить Е~ '-вычислимую нумерацию р. (точнее, Е“1-аппроксимацию {/,<]))> а значит, будет существовать вычислимая функция к, которая сводит нумерацию /1 к V, которая и будет искомой функцией.
Перейдем к описанию конструкции для / и д (для каждого е £ ш):
Шаг в = 0. Полагаем, /(е, х, 0) = 0, д(е, х, 0) не определена для всех х £ и/.
Шаг в+П Ищем такой у ^ й, что для всех х ^ у выполняется <р(е,:х,в + 1) = 1 и для всех у < х ^ в выполняется <^з(е, х, в + 1) =0, т. е. такой у, что па первых