Минимальные покрытия тьюринговых степеней

• Автор: Ишмухаметов, Шамиль Талгатович
• Шифр специальности: 01.01.06
• Научная степень: Докторская
• Год защиты: 2003
• Место защиты: Ульяновск
• Количество страниц: 178 с.

СОДЕРЖАНИЕ

Введение

Глава 1. Методы построения минимальных степеней

§1. Основные стратегии метода

§2. Дополнения рекурсивно перечислимых степеней в нижних конусах

§3. Дополнения произвольных степеней в нижних конусах

§4. Дополнения в конусах, ограниченных низкими степенями

§5. Эффективные минимальные покрытия рекурсивно-перечислимых степеней

Глава 2. Строгие минимальные покрытия и проблема Спектора

§1. Строгие минимальные покрытия а-р.п. степеней

§2. Степени, не имеющих строгих минимальных покрытий
§3. Слабо рекурсивные степени и проблема Спектора
§4. Слабые минимальные покрытия и построение изолированной степени
• Глава 3. Начальные сегменты степеней. Метод вложения
§1. Вложение 3-элементой решетки и ромба
§2. Методы представления конечных решеток
§3.Специальные виды решеток
§4. Вложение конечных решеток
§5. Вложение счетных порядков в тьюринговые степени
Глава 4. Относительная перечислимость тьюринговых степеней
§1. Открытые степени
§2. Относительная перечислимость тьюринговых степеней
§3. Разложение р.п.степеией над заданной степенью
§4. Построение высокой изолированной степени
^ §5.0 дистрибутивности верхних полурешеток степеней ниже 0'.
ЛИТЕРАТУРА
Введение
Введение

