Введение к работе
Работа посвящена двум большим разделам теории алгоритмов - теории иерархи? и иг -.ексным множествам. Оба раздела возникли в период формирован"ч теории алгоритмов и играют в увй цв-j нтральную роль. В замечательные работах 30-х годов Чёрча,Кли-| ни, Тьюринга и Гёделя были получены основополагающие факту о природе алгоритмов: доказана эквивалентность различных уточ- ; нений понятия вычислимой функции, сформулирован и обоснован тезис Чёрча, доказаны теоремы об универсальной функции, S-nwi -теорема и теорема о рекурсии. На отой основи далось доказать неразрешимость мноп ; важнейших алгоритмических проблем математики. Все это привело к бурному развитию теории аігори-тмов, которое продолжается і. сейчас.
Исследование рекурсивных иерархий началось с рр^от Клини; [Z&] и Мостоеского [32] , в которых зведена и изучена иерархия, называемая теперь иерархией Клини-Моссовского. Класс 2ц 1п<оо) этой иерархии состоит из всех подмножеств на- ; турального ряда О), определимых з системо (Ш",+і'» 0,1) j
2^-формулой языка логики предикатов. Из-за связи с арифме- ТИІСОЙ иерархия называется также ерифметкческой. Чтобы не делать некоторых исключений, будем считать Е.%~{0} Пп обозначает класс всех дополнений до '^-множеств, А^~ 2l П Ля. Важным свойством арифметической иерархии являем я наличие в любом Хп и зжества, наиболысего по т.-сводимости, называемого "2-универсальнш, и соотношения Х^иП,, =4ЛН ,
^я т Па Эти свойства являются характерном для любой иерархии. Другим важным свойством явіяется доказанная Клини и Постом связь с Тьюринговьаі скачком: при любом а<ш 2дН-универсальноо множество рекур-давно изоморфно Т-скачку 5L-универсального множества.
дальнейшее развитие теории алгоритмов привело ic появлению друг: .с иерархий. Они естественно расрздемтся нз более грубые и более тонкие, чем 'арифметическая. Важнейшей грубой иерархией является аналитическая иерархия { ческой, только теперь наряду с к..знтороыи по числам можно на- . :; вёшиаать и кванторы по функциям из Ш во). Сразу было заме-' чено, что -»- *» сД,, и возникла проблема характеризации і класса Л| через более прэстые множества. Аддисон заметил [15 ] , что эта проблема аналогична известной пробле* из дес- ; кркптивнои теории множйств, если считать арифметическую иерар- I хию аналоюм борелевской, а аналитическую - аналогом проектив-. ' ной иерархии Н.Н.Лузина. Эта аналогия оказалась исключительно глубокой и плодотворной. Как выяснилось, в случае иерархий классов функций лш по существу имеем дело с единой теорией, в і которой классические иерархии являются "предельными" случаями [ рекурсивные. Аналогия Аддисона хорошо поясняет решение проблемы характеризации . h1 . Надо построить трансфинитное продолжение арифметической иерархии по асем рекурсивны' ординалам -аналог иерархии Еорнля по всеа счетным ординачам.. Объединение : всех уровней этой иерархии, называемой гиперарифметической, и дает h\ 27,,35] . Эта теорема Суслина-Клини замечательна тем, что дает информацию об определимости в логике второго порядка. ' Из других грубых иерархий заметную роль играет иерархия, получаемая итерированием операции гиперскачка [ЗИГ] , она аналогична иерархии С-множеста, В данной работе нас в основном будут интересовать тонкие иерархии, поскольку они наиболее полезны в изучении/ндексных 'множеств. Первым примером такой иерархии (не считая субрекур-'силных, которые здесь не рассматриваем) была иерархия Ершова Ч^їі)а^и> Г41 Оказалось, что уЗЕ^Яйг» к возникла Аналогичная рассмотренной выше проблеме задача характеризации Wtfeca h^. Она решается \4, ч.й\ также путем транефкнитного ЭДродолжьния иерархии Ершова по всем рекурсивным ординалам: ,Aj'"Z-a = А » г^е (,0'і^о) - клиниевская система орди- Анальных обозначений . В [4, ч.Пу получено описание иерархии ЕрмБй через m-ікачок, аналогичное описание арифметической иерархии через Т-скачок. Аналогом иерархии Ершова в дескриптивной теории ынонеств является разностная иерархия, восходящая к Ку^ато ведому ч Хаусдорфу. Иерархия Ершова изуче- ;. на не столь полно, как ар -ыетическая. Так, в [4, ч.Ш] оста- ; влены отары*, jmh дві вопроса о релятивизованных вариантах "той иерархии. Многими автореми (Купер, Лахлан, Джокуш, Шор,Ы.М.Ар-1 слагав, Н.Р.Бухараев, Ш.Т,.Итмухаметов и др.) изучались вопросы 0 Т-степеня>: JL~ -множеств и о связи иерархии Ершова с клас- j Анализ теоремы -'д. шт-Клмни, характеризацки Аг, и многих аналогичных фактов из дескриптивной теории множеств (С-множества, R -множестьа и др.) показывает естественность и важность следующей задачи: найти естественный класс иерархий 3 такой, что: гиперарифметическая иерархия принадлежит З І еслиІєЗ не дискретна в данксм уровне, то найпется иерархия 1 « 9 , являгааяся плотным утончением ї в этом уровне*, любая; ем подходящей І Є 3 в некотором уровне; любил последователь- ; Класс Э давал бы в определенном.смысле идеальную классификацию гиперарифметических множеств с точки зрения теории иерархий. Поэтому будем называть поставленную задачу проблемой нахождения полной иерархической классификации гкперарифмети- '. ческих множеств (или арифметическ'*х множеств - последнее в том случае, когда речь в постановке задачи идет только о конечных уровнях). Эта проблема впервые поставлена авторам [44J . Независимо близкая задача поставлена в дескриптивной теории множеств А.Луво 9]| » Эта проблема будет решена ь данной работе. :" Рекурсивные иерархии имеют.много применений. Это обусловлено тем, что иерархии ввделтзт в очень сложной структуре степеней неразрешимости некоторые "эталонные" степени, с которыми можно сравнивать по сложности различные объекчы. Поскольку ота эталонные степени упорядочены "почти" КД ординалы (за исключением того, что каздое эталонное множество m-несравнимо со своим дополнением), поязляется возможность измерять алгоритмическую сложность . дожеств ординалами аналогично тому, как гесме .ричоекие или физические величины измеряются чмела- ми. Ситуацию поясним на рис. I. [Здесь Ct0, Q(l - га-степени, і оп_ .являемые соответственно мно нения невелика. Ка самом деле ото не так; естественно возника-щие множества, как правило, универсальны б некотором конечном уровне подходящей иерархии и потому могут быть "измерены" точко (с точностью до рекурсивного изоморфизма). Этот "эмпири- ; ческий" факт в лрдаенеьии к индексным множествам впервые сформулирован Роджерсом, поэтому будем его называть тезисом Род- КЄрС . ,Для примера рассмотрим некоторые применения к логике. Хотя известный результат бефор-.іана (см. [ііЗ ) показывает, что в любой рекурсивно перечислимо {* Т-степени найдется рекурсивно .аксиоматизируемая элементарная теория, все "естественные" рекурсивно аксиоматизируемые неразрешимые теории (например, арифметика Пеане или теория групп) универсальны в 2 . Интерес- \ ныо результаты по характеризации сложности различных классов . прв,ілоаений получены М.Г.Перетятькиным [ДОЗ . Например, если {Ц'п\ л<ш - гёделева итерация всех предложений конечной досаато'но богатой сигнатуры, то множество {nl ifa полно и > имозт посетую модели универсально в П| , а {п\ (рп имеет j простую модель ) -в Хг Перейдем к индексным множествам,,Следуя А.И.Мальцеву, (ч.р.ф.) будем называть нумерацией Клини и обозначать X , а нумарацип ьсех рекурсивно перечислимых множеств (р.п.м.) бу- ' дем называть нумерацизй Поста и обозначать ЗІ . Индексным множеством сёиейства ч.р.ф. f называю1" эс"ЧА)в-{п| Hrte А) , анаяогична.для р.пи. В«пл .яная определение нумерации Клини, видим, что X {h) можно отождествить с совокупностью всех ал- ! га ритмов, вычисляющих функции из А „ Известные результаты теории нумераций показывают, что индексное множество определено весьма инвариантно: индексные множества одного л того ко семейства в двух главгчс вычислимых нумер;щиях рекурсивно изоморфны. Все ото показывает, что индексные кнсжествп являются естественными и важньш объектами (і обусловливает полезность ух изучения» Исследование индексных множеств иокго разбить на 3 направления! I) экстенсионально;;, т.е. по возможности без ссылок на номера, описание семейсгв, индексные {множества которых лежат в данном классе данной иерархии, 2) вычисление сложности конкре'зннх важных для теории і горитмов индексных множеств и 3) изменив степеней индексных множеств по данной алгоритмическое сеодимости. В замечательной работе [3$},отчосщейся к I), Райе получил две важных теоремы,носящих нша его имя. Пусть А - семейство р.п.м. Первая теорема Раиса утверждает, что ?Г ЧА) рекур-сивно з точности тогда,когда А пусто или совпадает і классом всех р.п.м» Вторая теорема (называемая такке теоремой Рпйса-Шапкро) утверждает, что Я;*'(A) р.п. в точи ;ти тогда, когда к пусто или является классом всех р.п. наддаоместв некоторой эффективной последовательности конечних ШСЖЄСТВ. Впоследствии В.А.Успенский [l4] , Л.й. Мальцев н ЮЛ.Ераов (см. fj)l ) распространили эти результаты ка абстрактные классы нумерованных .множеств, БКЛЕчаицив нумерацій) Клини. Первая терема РаРса показывает, что никакое нетривка, ьное свойство вычислимых функций нельзя эффективно распознать по виду алгоритма? ото является отправной точкой в некоторых исследованиях по теоретическому программированив. Вторая теорема Раиса сыграла свою роль в формулировке понятия нумерованного множества с аппрок- : симацией и в применении к функционалам конечных типов г5} , что таяве интересно для теоретического программирования. Исследования в направлении 1} продолжались РаРсотл [34] , Деикером и МаЯхиллом |іб} и другими «вторами. Роджерс [її] . поставил проблему экстенсионального опг акия семейств р.п.м., индексные множества которых лежат з S^ при nt ^- 2 . Этим и близкими вопросами занимались Джокуш (см.", fill , с.471), Грасскн..[і8] , Х^й |23] , автор [12,13] и другие, но " 7 проблема оставалась нерешенной. ', Много внимания в литературе уделялось направлению 2), По ! существу, введение любого нового класса р.п.м. сопровождалось | попытками вычислить сложность его индексного множества. Это і объясняется, помимо естественности такого вопроса, неожиданны-і ми и глубокими применениями некоторых из этих результатов. Так,1 Ейтс [373 использовал свою теорему о том, что для любого р.п.м.1 Т множество {а\У„ет т) универсально в "2З'т, для относите-I льни простого доказательства теоремы Сакса о плотности р.п. і Т-степеней, Херрман 243 сумел применить оценки сложности ин- і дексных множеств для доказательства неразрешимости элементарной теории реиетки р.п.м. Интересные результаты получены Ейтсом " [38} и С.Каллибековым [7] : для любого р.п.м. Т множества WKnsmT> , {n.lTs?m3rft\ и {rU#nsmTi в нетривиальных случаях универсальны в Zg , а множество{nl3ta*mT ^=/^, - в П3 Из других результатов отметим полученную независимо Ю.Л.Ершовым и Л.Хэй ( [4, ч.Ґ] и [193 ) классификацию индексных множеств конечных семейств конечных множеств. Оказалось, что любое такое индексное множество универсально в одном из 21 п, Мы уделим большое внимание этой проблематике, причем впервые задача будет рассматриваться в большой общности: попытаемся классифицировать индексные множества предикатов, формульно определимых в решетке р.п.м. (8; и,П). Очевидна связь этой задачи со сложностью элементарной теории ТЬ(Б) и с модельными свойствами Th(S). При этом оказываются необходимыми описанные выше иерархии из 3 . Например, из наших результатов будет следовать, что множество і<п»»п>1Ят«ЯпЛ (Ят#0 У "%пФш)} нельзя охарактеризовать с помощью арифметической иерархии и релятивизованных вариантов иерархии Ершова. Если мы хотим сохранить упомянутый выше тезис Роджерса, надо искать новые иерархии, позволяющие оценивать такие множества. Аналогия с ситуацией, когда желание измерить диагональ единичного квадрата приводит к необходимости расширения системы рациональных чисел. Отметим, что такого рода соображения сыграли большую роль .в формулировке и решении проблемы полной иерархической классификации арифметических множеств. В направлении 3 изучались в основном структуры т- и Т-степенеЙ индексных множеств. Интерес к этому объясняется | тем, что эта задача является в определенном смысле предельном : случаем задачи 2) и тесно связана с изучением фактор-объектов данной нумерации. В этом направлении много работала Хэй [20-22] , однако полученные результаты косили в основном локальный! характер. Не было получено результатов, относящихся ко всей і структуре m -степеней индексных множеств. Целью диссертации является продолжение исследований упо- | минутах вопросов, а именно: I) исследование релятивкзованных ! вариантов иерархии Ерлова и ее соотношения с иерархией высоких1 -низких множеств, 2) построение полной иерархической классификации арифметических множеств и исследование построенных иера-. рхий, 3) разработка общих методов вычисления сложности индексных множеств, определимых в естественном языке, с помощью построенных иерархий, 4) получение общих результатов о структуре гп -степеней индексных множеств, 5) решение проблемы экстенсиональной характеризации семейств, индексные множества которых лежат в данном классе арифметической иерархии. В соответствии с этим диссертация разбита на 5 глав. Каждая глава разбита на 4 параграфа, нумерация которых сквозная. Общий объем работы 245 с., список литературы вялвчает 94 наименования. Наиболее принципиальные результати названы теоремами, их 10 и их нумерация сквозная по всему тексту. Нумерация остальных утверждений своя в каждом параграфе. Так, предложение 5.1 - это предлопение 1 из 5. На "качественном" уровне основные результаты могаго сформулировать так: а) полностью изучено взаимное расположение иерархии Ерлова и иерархии высоких-низких мно -неств, б) подробно исследованы релятивизованные варианты иерархии Ершова, что позволило, в частности, уточнить постановку задачи о полной иерархической классификации арифметических мнокеств, в) найден естественный класс иерархий, полностью классифицирующий арифметические множества, г) найдено описание построенных иерархий с помощью теоретико-множественных операций, которое показывает, что эти иерархии начнется рекурсивным аналогом степеней Уэджа борелевских множеств [29] , д) найдены применения построенных иерархий К ВКШІСЛеНИ'О СЛОЖНОСТИ !Ш~ дехснкх множеств, что позволило полностью классифицировать булевы комбинации А-преликаїов Яахлана и ответить на один вопрос! Со ара [ЗбЗ , е) показано, что проблема экстенсионально го опи- і саниа кндек них множеств решается положительно при И>3 и j отрицательно при п.-'.{ , и) найдена глубсчая связь м...яду теорией полных нумзраций w некоторой вопросами теории алгоритмов, что приводит к многочисленным применениям теории полных нумераций к степеням неразрешимости, вычислению сложности конкретных индексных множеств и к изучению структуры m-степеней ИН-! декеных множеств. Применяемые методи исследования весьма разнообразны. Ори-; гянальны алгебраический катоды в главах 2 и 3, где проблемы-решаются путем "наведения" подходящей.алгебраической структурі и достаточно глубокого ее изучения. На протяжегш всей работы испольэуютсл теорема о рекурсии для предполных нумераций, нумерованные множества с аппроксимацией и теория, полных нумераций, В главах 2, '4 и'5 используются идеи из теории операций над ьножестза?.Пл, а в главах 3 и 5 - из теории конструктивных к : р.п. алгебраических сирієм. В главе I используется оригинальная комбинация метода приоритета и метода "китайских ящиков" Лахлана. Результаты диссертации докладывались на семинарах "Теория нумераций" и "Алгебра и логика" в Новосибирском университете, -на семинарах по математической логике и теории алгоритмов в Казанском, Московском, Казахском и Латвийском университетах, в, ЛСМ;'- АН СССР, в пленарных докладах на 8 и 9 Всесоюзных конфе- , ренцнях по математической логики, в секционном докладе на 8 М&адутародном конгрессе по логике, методологии и философии науки е г.Москво. Воэ основные результаты диссертации являются новьми и
сификацией высоких-низких множеств ЗбЗ . Эти вопросы будут і
рассматриваться и в.э'^ой работе. :
1^9 , кроме гилерарнфмзтической, является плотнш утончени-1
ность иерархий из 3 , каждая из которых утончает яредыцущу», I
конечна. Используемые понятия буду? уточнены ниже. ' : смысл !
ясен из примеров: гиперарифметичвсяая иерархия - плотное угон-
ченке аналитической в первом уровне,, иерархия Ершова - плотное!
утончение гиперарифметической во второй.урочне,, иерархия Ершо-1
ва дискретна, т.е. не имеет утончений ни в каком уровне.
жествами 0 и со , а "конус" со-
/ стоит из остальных Ш-степеней.
Известный метод кодирования кон
структивных объектов натуральни
ми числами сильно расширяет об
ласть применимости, иерархий. По
скольку иерархии - инструмент
более грубый, чем тепени нераз
решимости, на первый взгляд ка-
Рис. I жется, что возможность их приме-
сіандарткую нумерацию всех частично рекурсивных функци;! '.
опубликованы в [39-54J . ''"'