Содержание к диссертации
Введение
Глава 1. Основные определения и обозначения 12
1.1. Теория вычислимости 12
1.2. Теория линейных порядков 15
Глава 2. Естественные отношения на вычислимых линейных по рядках 21
2.1. Естественные отношения 21
2.2. Отношения предельности 27
2.3. Алгоритмическая независимость естественных отношений . 36
Глава 3. Начальные сегменты и естественные отношения 48
3.1. Начальные сегменты с вычислимыми естественными отношениями 50
3.2. 02-начальные сегменты 68
3.3. Доказательство теоремы 3.2.1 . 71
Заключение 82
Литература
- Теория линейных порядков
- Отношения предельности
- Начальные сегменты с вычислимыми естественными отношениями
- Доказательство теоремы 3.2.1
Теория линейных порядков
Главным объектом исследований этой главы являются естественные отношения соседства , блока , плотности , предельности справа + и предельности слева - на вычислимых линейных порядках. Нашей целью будет установить алгоритмическую независимость данных отношений на вычислимых линейных порядках, то есть показать, что из вычислимости любого набора вышеприведенных отношений вычислимого линейного порядка не следует вычислимость остальных отношений из этого списка, а также получить полное описание возможных вариантов алгоритмической независимости естественных отношений на классе вычислимых представлений вычислимого линейного порядка.
Отправной точкой исследования первой главы послужил следующий фольклорный результат (см., например [21]).
Предложение 2.1.1. Существует вычислимый линейный порядок , имеющий порядковый тип , такой, что отношение невычислимо.
Так как линейный порядок упорядоченный по типу содержит один единственный предельный слева элемент, не содержит предельных элементов справа, не содержит плотных интервалов, и все его элементы содержатся в одном блоке, то из вышеприведенного факта следует
Следствие 2.1.2. Существует вычислимый линейный порядок , имеющий порядковый тип , такой, что отношение невычислимо, а отношения , , +, - вычислимы. Следующая теорема является аналогом предыдущего результата для случая отношения предельности слева Р .
Теорема 2.1.3. Существует вычислимый линейный порядок С, имеющий порядковый тип со2, такой, что отношение Р невычислимо, а отношения Sc, FJC, drtci Рс вычислимы. Более того, для каждого в.п. множества А существует линейный порядок С, имеющий порядковый тип со2, такой, что отношения S/:, FJC, drtci Р вычислимы и Р =т А.
Доказательство. Строим С в виде суммы вычислимых линейных порядков Л) + h выполнив для любого і к концу построения условие IZi : Ii = си.
Пусть {AS}SN — перечисление произвольного невычислимого в.п. множества А такое, что AQ = 0, As С As+\ и А = (J As. Построение Ik Шаг s = 0. Положим i o = {(0, к)}. Шаг s + 1. Пусть Ik,s = {io L L is}- Если к Є As+\ \ AS: то полагаем h,s+i = {{s + 1, к) L io L L s}, то есть порядок имеет вид V (s + l,k) h,s В противном случае, положим Ik,s+\ = {io L L is L (s + 1? )}, T0 есть ч_ / v k,s (s + 1, k) Построение Ik,s+i завершено. Положим Ik = [J Ik,s- Очевидно, что {//CJ/CGN равномерная последова-тельность вычислимых линейных порядков, упорядоченная по типу UJ.
Пусть С = IQ + 1\ + . Нетрудно видеть, что С — вычислимый линейный порядок, упорядоченный по типу ш2. Следовательно, отношения dric и Р — пустые множества. Отношение с вычислимо, поскольку (ж, у) Є с тогда и только тогда, когда х = (жо,Жі), у = (уо,Уі) и х\ = у\. Отношение S/: ВЫЧИСЛИМО, поскольку (ж, у) Є S/: тогда и только тогда когда либо х = (s,k), у = (s + 1, к) и к ф As+i \ AS: либо х = (s,k), у = (s + 2, к) и к Є As+i \ AS: либо х = (s + 1, к), у = (0, к) и к Є As+\ \ As для некоторых s и к. Очевидно, эти условия можно эффективно проверить. Осталось заметить, что из равенства ХА{%) = 1 — Хр-((0,ж)), очевидно вы текающего из конструкции, следует, что Р =т А. П
Так как отношения предельности слева и предельности справа симметричны, а именно, для любого линейного порядка С справедливо Р с {х) Ф P (x)Sz P/z(x) "" РЦ: (Х) Для всех xi т0 справедливо следующее
Следствие 2.1.4. Существует вычислимый линейный порядок С, имеющий порядковый тип (ш )2, такой, что отношение Р невычислимо, а отношения 3d JC, dric-, Ре вычислимы. Более того, для каждого в.п. множества А существует линейный порядок С, имеющий порядковый тип ( х )2; такой, что отношения Sc, с, dric, Р вычислимы и Р =т А.
Теорема 2.1.5. Существует вычислимый линейный порядок С, имеющий порядковый тип ( си, такой, что отношение ц невычислимо, а отношения S/:, P I dric І РС вычислимы. Более того, для каждого в.п. множества А существует линейный порядок С, имеющий порядковый тип ( си, такой, что отношения Sc} Рс dnc Рс вычислимы и с =т А. Доказательство. Как и прежде, строим С в виде суммы вычислимых линейных порядков IQ + 1\ + , выполнив теперь для любого і к концу построения условие
Отношения предельности
В этом разделе введём и изучим отношения на вычислимых линейных порядках, которые не являются алгоритмически независимыми. Эти отношения фор-мульно определимы в сигнатуре линейных порядков и естественным образом выражаются через отношения предельности справа и предельности слева.
Определение 2.2.1. Для каждого линейного порядка С = (L, L) и любого х Є L определим унарные отношения 1) Р {х) = Р {х) V Р (х); 2) Р {х) = P (x)Sz Р (х); 3) Рс (х) = Р{х) А Р {х) = (Р (х) & Р (х)) V (Р (х) & P (x)). Заметим, что вычислимость обоих отношений Р и Р необходимо влечет вычислимость Р , Р , Рс , то есть в совокупности эти отношения не являются алгоритмически независимыми. Предложение 2.2.2. Пусть С — вычислимый линейный порядок, V = {Р -, с і с і и = 1- с" Pjc}- Тогда из вычислимости любых трех различных отношений Pi, Р2 Є V и Рз Є 1Z следует вычислимость оставшихся двух отношений Р Є V и Р Є 1Z.
Доказательство следует из очевидных соотношений Р = Рс V Р , Р = Р & Р , Рс = Р & Рс і Рс = (- с ) и с" = (- с ) ) V Р . Заметим также, что из теоремы 2.1.3 непосредственно вытекает существование вычислимого линейного порядка С такого, что отношение Р невычислимо, Р = Рс = Р и {х : х Є Р } — пустое множество, то есть отношение Р вычислимо. Следовательно, имеем
Следствие 2.2.3. Существует вычислимый линейный порядок С, имеющий порядковый тип и2, такой, что Р , Рс и Р невычислимы, тогда как Р, Р вычислимы. Более того, для каждого невычислимого в.п. множества А существует вычислимый линейный порядок С, имеющий порядковый тип со2, такой, что отношения Р, Р вычислимы и А =т Р =т Рс —т Рс В силу симметричности, из следствия 2.1.2 вытекает
Следствие 2.2.4. Существует вычислимый линейный порядок С, имеющий порядковый тип {to )2, такой, что Р , Рс и Р невычислимы, тогда как Р , Р вычислимы. Более того, для каждого невычислимого в.п. множества А существует вычислимый линейный порядок С, имеющий порядковый тип (со )2, такой, что отношения Р , Р вычислимы и А =т Р =т Рс —т Рс
Комбинируя следствия 2.2.3 и 2.2.4, имеем следующее Следствие 2.2.5. Существует вычислимый линейный порядок С, имеющий порядковый тип со2 + 1 + (со )2, такой, что невычислимы, тогда как Р вычислимо. Более того, для каждого невычислимого в.п. множества А существует вычислимый линейный порядок С, имеющий порядковый тип UJ2 + 1 + (оо )2, такой, что отношение Р вычислимо и А =т Р =т Рс =т Р/2 =Т Рс Доказательство. Положим С = о+1+ъ гДе о порядок из следствия 2.2.3, а Сі — из следствия 2.2.4.
Теорема 2.2.6. Существует вычислимый линейный порядок С, имеющий порядковый тип (г) + 2) си, такой, что отношение Р , Р вычислимы, а отношения Рс , Р , Р невычислимы. Более того, для каждого в.п. множества А существует линейный порядок С, имеющий порядковый тип (г) + 2) си, такой, что отношения Р , Р вычислимы и А =т Рс =т Рс —т Р
Доказательство. Строим С в виде суммы линейных порядков IQ +1\ + так, чтобы к концу построения для любого і выполнялось условие
В противном случае, положим Isk+i,s+i = hk+i,s: hk,s+i равным уплотнению hk,s посредством N[2k] \ {\hk,s\[j\hk+i,s+i\} и hk+2,s+i — уплотнению hk+2,s
ПОСреДСТВОМ N +1 \ /3A;+2,s ДЛЯ ЛЮбьіХ Іо hk-, 4 hk+li H Є З/г+2 ПОЛОЖИМ Іо L 4 L H Построение /3jfe)S+i + hk+i,s+i + hk+2,s+i завершено.
Положим hk+hk+i+hk+2 = U hk,s + U hk+i,s+ U hk+2,s- Из конструкции следует, что Isk + hk+i + hk+2 имеет порядковый тип 77 + 2 + 77, в случае к Є А: либо порядковый ТИП 77 + 1 + 77 = 77, если к ф А.
Пусть С = IQ + 1\ + Непосредственно из конструкции следует, что отношения Р , Р вычислимы. Из равенства Хл{к) = 1 — ХрА({ 1,2/с)) = 1 — Хр&(( 1,2к)) = 1 — Хр (( 1, 2/с)) следует, что А =т Рс =т Рс —т Рс- Из симметричности отношений Р и Р вытекает
Следствие 2.2.7. Существует вычислимый линейный порядок С, имеющий порядковый тип [г] + 2) си , такой, что отношение Р , Р вычислимы, а отношения Рс , Р , Р невычислимы. Более того, для каждого в.п. множества А существует линейный порядок С, имеющий порядковый тип {J]-\-2)-UJ , такой, что отношения Р , Р вычислимы и А =т Рс =т Рс =т Рс
Теперь справедливо Следствие 2.2.8. Существует вычислимый линейный порядок С, имеющий порядковый тип (77+2)-бо +1+(т7+2)-бо ; такой, что отношение Р вычислимы, а отношения невычислимы. Более того, для каждого в.п. множества А существует линейный порядок С, имеющий порядковый тип (г) + 2) со + 1 + (77 + 2) со , такой, что отношение Р вычислимо и А =т Рс =т i =т Рс =Т P/z Доказательство. Положим С = o + l + i, где Со — порядок из теоремы 2.2.6, а Сі — из следствия 2.2.7. Более того, теорема 2.2.6 и следствие 2.2.3 позволяют установить
Следствие 2.2.9. Существует вычислимый линейный порядок С, имеющий порядковый тип (г] + 2) со + 1 + со2, такой, что отношение Р вычислимо, а отношения Рс , Р , Р , Р невычислимы. Более того, для каждого в.п. множества А существует линейный порядок С, имеющий порядковый тип (г) + 2) со + 1 + со2, такой, что отношение Р вычислимо и А =т Р =т Р =т Р =т Р .
Доказательство. Положим С = Со + 1 + С\, где Со — порядок из теоремы 2.2.6, а С\ — из следствия 2.2.3. Аналогично, следствие 2.2.4 и следствие 2.2.7 позволяют установить Следствие 2.2.10. Существует вычислимый линейный порядок С, имеющий порядковый тип (со )2 + 1 + (г) + 2) со , такой, что отношение Р вычислимо, а отношения Рс , Р , Р , Р невычислимы. Более того, для каждого в.п. множества А существует линейный порядок С, имеющий порядковый тип (со )2 + 1 + (г) + 2) со , такой, что отношение Р вычислимо и А =т Р =т Р =т Р =т Р.
Начальные сегменты с вычислимыми естественными отношениями
Таким образом, повторяя построение в случаи отношения плотности в предло жении 2.3.1, получим 0/-вычислимое представление порядка , что и требова лась доказать. Следствие 2.3.10. Существует линейный порядок С такой, что отношения соседства Sc, блока Fc, предельности слева Р и справа Р вычислимы, а отношение плотности dn невычислимо ни в какой его вычислимой копии С.
Доказательство. Пусть Л — произвольный 0/-вычислпмый линейный порядок, не имеющий вычислимого представления. Согласно теореме 2.3.9, линейный порядок (( + 1)- + 7 + ( + 1)-)-.А имеет вычислимое представление С с вычислимым отношение соседства Sc, блока Fc, предельности слева Р и справа Р. Предположим, что отношение плотности dri вычислимо для некоторого вычислимого представления С = (L, ) порядка С Повторяя построение из предложения 2.3.1 для случая отношения плотности, получим вычислимое представление порядка А, что противоречит выбору Л. Комбинируя полученные результаты, удается получить полное описание возможных вариантов алгоритмической независимости естественных отношений на вычислимых представлениях линейных порядков.
Следствие 2.3.11. Пусть V = {S, F, dn, Р , Р+}- Тогда для любых Vi, V2 С V таких, что V\ (J V2 = V, V\ f] V2 = 0 и S Є V\ влечет F Є V\, существует линейный порядок С такой, что все отношения из V2 вычислимы, а все отношения из V\ невычислимы ни в какой его вычислимой копии С.
Доказательство. Без ограничения общности предположим, что V\ = {S, F, Р+} и V2 = V \ V\. Пусть С\и С-2 — линейные порядки из предложения 2.3.4 и следствия 2.3.8, соответственно. Очевидно, что линейный порядок С = С\ + 1 + С-2 является искомым. Глава 3 Начальные сегменты и естественные отношения В этой главе изучаются вопросы конструктивизируемости начального сегмента вычислимого линейного порядка с добавленными отношениями плотности dn, предельности справа Р+ и предельности слева Р . Другими словами, рассматриваются структуры (L, , dnc), (L, , Р) и (L, , Р ), где С = (L, с) — линейный порядок. Начальный сегмент порядка L с индуцированным отношением соседства или отношением блока будет называться начальным сегментом структур (L, , dnc), (L, , Р) и (L, , Р ), соответственно. Таким образом, начальный сегмент данных структур будет иметь ту же сигнатуру.
Одной из фундаментальных задач теории вычислимых моделей является проблема эффективизация структуры, то есть построения её вычислимой копии, или доказательство несуществования подобного конструктивного представления. К примеру, Дж. Найт и М. Стоб [41] показали, что каждая -низкая булева алгебра имеет вычислимое представление, что обобщает известные ранее результаты Р. Доуни и К. Джокуша[23] и Дж. Тёрбера[46] о вычислимой представимости каждой низкой и 2-низкой булевых алгебр, соответственно. А. Н. Фролов [13] показал, что каждый низкий k-дискретный линейный порядок имеет вычислимое представление, с другой стороны, он построил [31] пример 2-низкого разреженного линейного порядка, не имеющего вычислимой копии, что дает отрицательный ответ на вопрос Э. Кэча и А. Монталбана[35]. Результаты Л. Фейнера[28] и К. Джокуша и Р. Соара[34] о существовании в.п. булевой алгебры и низкого линейного порядка, не имеющих вычислимых представлений, соответственно, являются примерами неконструктивизируемых моделей классических алгебраических структур.
Изучение конструтивизируемости начального сегмента вычислимого линейного порядка берет начало с работы М. Роу[43], который показал, что каж дый Iq-начальный сегмент вычислимого линейного порядка имеет вычислимое представление. С другой стороны, он построил вычислимый линейный порядок с неконструктивизируемым ПЦ-начальным сегментом. Р. Коулз, P. Доуни и Б. Хусаинов [19], используя метод приоритета с бесконечными нарушениями, показали, что существует вычислимый линейный порядок с П -начальным сегментом не изоморфным никакому вычислимому линейному порядку. Наконец, в совместной работе К. Амбос - Шпис, С. Б. Купер и С. Лемпп [15] установили, противоположно результату Р. Коулза, P. Доуни и Б. Хусаинова, что каждый 1]2-начальный сегмент любого вычислимого линейного порядка имеет вычислимую копию.
М. Зубков [4] исследовал отношения соседства и блока на начальных сегментах вычислимых линейных порядков, что позволило ему получить более простое доказательство результата Коулза-Доуни-Хусаинова. Для этого им были построены вычислимые структуры (L, , SJC) и (L, , FJC), содержащие неконструктивизируемые П -начальные сегменты. В первом параграфе рассмотрены случаи для оставшихся естественных отношений на линейных порядках, а именно, отношений плотности dn, предельности справа Р+ и предельности слева Р . Доказано существование таких вычислимых структур (L, , dric), (L, , Р) и (L, , Р ), что их П -начальные сегменты неизоморфны никаким вычислимым линейным порядкам с вычислимыми отношениями плотности, предельности справа и предельности слева, соответственно. В заключительном параграфе главы, в дополнении к результату К. Амбос - Шписа, С. Б. Купера и С. Лемппа [15], доказано, что каждый вычислимый линейный порядок без наибольшего элемента является И-начальным сегментом наперед заданной Е -степени некоторого вычислимого линейного порядка.
Доказательство теоремы 3.2.1
Допустим, что для некоторого х утверждение (3.14) не выполнено. Пусть х — наименьшее из таких чисел. Покажем, что в этом случае множество М вычислимо, то есть существует эффективная процедура определения принадлежности элемента п множеству М. Доказательство проведем индукцией по п. Если п = 0 и Ш0 ж, то ггщ ф А, иначе выполнена левая часть дизъюнкции (3.14), что невозможно в силу выбора х. Таким образом, в силу леммы 3.3.7, 0 ф М. Если ггщ ж, то ггщ Є А, иначе выполнена правая часть дизъюнкции (3.14). Следовательно, по лемме 3.3.7, О Є М. Предположим, что М \ п определено. Пусть, к примеру, имеет место [М \ п] 1 = а С (3. Выберем шаг и s такой, что гаа-\ и х принадлежат Lu. Если х ma i, то та \ ф А, иначе выполнена левая часть дизъюнкции (3.14), что невозможно, в силу выбора х. По лемме 3.3.7 имеем, что п ф М. Если же та \ ж, то та \ Є А, то есть п Є М. Следовательно, М вычислимо. Таким образом, для любого х выполнено соотношение (3.14). Если, к примеру, выполнена левая часть дизъюнкции (3.14), то есть lh(a) Є М и х та, тогда, в силу леммы 3.3.7, та Є А и х Є А. Рассуждая аналогично для случая, когда выполнена правая часть дизъюнкции, заключаем, что х ф А. Заметим, что из леммы 3.3.5 следует, что одновременно обе части дизъюнкции выполнены быть не могут. Лемма 3.3.10. А =т М. Доказательство непосредственно вытекает из лемм 3.3.8 и 3.3.9. Лемма 3.3.11. А = С
Доказательство. Покажем, что Ф = (J Ф3 осуществляет необходимое соответ s ствие. Непосредственно из определения 3.3.2 следует, что каждое Ф8, определенное к концу подшага 5, сохраняет порядок при отображение AS, определенного к концу подшага 2, на Ls. Из определения 3.3.2 и описания подшага 3 следует, что если Ф8{х) -J, и х Є As+i к концу подшага 2, то Ф8+і(ж) -1= Ф3(х) -J, к концу подшага 3 шага s +1 и, следовательно, к концу шага s +1. Таким образом, если х Є А и s наименьшей шаг такой, что для любого шага , большего s, выполнено х Є At, то Ф +і(ж) \= I для некоторого / Є Lt+i и для всех шагов и t + 1 верно, что Фи(х) -1= I. Следовательно, отображение Ф корректно определяет вложение порядка А в С.
Пусть теперь / \ Ls произвольно. На подшаге 3 в As+\ перечисляется необходимое количество элементов для определения Ф8+і так, что для некоторого х Є As+i выполнено Ф8+і(ж) -1= I. Пусть В = {у х\ у = та для некоторой вершины а}.
Если В пусто, то Фи(х) -1= I для всех шагов и s. Поскольку единственным возможным случаем смены а-метки элемента х на последующих шагах и s+1, а значит и Фи(х) t, является наличие такого шага t и такой вершины а С jt, что на подшаге 2 шага t имеет место подслучай І, то есть та помечено а-меткой и lh(a) ф Mt. Очевидно, что Фи(х) -1= /, где и s, верно и в случае, если В не пусто и для любого элемента из Ъ Є В = Ъ Є At для всех t s. Пусть теперь В не пусто и а — самая левая вершина такая, что свидетель та Є В и существует шаг -и, являющийся а-шагом, такой, что lh(a) ф MV, та помечен а-меткой и имеет место подслучай 1. Пусть q s + 1 — наименьший такой а-шаг. Пусть Фд(Ь) -1= V І = Ф8+і(ж) -1= Фч{х ) \. для некоторых / и х . Тогда на подшаге 2 шага q + 1 все элементы большие или равные Ь сменят а-метки на ту-метки. Причем, согласно подшагу 5, для всех элементов /" Є Lq+\ больших или равных V верно, что Фч+\{у) ]= I" для некоторых у Є Aq+i, которые не являются свидетелями никаких стратегий и, в силу выбора 6, для всех таких /" и у выполнено равенство Ф(у) -1= I. Лемма 3.3.12. С = С + г). Доказательство. Непосредственно из построения вытекает, что С = Л+Е. Более того, в силу действий предпринимаемых на подшаге 6, к концу построения 8 = г]. Из леммы 3.3.11 имеем необходимое С = С + ц.
В диссертационной работе исследовалась алгоритмическая зависимость естественных отношений соседства S, блока F, плотности dn, предельности справа Р+ и предельности слева Р на вычислимом линейном порядке и на вычислимых представлениях линейных порядков. Получены следующие основные результаты:
1. построена серия вычислимых линейных порядков, демонстрирующая независимость естественных отношений соседства S, блока F, плотности dn, предельности справа Р+ и предельности слева Р на вычислимых линейных порядках;
2. получено описание алгоритмической зависимости естественных отношений соседства S, блока F, плотности dn, предельности справа Р+ и предельности слева Р на вычислимых представлениях линейных порядков, а именно, доказано, что нет других зависимостей, кроме той, которую установил М. Мозес [37]. Для этого были построены следующие варианты 0/-кодировок линейных порядков: линейный порядок С имеет 0 -вычислимое представление тогда и только тогда, когда: (1) линейный порядок ((( + 1) ( + г] + (( + 1) () С имеет вычислимое представление С с вычислимыми отношениями соседства S блока F, предельности слева Р и справа Р ; (2) линейный порядок ((2 -\-ш + (2) С имеет вычислимое представление С с вычислимыми отношениями соседства 5 и блока F аналогично, (3) линейный порядок ((2 + UJ + (2) С имеет вычислимое представление С с вычислимыми отношениями соседства 5 и блока F . Также в работе изучалась алгоритмическая сложность начальных сегментов вычислимых линейных порядков с добавленными естественными отношениями и начальных сегментов, принадлежащих арифметическому уровню сложности иерархии множеств. В данном направлении получены следующие основные результаты:
1. построены вычислимые линейные порядки с добавленными отношениями плотности, предельности справа + и предельности слева -, соответственно, такие, что их 01-начальные сегменты не имеют вычислимых представлений с вычислимыми отношениями плотности , предельности справа + и предельности слева -;
2. доказано, что каждый вычислимый линейный порядок без наибольшего элемента является 02-начальным сегментом наперед заданной 02-степени некоторого вычислимого линейного порядка..
Результаты диссертационного исследования могут найти применение в учебном процессе при преподавании спецкурсов по теории вычислимых моделей и теории счетных линейных порядков, при написании курсовых и дипломных работ по соответствующей тематике, при организации самостоятельной работы студентов, магистрантов и аспирантов.