Изучение структуры тьюринговых степеней является одной из наиболее значительных задач теории вычислимости. С самого начала зарождения этой теории, т.е. с начала 50-х годов, большое число ученых обращается к изучению структурного строения полурешетки тьюринговых степеней (или степеней неразрешимости), получая новые и новые результаты. Ряд проблем, поставленных еще в середине 50-х годов относительно распределения минимальных степеней и их покрытий, был решен сравнительно недавно, а некоторые вопросы не получили ответа и поныне. Одной из наиболее известных таких проблем, поставленной в 1956 году К.Спекто-ром, является проблема описания класса степеней, обладающих строгими минимальными покрытиями. Напомним, что степень а называется строгим минимальным покрытием (с.м.п.) для меньшей степени Ь, если для любой степени с из с<а следует, что с<Ь. Другой важной нерешенной проблемой является проблема Ейтса (C.E.М.Yates [1970]) о существовании с.м.п. у произвольной минимальной степени. Решение этих проблем позволило бы сделать существенный скачок в решении задачи описания начальных сегментов степеней неразрешимости.
Одной из важных предпосылок для дальнейшего продвижения в этой области является разработка автором диссертации нового метода построения минимальных степеней, который позволил соединить ряд методов, разработанных для изучения начальных сегментов степеней, с различными модификациями метода приоритета, включая метод приоритета с бесконечными нарушениями (т.е. методы уровня О" и 0"' по классификации P.Coapa (R.Soare [1986]). Напомним кратко историю вопроса.
Первая конструкция минимальной степени принадлежит К.Спектору (C.Spector [1956]). Шенфильд (Shoenfield [1966]) ввел понятие деревьев, которое оказалось чрезвычайно полезным для формулировок и доказательств результатов о минимальных степенях и покрытиях и способствовало упрощению доказательства Спектора.
Определение. (Шенфильд [1966]). Деревом называется функция Т из множества 2<ш (т.е. из множества конечных последовательностей из 0 и 1, называемых строками) в множество 2<ш такая, что:
1. Т(ст) 4 Лг С а —> Т(т) 4 определено Л Т(т) С Т(а).
2. Если одно значение из пары Т(а * 0), Т(а * 1) определено, то определено и другое,и они несравнимы (будем использовать запись Т(а *
Введение

0)|Т(<7*1)).
Дерево Т называется полным, если функция Т определена на любой строке т.
Строка принадлежит по определению дереву Т, если либо сама строка т, либо ее некоторое расширение принадлежит области значений функции Т. Множество А лежит на дереве Т, если каждый начальный сегмент характеристической функции А лежит на Т.
Переведенное на язык деревьев, доказательство Спектора основывается на двух нижесформулированных леммах, итерационное применение которых позволяет легко получить минимальную степень (полное доказательство можно найти в книге М.М. Арсланова [1986], стр.142, или учебнике П.Одифредди [1989]).
Лемма 1. Если Т-полное рекурсивное дерево и е-произволыюе число, то существует полное рекурсивное поддерево Q дерева Г, такое что для любой бесконечное ветви А, расположенной на Q, А ф фе.
Лемма 2. Пусть Т-полное дерево, и е-произвольное число. Существует такое полное поддерево Q дерева Т, что для любого А, расположенного на Q, ф^-всюду определенная функция —> ^-либо рекурсивна, либо А <т ф£-
Анализ доказательства Спектора показывает, что требуемые в леммах поддеревья Q могут быть найдены с помощью оракула 0", поэтому и построенная им минимальная степень находится ниже О". Существенным признаком этой конструкции является то, что применение оракула 0" является необходимым.
Дж.Сакс (J.Sacks [1961]), используя частичные деревья, сумел устранить использование оракула 0" и доказал существование минимальной степени ниже 0'. Этот метод получил название метода е-штатов. Однако метод Сакса использовал оракул О' и не позволял ответить на ряд естественно возникающих вопросов. Одним из таких вопросов был вопрос о том, какие степени принадлежат замыканию множества минимальных степеней ниже О' относительно операции взятия верхней грани, и в частности, является ли степень 0' супремумом двух минимальных степеней. Другим является вопрос, под какими степенями существуют минимальные степени. В частности, есть ли минимальные степени под каждой нерекурсивной рекурсивно-перечислимой (р.п.) степенью?
Для решения этих проблем Ейтсом (Yates [1970] и Купером (S.В.Cooper
Дополнения р.п. степеней в нижних конусах.

предположения об исходах позитивных условий, предшествующих ей, совпадают с текущими.
Проверим, найдется ли Р-корректная на шаге в 4-1 строка /3 такая, что (п+1) ф С (п + 1)][я] совпадает с п(з) (значение этого параметра определено выше, перед инструкциями этого шага), и £^(п(в)) Д Эти условия означают, что для процедуры (п(в)) стратегии /3 выполняются условия шага 5 основного модуля, и сейчас надо изменить М. Если такие /3 найдется, то выполним следующие инструкции:
1. Выбираем строку /3 наибольшего приоритета с этим свойством. Пусть (т°,т^) текущий свидетель процедуры (п(з)) этой строки.
2. Изменим значения М(у), у < |т®|, определяя их равными тДу).
3. Инициализируем все 7 Э /3*(п(в)) и 7 >1 /3*{п(в)). Переопределим значения параметра г(7) равным в для всех инициализированных 7.
Этим завершаются инструкции шага .? + 1.
Верификация.
Определим истинный путь £ как самую левую бесконечную ветвь дерена исходов Т, посещаемую бесконечно много раз в течение конструкции
Лемма об исходах. Каждое условие Лг,, и Ре для е£ы удовлетворяется стратегиями а и /3 длины 2е и 2е+1 соответственно, расположенными на {.
Доказательство. Пусть а с£имеет четную длину 2е. Сделаем индукционные предположения о том, что
1. Существует бесконечное число а-шагов, являющихся одновременно Л-минимальными,
2. Найдется шаг §0 такой, что после этого шага никакая строка 7 С а не может инициализировать а.
Обозначим через эа > наименьший шаг, после которого строки 7 <1 а не посещаются и не действуют по инструкциям второй части шага конструкции, изменяя М. Такой шаг действительно найдется, т.к. после того, как каждая строка 7