Введение к работе
Актуальность тони: Теория алгоритмов (рекурсивнихфункций) является одним из современных и бурно развивающихся разделов математической логики. В блестяаях работах 30-х годов Черча,, Клини. Тьюринга и Геделя были получены основополагающие Факты о природе алгоритмов; доказана эквивалентность различных уточнений понятия вычислимой функции, сформулирован и обоснован тезис Черча. доказаны теоремы об универсальной Функции, s-m-n теорема ' и теорема о рекурсии. На этой основе удалось доказать нераэро-решимость многих важнейших алгоритмических проблем математики. Все это правело к бурпому развитию теории алгоритмов, которое продолжается и сейчас. Начало развития важнейших его разделов -тоории рекурсивно перечислимых (р.п.) множеств.и степеней неразрешимости - относится к оце более позднему времени - середине 40-ых - началу 50-ых годов. Именно в эти годы были опубликованы Фундаментальные работы Е. Поста с32, ЗЗЗ, С. К. Клики и Б. Поста C25J. содержащие не только первоначальное методы а результаты теории, но и определивши пути ее развития.
Для каждого множества a, л&>=^о.1,2 К кскзо с$срму-
лрсг.ать следующую проблему: существует ли алгоритм, позволяющий для любого х«" ответить на вопрос о принадлежности * к а. Множества, для которых данная проблема разрекгама, били названа рекурсивными. Однако, скоро выяснилось, что существуют различные по своей "сложности" р.п. множества, не являющиеся рекурси-FHWMii. которое стали особым объектом изучения. Инструментом для клас,:.::: лкаци;! подмножеств" по их "сложности" служит понятие
сводимости» являющееся одним из Фундаментальных в теории алг ритмов. На интуитивном уровне множество а сводимо к множеству . если существует алгоритм, который решал бы проблему вхожде ння элементов для А нри условии, что есть возможность пользоваться информацией о принадлежности тех или иньїі элементов множеству в. Такая сводимость в самом общем виде называется тьюрин-говоя ст-> сводимостыэ.
Результаты и методы теории алгоритмов быстро нашли свое применение в различных областях математики. Выяснилось, что многио из известных проблем являются неразрешимыми. Такими будут, например, проблема распознавания тождественной истинности формул исчисления предикатов, проблема тождества слов конечно определенных групп и полугрупп, 10-ая проблема Гильберта и другие. Часто неразрешимость одной проблемы доказывается посредством сведения к ней другой, о которой заранее известно, что она неразрешима. Эта последняя проблема в боль- винстве случаев является проблемой разрешимости подходящего Р. п. множества.
Наряду с т-сводимостью в 1944 .году Э.Пост С323 ввел некоторые специальные виды сводимостей, такие, как га-сводимость табличная ctt-э и ограниченная табличная cbtt-j сводимость.
Крупный вклад в изучение этих сводимостей внесли С.Клип и Э.Пост, Ю.Л.Ершов. А.Лахлан, Г.Сакс. К.Ейтс, Р.Фридберг, К.Джокуш, А.А.Мучник, А.Н.Дегтев, М.М.Арсланов, С.С.Марчонкс 'С.Д.Денисов, Г.Н.Кобзев и другие. Приведем несколько результатов, полученных в этом направлении. Ю.Л.Ершов показал, что ьорхняя полурешетка р.п. "-степеней, не является решеткой и
- ь -
построил пример р.п. "-степени, под котороп нет.минимальной "-степени сдз Он же дал полное описание полу решетки "-степеней с 103. А. Лаг лан описал начальные сегменты р. п. "-степеней, а также доказал, что каждая р.п. нерекурсивная Т-степень содержит минимальную ^-степень с263. Г.Сакс ^34^ показал, что р. п. т-степени упоядочены плотно относительно ^сводимости. Изучая верхнюю полурешетку р.п. "-степеней, А.Н.Дегтвв показал, что ока не является решеткой, имеет минимальные элементы. а такгке такие элементы, под которыми нет минимальных ^63. Он «в доказал, что каядая р.п. нерекурсивная т-степень содержит учетное число попарно несравнимых р.п. "-степеней С7]. ".Д.Денисов охарактеризовал верхнюю полурекетку р.п. "-степени с 53.
Кроме этиг видов сводимостей некоторыми авторами были оп-яделени другие виды сводимости. В частности, С.Теяненбаум дал определение О-сеоднмостя следующим образом:
Множество А 0-сводится к множеству о, если
(3f О. Р. ф. )
Понятие Q-сзодимости язляется весьмо естественным и вазк-п;м для ттории алгоритмов. С помоеью этого понятия был нолу-ігн ряд кнт&рооных результатов. Этому понятию принадлежит лавная роль в решении G.C. Марченковым с 13^известной проблемы iocra методами самого Поста. Q-сводякость используется в ис-.-& довйнйях кекоторих других областей теории алгоритмов, ва-гт.'^вр. в исследованиях по проблеме тождества слов и по слож-ости гычисленлй. . 0-сг-;дттмость по сравнению с другими видами сводимостей
" G -оказалась наименее изученной. Это, по-видимому, объясняется тек, что приятие о-сводимости не отличается такой простотой, как «-сводимость; в ее определении участвует р.п. множество tft
Если от множества vf(K', , из определения Q-сводимости, потребуем удовлетворение некоторым естественным условиям, то получим понятия, (Золее сильные чем Q-сводимосгь. Именно, скажем, что множество а eQ-своднтся (или сильно Q-сводится) к множеству в, если выполняется (*) и дополнительно,
(3S О.р.ф. ) 0* ) (Vy )'(yeVf ( к1 *y
Если, кроме того, существует число "«», такое, что
то скажем, что множество а ьзє
В изучении различных сводимостея явно выделились три направления. Одно из них заключается в том, чтобы охарактеризовать г-полные множества и выяснить соотношения, например, по включению, между классами г-полных множеств для тех или инь сводимостея г-. Другой связано с вопросами строения полурешеток -степеней, в особенности р.п.' г-степеней. Третье - с вопросами, сколько г-степеней имеется и как они расположены в степенях относительно более слабой сводимости.
В работе, eel А.Н.Дегтевым дано окончательное решение трех проблем; для класса сводимостоа табличного типа, относящихся к указанным выше трем направлениям.
- 7 ,-
Замечателъныо результаты по разра^эдке сбдих методов, позволяющих описать полные в соотвотетвуюцем уровне -арифметической иерархии классы арифметических множеств и яолутать тпа осново этих методов конкретная критерии полноты для l-, п-мноместв Сп-Р. принадлежа? М.,4. Арсланозу tO.
Ряд результатов относительно указанных видов сводимостей приведен в книгах Х.Роджорса С15Э, Р.Соара ^37^, П.Одифродда С31Л Н.М. Арсланова ^2,3^, Дж.їЛеЕ^илда ^1вз. Интересные критерии Q-полноты р.п. множеств получены в работе В.К.Булитко с53.
Весьма интересные связи р.п.
Со времени публикации в 1SCT г. двух статей И.Злюма 47, 183, в исследованиях сложности вычислений рекурсивных функций возрастающую роль начгпают .играть методы з результаты "чистой" тоори.и рекурсивних функция, особино теорема о рекурсии и методи приоритета.
И'2.ЧЬЇЇ_раС2ІН ЯВЛЯеТСЯ РЭПеЯНв ЛРСЙЛ5.М. ДЛЯ r^{Q,sQ,bsQ}-
свсдякостеЕ, относящихся к следующим направлениям-' і. Исследование есяямных связей между елояностными свойствами р.п. множеств и г-сводимостей. її. Изучение строения долурешеток р. п. г-стененеи. т. Выяснение сколько г-степеней имеется и как они расположены в степенях относительно более слабой сво-
- fi -
днмости. IV. Характерязация г-полных множеств и выяснение соотношений .между классами г-полных множеств, где
rc-{T,Q,V,sQ,bV,bsQf.
Основные метоли. Для доказательства основных результатов используются различные приоритетные конструкции, теорема о рекурсии, методы метрической теории алгоритмов, свойства неуско-ряемых и нигде не простых множеств.
Научная новизна. Все существенные результаты работы являются новыми. Они значительно обогащают и дополняют то небольшое число известных фактов о Q-степенях и сложностных свойствах р.п. мнонеств, которые были установлены ранее другими авторами.
Практическая и теоретическая ценность. Результаты работы представляют теоретический интерес. Они могут быть использованы в дальнейших исследованиях в теории алгоритмов. Основними результатами являются: установление эквивалентности понятия . аР-полцого р.п. множества, эФФективро субкреативного множества, сильно эффективно ускоряемого множества; доказательство ряда структурных свойств полурешеток р.п. г-степеней
. ПОЛНОе РЄШЄНИЄ ПРОбЛеМЫ О СООТНОШЄНИЯХ МЄЖДУ КлаССаНИ г-поЛНЫХ р.П. МНОЖеСТВ. r<*-{r,0,V,sQ,bV,bsQ}.
Апробация работа и публикации. Результаты работы доклсда-иа'лись на семинарах "Теория нумерации", "Конструктивные моде-ха".Е "Алгебра и логика" в Новосибирском государственном унй- Вурсатоте, на семинарах отдела дискретной математики Института
- a -прикладной математики им. И.Н.Векуа ТГУ, на общепнститутском семинаре ИПМ им. И.Н.Векуа ТГУ. на семинаре по математической логике и теории алгоритмов в Московском государственном университете, излагались на vi и Международном конгрессе по логике, методологии и Философии науки (Москва. 1987), на пленарном докладе "і Межреспубликанской конференции по .математической логике (Казань, 1992).'Все основные результаты опубликованы в работах с 39-552.
Объем и структура работы. Диссертационная работа состоит из введения, четырех глав,_ объединяющих 15 параграфов, и спи--ска литературы, насчитывающего 112 наименований. Общий объем работы 195 страниц.