Структурные свойства верхних полурешеток степеней по перечислимости

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

Содержание
Введение
1 Элементарные теории полурешеток ге-в.п. степеней по перечислимости
1.1 Свойства е-идеальных множеств
1.2 Формулировка структурных'теорем для полурешеток п-в.п.
степеней по перечислимости и сравнительный анализ их элементарных теорий
1.3 Доказательство структурных теорем
2 Относительные дополнения в верхней полурешетке Д2-Є-степеней по перечислимости
2.1 Существование неполной -е-степени, не имеющей относительного -дополнения вниз
2.2 Относительные дополнения вниз для низких е-степеней
2.3 Проблема существования дополнений для Д2-е-степеней
Литература

Введение
Одной из важных задач в теории алгоритмов является изучение алгебраических структур, связанных с понятием вычислимо перечислимого множества. Во-первых это связано с тем, что формальное описание вычислимых функций невозможно без рассмотрения частично-вычислимых функций и их областей определения (последние и есть вычислимо перечислимые множества). Во-вторых, многие известные неразрешимые проблемы математики (такие как, например, проблема равенства слов в ассоциативном исчислении, проблема разрешимости исчисления предикатов, 10-я проблема Гильберта и т.д.), формализованные в арифметике, сводятся к проблеме вычислимости того или иного вычислимо перечислимого множества.
Однако, класс вычислимо перечислимых множеств не может, конечно, охватить весь класс множеств натуральных чисел и, следовательно, весь класс неразрешимых проблем. Поэтому зачастую приходится исследовать возможность эффективного перечисления множества А, которое может не быть вычислимо перечислимым, по заданному перечислению другого множества В. Если это так, то мы говорим, что множество А сводится по перечислимости (е-сводится) к множеству В. Формальное определение этого интуитивно заданного понятия, принадлежащее Роджерсу и Фридбергу [19], будет приведено в пункте 2. Оно будет полностью соответствовать его интуитивному пониманию (см. [33] § 9.7).
В данной работе мы исследуем структуру степеней, называемых степенями по перечислимости или е-степенями, образованную сводимостью по перечислимости, т.е. структуру классов множеств, эквивалентных в том смысле, что их ’’сложности перечисления” одинаковы. Как и почти любая алгоритмически заданная степенная структура на множестве натуральных чисел, класс

степеней по перечислимости является верхней полурешеткой, относительно частичного порядка, индуцированного сводимостью.
Исследования в этой области были начаты Медведевым в 1950-х годах и продолжены в работах Гаттериджа, Розинаса и других. В частности, было показано, что не существует минимальных е-степеней (см. [20]); доказано существование квазиминимальных е-степеней (см. [30]); установлено, что тотальные е-степени порождают относительно операции взятия наибольшей нижней грани все е-степени (см. [34]).
В последние два десятилетия с развитием приоритетных методов особое внимание стало уделяться изучению структуры е-степеней Е° -множеств — аналогу структуры тьюринговых степеней ниже 0' в структуре всех тью-ринговых степеней.
Купером была установлена плотность Е-е-степеней (см. [9]). В работах (см. [8] и [10]) опровергается плотность верхней полурешетки всех е-степеней. Купер [9] также определил оператор скачка в е-степенях, обобщающий понятие скачка в тьюринговых степенях. Мак-Эвоем [29] (см. также [36]) была введена иерархия, согласованная с оператором скачка, которая подобно арифметической иерархии для тьюринговой сводимости, классифицирует сложность множеств относительно сводимости по перечислимости.
Кроме того, исследовались вопросы, касающиеся наиболее важного класса Е-е-степеней — класса е-степеней А-множеств (Д[]-е-степеней). Например, Арсланов, Калимуллин и Сорби [6] доказали теорему о плотности Дз-е-степеней, дополняющую теорему Купера [9] о плотности Е°-е-степеней. Ии, Купер и Сорби (см. [12], [13] и [14]) исследовали вопросы о дополняемости и относительной дополняемости Ез-е-степеней. Они показали, что все нетривиальные Д!] -е-степени (в отличие от всех Ез-е-степеней) обладают относительными дополнениями ВНИЗ И наверх в структуре Ез-е-степеней. Эти результаты естественным образом приводят к вопросу о существования дополнения В структуре Дз-е-степеней (или хотя бы в структуре Е°-е-степеней) для произвольной Дз-е-степени. Например, согласно результату Познера [32] ответ положителен для тьюринговых степеней.
В главе 2 исследуется именно этот вопрос и доказывается, что ответ на него отрицателен. Более того, существует неполная П°-е-степень, не имею-

Шаг 2. (Удовлетворение требований Р*,) Для каждого к < я определяем значение ’’функции длины”:
1{к,з) = шах{ж <я:(Уу< х){Г3(А3; у) = ЦГеу!1{у)]},
где к = 2е + г, г < 2. Находим наименьшее к0 = 2е0 + *о < я такое, что 1(ко,$) > тах{/(ко, () : I < я}, и полагаем Г;0>3+1 = Гго,3+1 и {({у, к0), {у}) : (у, ко) < «} и Г1,—го,«+1 = Г1—*0,*+х (если такого к,0 нет, то определяем Г+1 = Г,,а, г < 2).
Описание построения завершено. Полагаем Г* = изГ»,3 для каждого г <

Установим теперь, что Г0(А) и Г! (А) — искомые множества.
Лемма 1. Г0(А) и Гг(А) являются 3-в.д. множествами, причем Г0(А) и ГI(А) е-идеальны.
Доказательство. Нетрудно заметить, что для всех у, к, Р и г <
«у,&),Р)€Г):=Р = 0УР = {у}.
Следовательно, для каждого г < 2 имеем Г,(А) = Нт3 Г8(А3) и
|{й : Г*,ДА3;х) Г,-+1(А»+1;ж)}| <
для любого ж € о;. Значит, Г0(А) и ГА) — 3-в,п. множества.
Покажем, что требование N выполнено. Заметим, что по определению Г; для любых х, в, ? / | л 1 < 2, удовлетворяющих условию (ж, У) £ Г]3, справедливо х £ иееи< 2е+ я
Пусть б = (ГДА») — Г5+1(А+1)) П ф 0 при некоторых значениях х,я,к £ со и i < 2. Тогда, б С 2е+г [з и, следовательно, к = 2е -- г для некоторого е. Фиксируем наименьшее ко = 2ео + го < к такое, что (Г;о,ДА3)-Г;0,ДА 3+1))П<Д°1 Ф 0. По построению имеем [йС Г_ <.,»+1(0) С Гх_зд 3+1(Х) для любого множества X. Поэтому, г = г0 (иначе было бы С С Г,+1(А,+1)), откуда я С Гх-+ДО) С Гх_ДА).
По теореме 1.1.12 множества Г0(А) и ГДА) е-идеальны