Структурные свойства тьюринговых степеней множеств из иерархии Ершова

• Автор: Ямалеев, Марс Мансурович
• Шифр специальности: 01.01.06
• Научная степень: Кандидатская
• Год защиты: 2009
• Место защиты: Казань
• Количество страниц: 86 с.

СОДЕРЖАНИЕ
Введение

Глава 1. Разложимость 2-в.п. степеней с избеганием

конусов
§1.1. Достаточные условия избегания верхнего конуса Д!]-степени . 17 §1.2. Разложимость и изолированность

Глава 2. п-низкие в.п. и п-низкие 2-в.п. степени

не являются элементарно эквивалентными

Глава 3. Сильная недополняемость в низких в.п. степенях

Литература

Введение
Тыоринговая, или алгоритмическая, сводимость является одной из самых естественных и важных сводимостей, рассматриваемых на классе подмножеств множества натуральных чисел и>. Интуитивно, множество А сводится по Тьюрингу к множеству В, если мы, умея распознавать элементы множества В, можем эффективно распознавать элементы множества А. Хорошо известно, что все тыоринговые степени О образуют верхнюю полурсшетку В(<г,и). Локальная теория вычислимости изучает В(<г О', и) (или Афстепени), т.е. тыоринговые степени расположенные ниже 0', которые также образуют верхнюю полурешетку. Диссертационная работа посвящена изучению структурных свойств верхних полуре-шеток п-вычислимо перечислимых (далее, п-в.п.) тьюринговых степеней (далее, Г-степеней, или степеней) для различных натуральных п > 0. Степень называется п-в.п., если она содержит п-в.п. множество, если она при этом не содержит (п — 1)-в.п. множеств, то она называется собственной п-в.п. степенью.
Изучению верхних полурешеток тыоринговых степеней, состоящих из конечных булевых комбинаций перечислимых множеств, посвящены многие работы. В трудах Арсланова, Доуни, Ейтса, Калимуллина, Купера, Лахлана, Лемппа, Ли, Сакса, Соара, Харрингтона исследуются различные свойства разложимости, изолированности, дополняемости и недопол-няемости для степеней из этих структур.
Степень а называется разложимой в классе степеней С, если существуют степени хо,Х! € С такие, что а < х0 Ыхх и Хо,хг < а. При рассмотрении конечных уровней иерархии Ершова если класс С не упоминается, то

будем считать, что разложение проводится на том же уровне. При изучении свойств разложимости возникают два типа дополнительных вопросов: разложение одних степеней над другими и разложение степеней с избеганием верхних конусов других степеней. Пусть даны степени 0 < Ь < а, и имеется разложение а = х0 и хх. Если Ь < х; (г = 0,1), то говорим, что степень а разложима над степенью Ь: если Ь х; (г = 0,1), то говорим, что а разложима с избеганием верхнего конуса Ь. В обоих случаях представляет интерес хотя бы одно разложение с требуемыми свойствами. Как увидим далее, ни один этих вопросов не является тривиальным. Также будем считать, что разлагаемая степень расположена сверху, если это не указано явно.
Свойства разложимости первым начал изучать Сакс [1|. Теорема Сакса о разложении гласит, что произвольная невычислимая в.п. степень может быть разложена в классе низких в.п. степеней с избеганием верхнего конуса произвольной в.п. степенью. Отметим, что доказательство переносится на случай избегания конуса произвольной А-степени. Позднее, Робинсон
[2] доказал, что произвольную невычислимую в.п. степень можно разложить над произвольной низкой в.п. степенью.
Спустя некоторое время Арсланов, Купер и Ли получили серию результатов о разложимости на более высоких уровнях иерархии Ершова. Купер
[3] доказал, что произвольная невычислимая 2-в.п. степень разлагается в классе 2-в.п. степеней; Купер и Ли [4] доказали, что произвольная 2-в.п. степень разлагается над произвольной в.п. степенью; Арсланов, Купер и Ли [5-6] доказали, что произвольная в.п. степень разлагается в классе 2-в.п. степеней над произвольной низкой 2-в.п. степенью. Вопросы разло-

никают при их использовании. Затем приведем интуитивное описание преодоления этих трудностей и также интуитивно проясним некоторые моменты конструкции. После этого опишем модифицированные модули, с помощью которых приведем формальную конструкцию. В итоге последует раздел с верификацией.
Каждое 75-требование будет строить свои функционалы Г и Д. Также, не ограничивая общности, будем считать, что изе-функции всех рассматриваемых функционалов возрастают по аргументу. Для удобства будем рассматривать переменные х как свидетели требований 5© и возможные элементы множества Е, переменные у — как возможные элементы множества и и переменные г — как как свидетели требований Т-’ф и возможные элементы множества 77. Такая же негласная привязка будет касаться функционалов.
Базовые модули.
V- и 5-требования в отдельности удовлетворяются при помощи стандартной стратегии Фридберга-Мучника. При этом V- и 5-требования будут удовлетворены за конечное число шагов и могут инициализировать все требования с более низким приоритетом. АЛ-требования — это стандартные требования низости, которые удовлетворяются запрещением начальных отрезков множества Е ® Д. Ввиду конечности действий положительных требований стратегии Л/"-требований можно будет определенным образом расположить на дереве стратегий (см. также удовлетворение требований низости в теореме 3.1), поэтому вплоть до конструкции будем описывать конфликты между стратегиями без ЛГ-требований.
Задачей 75требований будет корректное построение функционалов Г