Q-степени рекурсивно перечисляемых множеств тема автореферата и диссертации по математике, 01.01.06 ВАК РФ
|
Оманадзе, Роланд Шатрович
АВТОР
|
||||
|
доктора физико-математических наук
УЧЕНАЯ СТЕПЕНЬ
|
||||
|
Новосибирск
МЕСТО ЗАЩИТЫ
|
||||
|
1993
ГОД ЗАЩИТЫ
|
|
01.01.06
КОД ВАК РФ
|
||
|
|
||||
РТ6
од
РОССИЙСКАЯ АКАДЕМИЯ НАУК СИБИРСКОЕ ОТДЕЛЕНИЕ ИНСТИТУТ М Л ТЕМАТИКИ ' Специалиэироваяный Совет Д 002.23,01
На правах рукописи
ОМАНАДЗЕ Ролаяд Шкикэт?
УДК 510.5
<3-СТЕПЕНИ РЕКУРСИВНО МНОЖЕСТВ
01.01.05 - катекатггчоская догака, алгоора я -оорг.я чисел
Автор« Ф а р т
диссертации на соискаппо ученоЛ <ст,сс;г;к доктора Фпзнко-математпчоскнх нал:
Новссибирак 1393
Работа шпслнокэ в Института •,.т:.,х,д.'Ои здтоздтпки :::.*.она П.Н.Векуа Тбилисского гос7ДО]хг-гьс1;::ого унлшзрситота «гло.,.: И.А.Джавазсипшли
Научний консультант - акадшаж РАН, доктор физшсо-:,!ато:.и1т::-чссхпх паук, профессор ЕРШОЗ &.Л.
Официальные оппононти - доктор фпзш'.о-г.атш.атичоских наук, профессор С.С.ГОНЧАРОВ,
доктор физико-математических наук, профессор М.М.АРСЛАНОи,
доктор фкзико-матоцзткчосклх наук, профессор В.11.Д0БРИЦА.
Вэдущая организация - Уральский государственный университет. Автореферат разослан "
ШС>Л<К 1993 г. Защита состоится " ЪО " гг. в (Ц часов на заседании Специализированного совета Д 002.23.01 при Циститу Т5 математики Сибирского отделения РАН по адресу: СЗСОСО, г.Новосибирск, 90, Университетский проспект, 4.
С диссертацией иошо ознакомиться в библиотеке ¡¡лститу:^ математики С' РАН.
Учшшй секретарь
слбщ;злазирокзк;;ого соеотз Д ccz.23.cl '
клд. ¿.кз.-глт.наук С.ТЛодорясш .
ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ
Актуальность тони: Теория алгоритмов (рокурсивннхфункций) является одним из современных и бурно развивающихся разделов математической логики. В блестяаях работах 30-х годов Черча,, Клини. Тьюринга и Геделя были получены основополагающие Факты о природе алгоритмов; доказана эквивалентность различных уточнений понятия вычислимой функции, сформулирован и обоснован тезис Черча. доказаны теоремы об универсальной Функции, теорема ' и теорема о рекурсии. На этой основе удалось доказать нераэре-решимость многих важнейших алгоритмических проблем математики. Все это правело к бурному развитию теория алгоритмов, которое продолжается и сейчас. Начало развития важнейших его разделов -теории рекурсивно перечислимых (р. п.) множеств .и степеней неразрешимости - относится к оце более позднему времени - середине -10-ых - началу 50-ых годов. Именно в эти годы были опубликованы Фундаментальные работы Е.Поста с32, 333, С.К.КяякииБ.По-ста с253, содержащие не только первоначальные методы а результаты теории, но и определившие пути ее развития.
Для каждого множества А, ла>=^о. 1,2____К кс:хяо сперму-
лрег-ать следующую проблему: существует ли алгоритм, позволявши?. для любого х«" ответить на вопрос о принадлежности * к л. Множества. для которых данная проблема разрешима, были названы рекурсивными. Однако, скоро выяснилось, что существуют различило по сбор!! "сложности" р.п. множества, не являющиеся рекурсивными. которое стали особым объектом изучения. Инструментом для кла.х'-ч'.пкацЕ!! подмножеств « по их "слоашостя" служит понятие
сводимости» являющееся одним из Фундаментальных в теории алг ритмов. На интуитивном уровне множество а сводимо к множеству в. если существует алгоритм, который решал Оы проблему вхожде ння элементов для А при условии, что есть возможность пользоваться информацией о принадлежности тех или ины1 элементов множеству в. Такая сводимость в саном общем виде называется тьюрин-говоя ст-> сводимостью.
■ Результаты и методы теории алгоритмов быстро нашли свое применение в различных областях математики. Выяснилось, что многио из известных проблем являются неразрешимыми. Такими будут, например, проблема распознавания тождественной истинности формул исчисления предикатов, проблема тождества слов конечно определенных групп и полугрупп, 10-эя проблема Гильберта и другие. Часто неразрешимость одной проблемы доказывается посредством сведения к ней другой, о которой заранее известно, что она неразрешима. Эта последняя проблема в боль-• иннстве случаев является проблемой разрешимости подходящего р. п. множества.
Наряду с г-сводимостью в 1944 .году Э.Пост С323 ввел некоторые специальные виды сводимостей. такие, как "-сводимость табличная сгг-э и ограниченная табличная сьи-з сводимость.
Крупный вклад в изучение этих сводимостей внесли С.Клип и Э.Пост, Ю.Л.Ершов, А.Лахлан, Г.Сакс. К.Ейтс, Р.Фридберг, К.Джокуш, А.А.Мучник, А.Н.Дегтев, М.М.Арсланов, С.С.Марчонкс "С.Д.Денисов. Г.Н.Кобзев и другие. Приведем несколько результатов, полученных в этом направлении. Ю.Л.Ершов показал, что ворхняя полурешетка р.п. "-степеней, не является решеткой и
- ь -
построил пример р.п. "-степени. под которой нет.минимальной ^-степени с93. Он же дал полное описание полурешетки "-степеней fio3. А.Лахлан описал начальные сегменты р.п. "-степеней, а также доказал, что каждая р.п. нерекурсивная Т-степень содержит минимальную m-степень t2f>-. Г.Сакс £34^ показал, что р. п. т-степени упорядочены плотно относительно '-сводимости. Изучая верхнюю полурешетку р.п. "-степеней, А.Н.Дегтвв показал. что ока не является решеткой, имеет минимальные элементы, а такие такие элементы, под которыми нет минимальных Он «а доказал, что каждая р.п. нерекурсивная т-степень содержит учетное число попарно несравнимых р.п. "-степеней C7J. ".Д.Денисов охарактеризовал верхние полурекетку р.п. "-степени с 53.
Кроме этих видов сводимостей некоторыми авторами были оп--яделены другие виды сводимости. В частности. С.Таняепбаум дал определение О-сеодимостя следующим образом:
Множество А 0-сводится к множеству о, если
(зг о. р. ф. ) с* ) (x£a«->vf ( х) 33 ). <• )
Понятие Q-сзодимости является весьма остествепним и вазк-п;м для т'юряи алгоритмов. С помоаыо этого ^снятия был нолу-¡.-•е ряд интересных результатов. Этому понятию принадлежит •данная роль в решении С. С. Марченковым ЧЗ^известлоЯ проблемы Lc-cra методами самого Поста. Q-сводимость используется в ис-довйниях некоторых других областей теории алгоритмов, на-TiíMep. v исследованиях по проблеме тождества слов и по слож-■:с-тп гычислен."*?. . о-сг-сдямость по сравнению с другими видами сводимостей •
оказалась наименее изученной. Это, по-видимому, объясняется тек, что приятие Q-сводимости не отличается такой простотой, как "-сводимость; в ее определении участвует р.п. множество "»<*> • которое может быть и бесконечным. И еще. из 0-сводимос-ти в обцем случае не следует даже т-сводимость.
Если от множества vf(K', , из определения <?-сводимости. потребуем удовлетворение некоторым естественным условиям, то получим понятия, более сильные чем Q-сводимосгь. Именно, скажем. что множество * eQ-сводится (или сильно Q-сводится) к множеству в, если выполняется (*) и дополнительно,
(Зе о.р.ф. )CVx)(Vy)'<yeVf(Ki чу<есх>).
Если, кроме того, существует число такое, что
то скажем, что множество а ьз<?-сводится (или ограниченно s<?-сводится) к множеству в.
В изучении различных сводикостей явно выделились три направления. Одно из них заключается в том, чтобы охарактеризовать г-полны о множества и выяснить соотношения, например, по включению, между классами г-полных множеств для тезе или инь сводимостея г-. Другое связано с вопросами строения полурешеток г-степеней, в особенности р.п.' г-степеней. Третье - с вопросами, сколько г-степеней имеется и как они расположены в степенях относительно более слабой сводимости.
В работе.C8i А.Н.Дегтевым дано окончательное решение трех проблем; для класса сводимостоз табличного типа, относящихся к указанным выше трем направлениям.
Замечательные результаты по рдараЗодко .общи методов, позволяющих описать полные в соответствующем уровне -арифметической иерархии классы ари^моттчоских множеств и яолутать тпа основе этих методов конкретпие критерии полноты для г£-, мноместв Сп-Р, принадлежа? М.И.Арслакозу
Ряд результатов относительно указанных видов сводимостей приведен в книгах X. Роджерса р.соара П.Одифродда
С31Л Н.М. Арсланова ^2,3^, Лж.Шенфилда ^153. Интересные критерии 0-полноты р.п. множеств получены в работе В.К.Булитко с53.
Весьма интересные связи р.п. -О-иолля:-^ множеств со сложностью вычисления были напдены з работах Блзома и Маркуса С19Э и Гнлла и Морриса с213. Блюм и Маркус с 193 отмечают, что важной целью теории сложности вычисления рекурсивных функций является характеристика рекурсивных функций и р.п. множеств, имеющих некоторые данные сложнортныв свойства, в терминах, не содержащих в себе сложностных понятия.
Со времени публикации в 19СТ г. двух статей И.Блюма 47, 183, в исследованиях сложности вычислений рекурсивных функций возрастающую роль лачгнают .играть методы и результаты "чистой" теории рекурсивных функция, особенно теорема о рекурсии и методы приоритета.
И';.ЧЫ)_Г'аС21Н является рэпеняе дребяг.м. для г-5{<5.=0,Ь5<з свсдякостеЕ, относящихся к следующим направлениям-' 1. Исследование есяямных связей между слояностными свойствами р.п. множеств и Г-СВОДПМОС79Й. 11. Изучение строения долурешеток р. п. г-отопеней. ш. Выяснение сколько г -степеней имеется и как они росполокены в степенях относительно более слабой сво-
- Й -
днмости. IV. Характэризация г-полных множеств н выяснение соотношений .между классами г-полных множеств, где гс-{т,<},У,з(з,ьу,ЬБд
Основные метолы. Для доказательства основных результатов используются различные приоритетные конструкции, теорема о рекурсии, методы метрической теории алгоритмов, свойства неуско-ряемых и нигде не простых множеств.
Научная новизна. Все существенные результаты работы являются новыми. Они значительно обогащают и дополняют то небольшое число известных фактов о <5-степенях и сложностных свойствах р.п. множеств, которые были установлены ранее другими авторами.
представляют теоретический интерес. Онй могут быть использованы в дальнейиих исследованиях в теории алгоритмов. Основными результатами являются: установление эквивалентности понятия . а9-полного р. п. множества, эффективно субкреативного множества, сильно еФФективно ускоряемого множества; доказательство ряда структурных свойств полурешеток р.п. г-степеней г«{о,н<},ьо<)}. Полное решение проблемы о соотношениях между классами г-поЛНЫХ р.П. множеств. r■e■{T,Q,V,зQ,ЪV,ЬsQ}.
Апробация работы и публикации. Результаты работы докладывались на семинарах "Теория нумерации", "Конструктивные моде-Хи'.Е "Алгебра и логика" в Новосибирском государственном унй- • в&рсптоте. на семинарах отдела дискретной математики Института
- а -
прикладной математики им. И.Н.Векуа ТГУ, на общепнститутском семинаре ИПМ им. И.Н.Векуа ТГУ. на семинаре по математической логике и теории алгоритмов в Московском государственном университете, излагались на VIII Международном конгрессе по логике, методологии и Философии науки (Москва, 1987), на пленарном докладе Межреспубликанской конференции по .математической логике (Казань, 1992).'Все основные результаты опубликованы в работах с 39-55-з.
Объем и структура работы. Диссертационная работа состоит из введения, четырех глав,_ объединяющих 15 параграфов, и спи--ска литературы, насчитывающего 112 наименований. Общий объем работы 195 страниц.
СОДЕРЖАНИЕ-РАБОТЫ
Глава 1 посвящена изучению сложностных свойств р. п. множеств и классификации класса простых множеств. Одним.из наиболее интересных и важных аспектов теории сложности вычисления рекурсивных функций является Феномен' ускоряемости. содержащийся в известной теореме М.Блюма 3 работе 49^ М.Елим и И.Маркус распространяют понятие ускоряемости из о.р.Ф. на ч.р.ф." или эквивалентно, на р.п. множества и вводят понятия неусхоряекого, эффективно ускоряемого и субкреативного множеств и доказывают эквивалентность понятий субкреативного л элективно ускоряемого множеств. Гилл и Моррис дали интересную характеристику эффективно ускоряемых множеств в терминах °-полиых множеств. Они доказали, что р. п. множество •является с>ф*ективно ускоряемым тогда и только тогда, когда с но о-полно. Р.Соар £363 нашел'очень" интересную характерно-
тику неускоряемых множеств Ф 'У&рмиьах индексных множеств.
В Я естественным гдай^ йзодятся понятие ¡^-сводимости и понятия эффективно субкреа^Вййого и сильно эффективно ускоряемого множеств и доказав один из основных результатов этой главы.
Определение £19}. Р.п. множество А называется суокроатив-ным. если существует о.р.ф. г, такая, что для каждого номера 1 существует натуральное число \, такое, что
1. ^(<>-А и
2 а еСУ п АЗ II и А.
^ ' ». 4. 1 ' I
Если дополнительно существуем Р.-Р.ф. е. такая, что
з. а. еСУ. и А ■* а. <бСП,
¿о назовем множество а эффективно субкреативным.
Пусть последовательность ч.р.Ф. -удовлетворяет
аксиомам М.'Блюма 47^.
Определение с 191. Р.п. множество а,называется эффективно ускоряемым, если существует о.р.ф. т; такая, что для всох натуральных чисел 1 и 1, если есть частично характеристическая Функция а (эквивалентно V. =а> и - о.р.ф., то
IV , -А (т е *> , =с )
Ttl.ll Т< I . I )
2. (ВхХхсА » Сх,^т< ^ ^СхЭЭЗ.
Если дополнительно существует о.р.ф. е, такая, что
3. СУ13СУ15СУу2СуеУт1 . \А * у <есС1, ПЭ ,
где с - нумерационная функция, то р.п. множество а назовем сильно сдффективно ускоряемым. Здесь символом а™ обозначается выражение "существует бесконечно мно-
- ТТ -
го *".
Определение» £191. Р.п. множество а называется неускоряе-мым, если существует число 1 и о.р.Ф. такие, что и
СУРСУ^-Л -> <У>?>Сх«Л ф^ СхЭЭЗЗ,
где символом обозначается выражение "для почти всох *". Имоот место следующее утверждение.
Теорема 1. Пусть а _ р.п. множество. Тогда следующие утверждения эквивалентны:
I. л есть ^о-полное множество:
и. А ость'эффективно'субкреативное множество;
iii. сзс о.р.ф.эсзе о.р.ф.хуххуухсу ^л-о + аз
Г < к > к Г1 <1 ' а '
IV. а есть сильно эффективно ускоряемое множество.
Из этой теоремы вытекает, что существует эффективно ускоряемое. но не сильно эффективно ускоряемое множество.
Маасе ^273 показал, что если а,в являются точно простыня иеускоряемыми множествами, то существует автоморфизм ® решет-' ки п всех р.п. множеств, такой, что .¿саэ-в. соар СЗС1 дока- . элл, что если А ноускоряемое множество, то решетка У-р.п. »М'ОктиЕчю изоморфна решетке е. в 52 мы продолжаем нсследова-шю сложностных свойств р. п. множеств. Показано, что если -0-стопонь содержит неускоряемые множества, то все р.п. множества из этоа О-степени будут неускоряемымиг поэтому 0-сте-певь н«ускоряемого множества будем называть неускоряемой с-степенью. Маркус С2£Р показал, что в каждоП р.п. т-степени сод^р.читсл н^усыоряэмсе множество. Из выпгепрлводешшх рсзуль-
татов следует, что этот результат Маркуса не имеет места для р. п. О-степеней. Однако замечено, что неускорявмые О-степанн образуют идеал в верхней полурешетке всех р.п. Q-степенеИ и этот идеал не имеет наибольшего элемента. Основным результатом этого параграфа является теорема 2, утверждающая, что указанный идеал неускоряемых Q-степеней упорядочен плотно. Именно, доказано следующее утверждение: пусть ь-неускоряемие 0-степени и а<ь. Тогда существует бесконечное число попарно Q-нес-равнимих пеускоряемьи О-степенеВ ^ ^^ таких, что
CVi5Ca< с < Ъ). а ь а
Результаты этого параграфа используются в дальнейших исследованиях.
Для каждого обозначим через LCA:> множество всех p.a. надмножеств множества А. Класс л подмножеств множества <- называется кофинальным если для каждого р. п. множества А с бесконечным дополнением существует множество такое, что fss. P.a. множество А с бесконечным дополнением имеет кофинальные гипергиперпростые надмножества 12V. осли класс нн • гипергнперпростых множеств является кофинальным в lca>. обозначим через 'И - класс всех р.п. множеств с кофинальными ги-пергиперпростыми надмножествами.
В работе с36^ Р.Соаром указаны интересные свойства простых неускоряемых множеств. В частности, показано, что если множество принадлежит классу fsHS _ конечно строго гиперпростых множеств, то оно является ускоряемым.
В работе Е.Херрманном исследованы точные взаимные.расположения классов простых множеств и доказана соот&етствуюаая
с
классификационная теорема. При этом оставлена открытой следующая проблема: имеет ли местогиегвнз--' Другими словами, если АЛГвНЗ, то МОЖНО ЛИ построить множество Уе^СА), такое, что 17!=а>
И 1-С?;> П НН-О ?
В }3 обнаружена неожиданная связь между классами р.п. 9-полных множеств и множеств, не принадлежащих классу »"еНЗ, Именно, доказана теорема 3, из которой вытекает положительный ответ на вопрос Е.Херрманна.
Теорема 3. Пусть р.п. множество л с бесконечным дополнением не принадлежит классугонз тогда существует р. п. множество с. Л5С. такое, - что всякое надмножество множества с с бесконечным дополнением является 0-полным.
Следствие, гнсгвнз.
Таким образом, классификационная теорема Херрманна я теорема 3 дают окончательную картину точных взаимных расположения классов простых множеств.
Глава и посвящена исследованию структурных свойств верхних иолурешеток р.п. «■-степеней, где гв^.од.ьзд^
Шор с35; ввел восьма полезное и интересное понятие нигде не простых множеотв. Он показал, что нигде не простые множества содержатся в каждой р.п. т-степени и нигде не простые мпо-жеютва можно успешно использовать при изучении автоморфизма рмшткя. е" - Фактор-роиетки решетки всех р.п. множеств е по модуле конечных множестЬ. Миллер и Реммэл С293 показали, что свойство нигде не простоты является элементарно тооретнко-ре-иеточным в Е и е".
- 14 -
В 54 исследуются некоторые свойства нигде не простых множеств и показано, что как и в случае неускоряемых множеств, если Р-степень содержит нигде не простое множество, то все р.п. множества этой • О-степени являются нигде не простыми. <)-степонн нигде не простых множеств образуют идеал в полуре-шеткв всех р.п. О-степеней. .Естественно возникает вопрос-верно ли, что в каждой нерекурсивной р.п. 9-степени содержится простое или нигде не простое множество? Отрицательный ответ на этот вопрос дает следующая теорема, которая является основным результатом этого параграфа.
Теорема 4. В каждой р.п. нерекурсивной т-гстепени содер-, ентоп р.п. множество а такое, что в Р-степени множества а отсутствуют простые и нигде не простые множества.
В заключение этого параграфа рассматривается фактор-полурешетка полурепетки всех р. п. О-степеней по.модулю идеала <?-степеней нигде не простых множеств 'и показано, что в этой Фактор-полурешетке имеются несравнимые элементы.
Интерес к изучению свойств »<}- сьв<з~э сводимости возника-. ет из следующих соображений: С1) ер- сьа(}-> сводимость получается с естественным ограничением из 0- св<з-э сводимости, и <П)г!}- сьаО-> сводимость является самой общей сводимостью, из которой на классе р. п. множеств вытекают одновременно сьу-з сводимость и 0- <«"3-3 сводимость.
ИСХОДЯ ИЗ специфики <Ьв<5-Э сводимости удалось получать ряд важных результатов, относящихся к полуреиетке р'.а. сф- сье(?-5 степеней.
Пусть ге^М}, Ьг<5}-. в $5 исследуется вопрос о плотпостп
- 1Ь -
верхней полурешотки р.п. г-степенй и доказана интересная
Тоорема 5. Пусть * и ь - р.п. г-стопонн и "<ГЬ. Тогда существует бесконечное число попарно г-несравнимых- Р. п. г-стопа-Н0Я ^ео таких, что •
(У1 )(«< с < Ь)
' Г I г ' ■
С.С. Марчонков <12^ показал, что для сводниоствй табличного типа и для 7-сподимости имеет мосто следующий результат: какова бы пи была р.п. нерекурсивная неполная степонь. существует но сравпнмая с неп степень, содержащая наксималь-ноо множество. Известно с 105', что максимальное множество является ускоряемым. Поэтому, анализируя доказательство вышеуказанного результата Марченкова, получаем, что для кавдо? норекурсивной р.п. по г-полной. гв{яО, ьво}-, степени существует несравнимая с ней ускоряемая г-степень.
Основным результатом }6 является'следующая
Теорема 6. Для всякой р.п. нерекурсивноп не полной г-сте-пени, г«=<в<5( ьжз^ существует несравнимая с ней неускоряемая' г-степень.
Пусть г - некоторая сводимость. Обозначим через ьг верхнюю полурешетку р.п. г-степеней. а через тпсьгэ - элементар- . ную теорию 1-г.
Одной из главных задач в изучении степеней неразрешимости является проблема соотношений меад/ элементарными теориями. Решению этой проблемы для ' различных сводпмостей <зыл посвящен ряд работ разных авторов. В работе. А.Н.Дегтева дано полное резейио этой проблемы для сводимбсгеп табличного
типа.
Хорошо ИЭВеСТНп. ЧТО tH'JIH 1 - ЯКИмнТОЯ ('ЬчЛИМчОТЬЮ таблич-чн<чч> тнпч. t«.i н 'сущи-тьуют минимальны« элементы. Из пред-лояония 3 параграфа 2 вытекает. что в , r«--¡Q. -У, ьор(_ минимальны! элементов по существует. Поэтому Th<L( ^TtuL^ > для
i
r«{Q, «о, boQ} и дЛ)1 сьоднмостей табличного типа
В 1Г?79 1\>ду А.Н.Догтев поставил автору следующий естественны В вопрос: имеет ли место ThCLa'-Т|''а1С другой стоянки Р.Одкфроддн сОО] отмечает, что не и-лч-етно. совпадают лиТГ1С1-а:> в ThCLr3 для ro^V.Tp
Центральным результатом 57 является теорема 7. с помощью которое получается ответ на вывепоетаменныя вопрос.'Эти творена 7 ннторесна еще тем, что из нее получается, что классическая теорема Сакса о расщеплении неимьот моста для р. п. 9-степеней.
Теорема 7 (о перасциалсшии). О-отопчнь максимального мно-
*
«еотва не'является точной верхпоя.rptüui ни для клких ы-срав-ш1) шх. <?-с70п 0202.
Следствие. Пусть г«{9. oq, ьь-Qh а г^^т, и. ь«}. Тогда >^Thar
В заключительном 58 этой главы рассмотрены «"-отделимые р. П. шоаеетш. Этот класс множеств оказываете/, очень важным ихиооок для творцы р.п. Kiioay-'JTn. Чтобы убедиться п этом, до-сгаточпо эдмотить. что подавно Б.Херрманн <233. используя ГЦ-Вйзлоту индексного мноисюты у„-^-отдслимо>. доказал по-
разрешимость элементарно;! теории решетки р п. множеств, реанв тем самым известную проблчму В этом параграф» доказывается, что если а. п - р.и • множк:тм. а - г-отдолииое мношкшю, то
в .» сзс нирокуроивноозс"„л * С5„ю .Эта теорема используется для доказательства следующего предлокиния. которое явля-отся усилением одной теоремы из ЧП Пусть А и п ~ р п. множества, л обладает минимальной т-стопоиы) и в*, А. Тогда
I
сусхс-р.п в в с" - совершенные множествам
В главе П1 изучаются соотношения между р. п. т- и О-сте-понями. р п. V- и зО-степенями, р.п. ьv- и ьи<?-степенями, а также другие вопросы.
Особенность О-сводимости состоит в том. что сша не являет-" ся частным случаем т-сводимости. Это обстоятельство дало возможность Л.Хея 1223 доказать, что никакая нерекурсивная р.п. неполная т-стопень но может содержать целиком никакой <?-степе-ни. Вместе с том в 59 показано, что в р.п. полной т-степ&на содержится бесконечное число попарно о-песравннмых р.п. Ч-стопо-ней. '
Центральным результатом этой главы является '
Теорема 10. 1) В каждой нерекурсивной р.п. Т-степени содержится бесконечное число попарно О-несравннмых ноускоряеиых множеств.
2) В р.п. полной т-степени содернптся бесконечное чясяо попарно 0-несравнимых р.п. 9-степепеЯ.
3) Среди всех р.п. <?-степенея, содерзацихся в р.п. полной т-степени, нет максимальной р.п. З-степенн.
- 1В -
Для доказательства этой теоремы показано, что для всякой ноускоряемой 0-стопони существует несравнимая с ней неускоря-омая О-стопень. Кроме того, используются результаты из }2.
С помощью результатов из ы и 55 доказывается
Теорема 11. В каждой нерекурсивной р.п. у-степени содержатся бесконечное число попарно в<?-несравнимых р.п. множеств.
Эта теорема являотсл основным результатом ЛО. Кроме того. в этом же параграфе дается простая и интеросная характг рнстнха ковтигуадьных *-степеней, а нмянно: р.п. т-степень л является контнгуальной тогда и только тогда, когда все р.п. полурокурснвныо множества, принадлежащие о, являются ^-эквивалентными.
В 511 доказивается следующая
Тоорома 12. Всякая нерекурсивная р.п. ^-степень оодер-" ант бесконечное число попарно ьяу-носраннимых р.п. множеств.
Из вышеприведенных результатов создается впечатление, что осдй «"-сводимость сильное к-сводимооти, то каждая р.п. нероку-рсиваал "-сгепепь состоит либо из одной р. п. г-степени, лноо аз б осколочного числа попарно некрашшмш р. п. г-стсшвноя. Однако ото но. так. Недавно Доеной 420* получил ^неожиданный результат. Именно. он доказал, что суциструот'не)ч.куг<.'и1п:ал р.а. ^-стопень, состоящая точно из трих р.п. "-стсии-лоя.
В $12 изучаются °-степелн внутри '-^-еп'пкчи. Ряноу автором Ч43 доказано, что на классе р.п множеств -«-стопень п полная ьо-отепоиь совпадают. Кроме то;\\ клк-тн.лЛН!. что в каждое р.п. ^-степени содержите ли"«.- 1«дн<» р п •»-ото-
пень, либо бесконечное число попарно несравнимых р.п. "-степенен. Эти результаты имеют место и для ьао-степенай. Естествен-ьенно возникает вопрос <Ю. Л. Ершов): если "-степень р.п. мно-' жества а состоит из единственной 1-степояи. то состоят лд степень множества А из единственной ^-стьтнуяй-' ЗД?»цательный ответ на этот вопрос дает ирвгложжнь 12.'3. .-кстггвв. утверждает. что р'.к. тгго.^-сзеаень множеств* а с^у.т ъу еджкте-'жглг ;-с?еп*ня. но ьв^степекь множества устоит из бесконечного числа попарно ^-несравнимых р. п. "»-степеней. Таким множеством является л". когда * конечно строго гипоряросгое множество. .
I
Перейдем к содержанию главы IV, иосггдаетоз полным мно:ш-ствам. В этой главе проблема о соотношении между'ьяр-, ж?-, о-, ьу~, у-, т-полными р.п. множествами полностью решена.
Центральным результатом главы- 14 является теорема 13 из 513. которая доказывается с использованием результатов преди-дутих параграфов. •
Теорема 13. 1) Существует одновременно 0- и «-полное множество. не являющееся, -^-полным.
2) Существует одновременно =0- и ьу-полное множество, не являющееся ьзо_ПОлным.
3) Существует одновременно С- и У-полное множество, но являющееся ь«-полным.
3 Я4 естественным образом определяется г4 -сводимость для г«{о, ьзд, ьр}. ц показано, что р.п. множество г-полно тогда и только тогда, когда оно г,-полно. Для <3-сводимости это
доказано в ^213. В этом же параграфа получены критерии г-полноты р.п. множеств, для г^ьнр, сд, ьи}.
Наконец, в яослоднем параграфе 15 этой главы (и диссертации) с использованием свойств О-сводимости определяется еще одни новый нетривиальный класс р. п. множеств, содержащий только не т-полные множества и исследуется соотноаенио этого класса с аналогичными классами С.С.Марчонкова с13] и М.М.Арсланова с;
Теорема 15. Р.п. полурекурснвноо неускоряемое множество но мохот бить полным по Тьюрингу.
Автор выражает глубокую признательность академику РАН, проф. Ю.Л.Ершову за его постоянное внимание к работе и многочисленные полезные беседы, а также доктору Физ.-мат. наук А.С.Хараэипвили за поддержку и полезнее советы.
ЛИТЕРАТУРА
1. Арсланов ММ. Об одном класс« гипорпростых множеств-'-' Цат. Заметкг. - 1985. - Т.33. - «г. - С.872-8?.!.
2. Арсланов К. ¡4. Рекурсивно п-^ичколимки миомисть* и степени нера->розглмости. - Казань: к:<д-вс> КГУ. - 1КЧ'>. - 205 с.
3. Арсланов М.М. Локальная теория стчпен-г. нер^ч^кмости и ¿"-множества. - Казань: изд-во КГУ. - глс. - ио
•4. А?сланов М.М. Полнота в аркФметич'Х.:-..* керархиа и
иножества^АвтореС^рат докт. диссертаций. - н.-л«у-иокк-к. 1РЗЗ-
»
5. Булитко Б.К. О способах характ^риз-нич 1к..-!''их кножеств '"Изв. АН СОСР. Сория математическая. 19?!. - Т.ЪГ>. - К2. -С.227-253.
6. Денисов С.Д. Строение верхней полурешетки рекурсивно перечислимых "-степеней и смежные вопросы. 1 ''<Алгобра и логика. - 1978. - 7.17..- "6. -С. 643-683.
7. Дегтов А. К. Наследственные множества и табличная сво-димость^Алгебра и логика. - 1972. - 7.11. - «3. - С.257-269.
8. Дегтов А.!!. О и '"-степенях^Алгебра и логика. -1973. -Т.12. - «2. - С. 143-161.
9. Дегтов А Н. Сводимости табличного типа^АвтореФерат докт. диссертации. - Новосибирск.- - 1984.
10. Ериов Ю.л. Гиперпростыо »-степени^Алгебра и логика.
- 1969. - Т.8. - N5. - с.523-552.
11. Ершов Ю.Л. Верхняя полурешетка нумерации конечного множестЕа-"-'Алгебра и логика. - 1975. - 7.14. - ы3. - 0.258-282.
12. Кобзев Г.Н. О г-отделимых множествах''-^Исследования по мат. логике и теории алгоритмов. - Тбилиси: изд-во 7ГУ. - 1975.
- С.19-30.
13. Марченков С.С. О табличных степенях максимальных мно-жеств^Мат. заметки-. - 1976. - Т.20. - "3. - С.373-381.
14. Марченков С.С. Об одном классе неполных множеств^-' Мат. заметки. - 1976. - 7.20. - "4. - С.473-478. '
15. Оманадзе Р.1Л. Об ограниченной Q- сводимости^Сообщ. АН ГССР. - 1980. - 7.100. - "1. - С.57-60.
16. Роджерс X. 7еория рекурсивных- функций и эффективная вычислимость. - М. Мир. - 1972.
17. Еенфилд Дж. Степени неразрешимости. - Москва'. Наука.
- 1977.
18. Blum М. A machinu-independent theory of the comp-
lexlty of recursive functions^'.!. Asboc. Comp. Hach. - 19C7.
- V.14. - N2. - P.322-336.
19. Blum M." On the aize of Mchlnfs/.lnform. and Control.
- 1907. -V.il. - N3. - P. 257-265.
20. DUjtn P.. , Marquee I. On comp 1 fx 11 v pror>'*rti^K of rccu-rolvely enuiwr tblf cc-l^.v J.Zymv. Lotfic. 197"!. - V.Tlfl. - N4. -P.379-593.
21. Dourn»v R.G. Recursively enumerable m- and tt-dcgreea ■
O
I. The quantity of m-dfcrccc^/J. Eyrr.s. Logic. - 1909. - V.5i.~ N2.
22. Gill J.T. , florrlo P.M. On cubcrcative et.ts and S-re-duclbl 1 lty--VJ. Symb. Logic. - 1974. - V. j 9. - N4. P.Gb9-677.
23. Hoy L— The clacr; of recursively enumerable cubcets of a recursively -etiuwirablc set^VFacif. J. Math. - 1V73. - V.46.
- xi. - >r.MJ7/-iiaa.
24. :Uur;iuunn C£. The undccldabl 1 lty of the elementary theory of 'tlte !lt>rl.l.Tii; i.tlf trficurolvc ly cr.ur.veruble aetu-'/froc. of Intorn. ecu::. At-Uir.u«3ir.ln CFrefr, Cot.!"er'.onco 19ii4>. - Berlin:
- 1904.-Tut, j-72:.
23. lUMJjnaan, tZ. Oases of oinple c.»to, filter properties and tholi r.:>aiiitlon. llerni harbor 1 . C-'rli.".: Hurr..->olt-
Ur.lversltat. - :ivfi4. - SCO. - P.l/J-72. ' '
- 26. Kieenc 5.C. , Poet E.L. Tt.s uf.{.cr tfi-U! lice oi >v-greas of iccuroiv« uftoolvabllity.vi.hri. Soil: •..*'" - '-'-'4. -
V.39. - P.379-407. »
27. Lochlaa A.
