Конструктивизируемость структур и их степени неразрешимости

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

1 Д“-спектры линейных порядков

1.1 Д 2-спектр

1.2 Линейные порядки, сильно похожие на Т]

1.3 Квазидискретные линейные порядки

2 Вычислимые алгебры Ершова

2.1 2-низкие алгебры Ершова

2.2 3-низкие алгебры Ершова

3 Класс вычислимых множеств

3.1 Теоретико-множественная структура

3.2 Теоретико-множественные сводимости

3.3 ЗЕТ- 1-сводимость на классе вычислимых множеств

Литература

Одной из важных задач в теории алгоритмов является изучение алгоритмической сложности различных счетных алгебраических структур на основе построения эффективных представлений этих структур на множестве натуральных чисел. В данной работе мы исследуем такие алгебраические структуры, как линейные порядки и алгебры Ершова.
Исследования в этой области были начаты Л. Фейнером в конце 1960-х и продолжены в работах Дж. Реммела, С.С. Гончарова, Дж. Найт, К. Эша и других. В частности, было показано, что существуют вычислимо перечислимые булева алгебра и линейный порядок, не имеющие вычислимые изоморфные копии (см. [1] и [2]), другими словами, являющиеся неконструк-тивизируемыми.
В последние года активно изучаются такие вопросы, как описание спектра счетных алгебраических структур. Например, Т. Сламан (см. [3]) и С. Вейнер (см. [4]) независимо друг от друга построили такую счетную структуру А, что 5'рес(Д) = О — {0}, где И — класс всех тьюринговых степеней. Р. Миллер в [5] доказал, что существует такой линейный порядок Ь, что 5рес(Д) П А® = Д° — {0}. С. Гончаров, В. Харизанов, Дж. Найт, К. МакКой, Р. Миллер и Р. Соломон в [6] построили для любого пбш такую структуру Ап, что 5'рсс(Ап) = П — Ь„, где Ь„ — класс всех »-низких степеней.
В этой работе мы докажем, что для любого п Є и существует такой линейный порядок £„, что 5рес(£п) П Д° = — Ь„.
В [7] Р. Доуни и М. Мозес показали, что любой дискретный линейный порядок низкой степени имеет вычислимую копию. Мы обобщим этот результат, доказав, что каждый 2-низкий квазидискретный (и, следовательно, дискретный) линейный порядок изоморфен вычислимому порядку. Причем,
покажем, что для 3-низких квазидискретных порядков этот результат не верен.
Также Р. Доуни спросил, какие еще существуют свойства линейных порядков Р, что для любого низкого линейного порядка Ь из Р(Ь) следует существование вычислимой копии. В этом направлении мы докажем, что каждый низкий линейный порядок, ’’сильно похожий” на г/, изоморфен вычислимому порядку (причем для 2-низких это не верно).
Отечественными и зарубежными учеными активно исследуется также вопрос о тг-низких булевых алгебрах и алгебрах Ершова. В [1] Л. Фейнер построил вычислимо перечислимую булеву алгебру, не изоморфную никакой вычислимой алгебре. Построенная им булева алгебра не изоморфна никакой п-низкой алгебре, ни для какого натурального п. Естественно возникает вопрос: каждая ли га-низкая (для любого п £ ш) булева алгебра имеет вычислимую копию? Постановку этого вопроса можно найти, например, в [8].
В общем случае ответ на этот вопрос пока неизвестен, известны частичные ответы. В [9] Р. Доуни и К. Джокуш доказали, что каждая низкая булева алгебра изоморфна вычислимой алгебре. В [8] Дж. Найт и М. Стоб доказали, что любая 4-низкая булева алгебра имеет вычислимую копию. В этой работе мы покажем, что каждая 3-низкая алгебра Ершова изоморфна вычислимой алгебре.
В теории вычислимости особое место занимают исследования теоретикомножественных свойств различных структур, особенно теоретико-множественные свойства класса вычислимо перечислимых множеств относительно вычислимых множеств.
В третьей главе данной работы изучается теоретико-множественная структура класса вычислимых множеств относительно полиномиально вычислимых и примитивно рекурсивных. В этой главе вводится классификация вычислимых множеств и доказывается, что каждый класс введенной классификации не пуст.
В третьей главе вводятся и изучаются две так называемые теоретикомножественные сводимости. Доказаны теоремы о нормальной форме для каждой сводимости, критерии минимальности и плотности. Используя криОчевидно, что п(х) является полиномиально вычислимой. Так как 0 Соо R, то существует бесконечно много таких чисел х, что х £ R. Таким образом, для любого числа х > 0 существует число у = п(х), то есть можем считать, что л(т) — сюръекция.
Пусть D = (А — P)U{æ € R р(п(х),х) = 0}. Имеем А = DUR. Осталось доказать, что D ^-предельно.
a) Если р{п(х),х) = 0, то х € D, так как иначе х fi R. Тогда 0 = р(п(х),х) =р(к,х) = 2, противоречие;
b) Если р(п{х),х) = 1, то х £ D, так как иначе х ^ R. Тогда 1 = р(п(х),х) =р(к,х) = 2, противоречие.
Таким образом, по предложению 3.1.7 множество D является V-предельным.
II) В случае, когда А не является Р-коиммунным под ш, доказывается аналогично пункту I.
III) Пусть А Т-’-бииммунно в 0 Соо ш ■ Зафиксируем такое полиномиально вычислимое множество R, ЧТО 0 Coo R Соо а1- Тогда 0 Соо RÇAUR и 0 Соо RÇAuR. По пункту I существуют такие V-предельные множества Di и D2, что ADR = DiUR и A(JR = D2L)R. Тогда А = (j4Ui2)fl(AUR) = (Di U R) П (D2 U R).
Очевидно, что представление множества А в случаях 1 - 3 в условии теоремы улучшить нельзя. Пусть множество А является V-бииммунным в 0 Соо w. Предположим, что множество А можно записать с помощью теоретико-множественных операций с использованием меньшего числа V-предельных множеств. В этом случае, легко видеть, что существует такое бесконечное V -предельное множество D. что D С. А или А С D.
Рассмотрим случай, когда DCA (случай А С D рассматривается аналогично). Так как 0 Соо D и D ©-предельно, то существует такое полиномиально вычислимое множество Р, что 0 Соо Р Соо D. Получили противоречие с V-иммунностью над 0 множества А. □