Тьюринговые скачки в иерархии Ершова

• Автор: Файзрахманов, Марат Хайдарович
• Шифр специальности: 01.01.06
• Научная степень: Кандидатская
• Год защиты: 2011
• Место защиты: Казань
• Количество страниц: 91 с.

Содержание
Введение

Глава 1. Тыоринговые скачки в иерархии Ершова

§1.1. Иерархия Ершова, конструктивные ординалы и системы обозначений

§1.2. Уровни иерархии Ершова, содержащие тыоринговые скачки 17 §1.3. Вычислимые нумерации семейств низких множеств

Глава 2. Элементарные теории алгебраических систем, порожденных низкими степенями

§2.1. Полурешетка, порожденная супернизкими в.п. степенями .

§2.2. Низкие в.п. и низкие 2-в.п. степени не элементарно эквивалентны

Глава 3. Е-скачки в иерархии Ершова

§3.1. Сводимость по перечислимости и е-степени

§3.2. Уровни иерархии Ершова, содержащие е-скачки
§3.3. Дополнения низких Пре-етепеней
Литература

Введение
Одним из важных понятий в теории вычислимости является понятие низкого множества, которое, интуитивно, выражает, что множество слабо вычислимо. Это связано с тем, что при изучении алгоритмических свойств множеств натуральных чисел часто возникает вопрос, при отсутствии подходящего вычислимого множества, о нахождении низкого множества, удовлетворяющего данному свойству. Например, согласно с теоремой Джоку-ша и Соара о низком базисе [34], каждый непустой П^-класс содержит низкое множество; по теореме Амбос-Шпииса, Джокуша и других [15], каждая быстро простая степень имеет низкое дополнение наверх. С другой стороны, существует большое количество литературы, посвященной низким множествам и их свойствам, которые напоминают свойства вычислимых множеств. Например, Соар установил [46], что решетка вычислимо перечислимых (в.п.) надмножеств низкого в.п. множества изоморфна решетке всех в.п. множеств; согласно с теоремой Робинсона [41], теорема Сакса о разложении справедлива в верхнем конусе любой низкой в.п. степени.
Множество А называется низким, если А' =т 0;- Таким образом, оператор скачка, не может различать вычислимые и низкие множества. В известной работе Бикфорда и Миллса [17] введено понятие супериизких множеств, которое естественным образом усиливает понятие низких множеств: множество А называется супернизким, если А! =и 0'. Стандартное построение низкого простого в.п. множества с сохранением вычисления скачка уже дает супериизкое множество (как и теорема о низком базисе). Однако ио каждое низкое множество является супернизким. Одним из следствий теоремы Сакса о разложении [43] является существование таких низких в.п. множеств А0. А, что Д0 О А — 0 и Д0 О Ау = 0'. Согласно с результатом Бикфорда и Миллса. [17], одно из таких множеств /10, А не супериизкое.

Более того, упорядоченные множества низких в.п. и супсрнизких п.п. степеней не элементарно эквивалентны (см. Доуней, Гринберг и Вебер [291).
В работах Ершова [5][6][7| построена иерархия множеств А 0', получившая в литературе название “иерархия Ершова”. Как оказалось, возникающая иерархия исчерпывает весь класс множеств А %' • Каждый следующий уровень иерархии содержит все предыдущие и не совпадает ни с одним из них. В представленной работе изучаются новые усиленные понятия низких множеств, а именно множества, тыорипговые скачки которых лежат в фиксированных бесконечных уровнях иерархии Ершова. По результату Карстенса [18], множества А из первого бесконечного (А“1-) уровня иерархии Ершова характеризуются условием А 0'. Поэтому первым уровнем такой иерархии скачков будет класс супернизких множеств.
Первый, естественно возникающий, вопрос при изучении иерархии Ершова для скачков - будет ли каждый уровень содержать скачки, по лежащие в меньших уровнях. Легко проверить, что для конечных уровней это не верно, то есть, если АI п-п.п., тогда А! в.п. В первой главе устанавливается, что и бесконечные уровни могут ие содержать тыорипговые скачки. Более того, сели дан ординал а < ш2 и А! Е А”1, тогда А супор-низкое (в частности, если А! € Е~ тогда А' £ А“1). Вторая часть перво!! главы посвящена вопросу о существовании Д^-вычислимых нумераций классов скачков. Впервые этот вопрос был изучен Ниисом. В работе [39] он ввел понятие множества с трассируемым скачком и установил, что для в.п. множеств этот класс совпадает с классом супернизких множеств. Класс множеств с трассируем скачком будем обозначать JT. Индексное множество в.п. множеств из JT принадлежит Ед-уровшо арифметической иерархии. Следовательно, класс всех супернизких в.п. множеств имеет вычислимую нумерацию. Однако, в общем случае множества е трассируемым скачком могут не быть супернизкими. Тем не менее в § 2 устанавливается.
Теорема 1.3.6 (Ниис [39]). Существуют со-в.п.,множество А. такое что
А € ТТ — 5Х.
Более того, множества с трассируемым скачком могут не быть низкими. Так в книге Нииса [40] приведен пример высокого множества с трассируемым скачком.
В этом параграфе мы приведем достаточные условия вычислимости семейств низких множеств, откуда будет следовать Е~1-вычислимость семейства всех супернизких множеств.
Теорема 1.3.7. Пусть даны обозначения а,Ь Е О и элемент е (Е си. Тогда множество Ме = {г : У(а,е)' ф У(Ъ,г)} в.п. относительно 0' равномерно по е. Другими словами, сугцсствуетп вычислим,ая функция д, такая что М,. = для всех е.
Доказательство. Для каждого г построим равномерно по i тьюринговый функционал Ф,. Используя теорему рекурсии с параметрами, можно считать, что в начале построения мы имеем такую вычислимую функцию п, что для всех г Ф,- = Ф„(г)- Следовательно, равномерно по г мы можем указать вычислимую функцию })„,, такую что
Ф,(Х;ж) 4.0 Фп^фХДфх)) 4
Конструкция Ф;.
Шаг я=0. Полагаем Фгд(ст) = 0 Для всех а Е 2<ш.
Шаг 1-1. Для всех х Е со и для всех а Е 2<и} полагаем Ф^.+Дсг; х) 4-= 0 в том и только в том случае, если Ф-^+Дсг; х) 4- и либо т(Ь, г, ЛДт), 5 + 1) = -1, либо (р^+1{т(Ь,г,кфх), в + 1),ЛДж)) = 0.
Полагаем Ф* - [Д* Ф^.