Вычислимые линейные порядки и естественные отношения на них

• Автор: Бикмухаметов, Равиль Ильдарович
• Шифр специальности: 01.01.06
• Научная степень: Кандидатская
• Год защиты: 2014
• Место защиты: Казань
• Количество страниц: 89 с. : ил.

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

Глава 1. Основные определения и обозначения

§1.1. Теория вычислимости

§1.2. Теория линейных порядков

Глава 2. Естественные отношения на вычислимых линейных порядках

§2.1. Естественные отношения

§2.2. Отношения предельности

§2.3. Алгоритмическая независимость естественных отношений

Глава 3. Начальные сегменты и естественные отношения

§3.1. Начальные сегменты с вычислимыми естественными отношениями

§3.2. Е^-начальные сегменты
§3.3. Доказательство теоремы 3.2.
Заключение
Литература

Введение
Актуальность темы исследования. Данная работа посвящена изучению алгоритмической сложности естественных отношений на линейных порядках.
Более обще, теория вычислимых моделей занимается изучением вопросов эффективности алгебраических структур и моделей. История изучения подобных структур обширна и берет начало с работ Д. Гильберта и М. Дена. Отечественные исследования в этом направление и становление вычислимой теории моделей как самостоятельного направления современной математической логики обязаны трудам выдающегося математика академика А. И. Мальцева [5], [6]. Одним таким классическим примером изучаемым в рамках этой теории являются вычислимые линейные порядки. Вычислимые линейные порядки широко исследовались многими авторами такими, как Р. Ганди [32], Р. Доуни [21, 22], Р. Доуни и Дж. Найт [25], Р. Доуни и М. Мозес [24], М. Мозес [37-39] X. Райс [42], Л. Фейнер [27, 29], А. Н. Фролов [9-13, 30], Дж. Харрисон [33], Чен [17], Дж. Чи-шолм и М. Мозес [18], К. Эш [16] и др.
На протяжение истории изучения линейных порядков формировался круг наиболее естественных отношений на них, а именно, отношения соседства 5, блока Г1, плотности йп, предельности справа Р+, предельности слева Р~. Данные отношения исследовались многими авторами при изучении линейных порядков, их структурных свойств и классификации. М. Мозес [37, 38] показал, что линейный порядок имеет 1-разрешимое представление тогда и только тогда, когда он имеет вычислимое представление с вычислимым отношением соседства. С. С. Гончаров и В. Д. Дзгоев[3] и Дж. Реммел [44] показали, что вычислимый линейный порядок является вычислимо категоричным тогда и только тогда, когда он имеет только лишь конечное число соседних элементов. А. Фролов [13] показал, что линейный порядок является низким тогда и только тогда, когда он имеет 0'-вычислимое представление с 0/-вычислимым отношением со-

седства. Г. Ву, Р. Доуни, Ш. Лемпп [26] и А. Фролов [9] в совокупности показали, что спектр отношения соседства либо тривиален, либо замкнут наверх в в.п. степенях.
Отношение блока исследовались, например, в работах М. Мозеса [37, 38], где было показано, что отношение блока вычислимо категоричного 1-разрешимого линейного порядка является вычислимым. Введенные выше отношения использовались в работе Дж. Тёрбера[46], который исследовал 2-низкие булевы алгебры, порожденные линейными порядками. Также данные отношения использовались в работе П. Е. Алаева, Дж. Тёрбера, А. Н. Фролова [1] для исследования 2-низких квазидискретных линейных порядков. М. Зубков [4] исследовал отношения соседства и блока на начальных сегментах вычислимых линейных порядков, что позволило ему получить более простое доказательство теоремы Коулза-Доуни-Хусайнова [19] о существовании вычислимого линейного порядка с неконструктивизируемым П^-начальным сегментом. Отношения соседства, предельности справа и предельности слева использовались в работе А. Фролова [30] для описания 2-низких линейных порядков. А именно, им было показано, что 0"-вычислимость структуры (К, <£, Дс, С^с, Р£, ), где С = (М, <с)
— линейный порядок, влечёт существование 2-низкого представления порядка С. Этот результат для специальных классов линейных порядков имеет более простой вид: если С = (М, <с) — дискретный или разреженный линейный порядок, то 0"-вычислимость структуры (М, <£, Дщ Дс, Р£, РД) влечет существование 2-низкого представления порядка С. Если же С = (К, <с) — квазидискретный линейный порядок, то из 0"-вычислимости структуры (М, <щ Дщ Дс, (1пс, Р£■ ДД) следует, что С имеет 2-низкое представление. Изучению арифметической сложности всех введенных выше отношений также посвящена недавняя магистерская работа У. П. Тёрнера [47]. Из последних результатов видно, что отношения соседства Д, блока Д, плотности йп, предельности справа Р+, предельности слева Р~ играют важную роль в иссле-
|/5*+1,5+11 У |/5*М-2,з|}, Ьк+г,в+1 = Ьк+3,я, & 1ьк+4,з+1 ~ уПЛОТНвНИЮ /5*1+4,я ПОСреД-СТВОМ М[2А:+11 {|/5*+з,8+1| и |/5*+4,я|}-
В противном случае, положим /5*1,5+! равным уплотнению /5*,.5 посредством МИ{|/5м1и1^+1,8|}, кк+1 ,5+1 — /5*1+1,я — {(1, 2А:)}, /5*1+2,в+1 — 1$к+2,я = 0, /5*+з,я+1 = кк+ъ,8 = {<1,2/с + 1)}, а /5^+4,5+1 — уплотнению 15к+4,5 посредством
ИР*+11 {|/5*+з ,51 и |/б*+4,в I }•
Для любых г0 £ /5*, к £ /5*1+1, к £ /5*1+2, к 6 /5*1+3, Ч е Д*+4 положим го <ь гг <ь к <ь к <х Ч-
Построение /5*1,3+! + /5*1+1.в+1 ~Ь /б*+2,5+1 “Ь /5*+з,я+1 /5*+4,5+1 завершено.
Положим
/5* + /б*+1 + /5*+2 + /з*+3 + Д*+4 = и ^ък'3 + и /5*1+1,3 +
век ябМ
/5*+2,в + и /5*+3,5 + и /5*+4,я
8eN ЗбК яеК
Из построения следует, что /5* + /5*,+1 + /5*1+2 + /5*1+3 + /5*1+4 имеет либо порядковый ТИП 77 + 2 + 77 + 2+?7, если к £ Л, либо порядковый ТИП 7-7 + 2 + 77, если к <£ А.
Пусть С = /о + 1 + ' ■ • ■ Отношение Р£ ВЫЧИСЛИМО, поскольку Р/-(х) = 1 ДЛЯ всех X. Отношение +£ вычислимо, поскольку X ^ Р^ 4=* х = (у, 2к) и X £ кк+1-Х ИЛИ X = (у, 2к + 1) и X £ кк+3,х ДЛЯ некоторых у и /с. Отношение Р^ также вычислимо, поскольку х £ Рх ф Р^. Из равенства хл{к) = 1 ~ Хрс-(( 1, Щ) = 1 - Хр+(( П 2/с + 1)) следует, что Л =т Р£ =т Р£. □
Исключая тривиальные случаи, а также случаи, возможность которых исключается вышеприведенными фактами и случаи, справедливость которых следует из симметричности отношений Р+ и Р~. имеем следующее