Счетные линейные порядки и их алгоритмическая сложность

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

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

Глава 1. Спектр отношения соседства

1.1. Замкнутость наверх в классе перечислимых степеней

1.2. ДфСпектры отношения соседства, образующие конусы

1.3. ДСпектры отношения соседства, содержащие

Глава 2. Низкие линейные порядки

2.1. Описание низких представлений

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

2.3. г/ Схожие линейные порядки

2.4. Оценки изоморфизмов

Глава 3. 2-Низкие линейные порядки порядки
3.1. Описание 2-иизких представлений
3.2. 1-Квазидискретные линейные порядки
3.3. Разреженные линейные порядки и контрпримеры
Глава 4. Спектры и До-спектры линейных порядков
4.1. Спектры линейных порядков
4.2. Дфспектры линейных порядков
4.3. Кодирующие теоремы. О'-Кодирование
4.4. (У'-Кодирующие теоремы
Литература

Введение
Данная работа посвящена изучению алгоритмических свойств счетных линейных порядков на основе построения эффективных представлений этих структур на множестве натуральных чисел. Это направление исследований находится на стыке теории вычислимости и теории счетных линейных порядков. Счетные линейные порядки твердо заняли свое место в теории моделей — каждая счетная булева алгебра порождается некоторым счетным линейным порядком, а в теории групп особое место занимает направление исследований упорядоченных групп и прочее.
Основы теории вычислимых алгебраических структур и их моделей были заложены в работах 50-х годов прошлого века П.С. Новикова [5|, О. Рябина ]47|, А. Фролиха и Дж. Шсфердсопа |27], Р. Воота [56], А.И. Мальцева [3] и [4] и с тех пор активно развивается. В качестве наиболее важных и современных источников можно указать книги С.С. Гончарова и Ю.Л. Ершова |2| и Дж.Пайт и К. Эша [11], а также большую обзорную работу 2007 года
С.С. Гончарова [28].
Исследования в области вычислимых линейных порядков были начаты почти одновременно с зарождением теории вычислимых структур с работы 1956 года X. Райса [49], были продолжены в работах Д. Янга |59|, Л. Фейпера [23] и |24], Р. Соара [53], М. Перетятькипа [6], А. Пииуса [7], С. Фелнера [25] и с тех пор прочно заняли свое место в теории вычислимых структур. Так, парубеже веков выходит в свет обзорная работа Р. Доуни и Дж. Реммела [22] охватывающая все актуальные направления исследований и важные открытые вопросы в теории вычислимых структур, где теории вычислимых линейных посвящен отдельный раздел. В этом направлении наиболее важными и современными источниками являются книга Дж. Розсиштейна [51] и обзорные работы Р. Доуни [16] и 115].

Все исследования в области вычислимых линейных порядков (и вычислимых алгебраических структур, в общем) можно условно разделить па три основных направления:
I. Исследование свойств вычислимых линейных порядков;
II. Описание достаточных (и необходимых) условий вычислимой представимости линейных порядков;
III. Описание спектров линейных порядков (то есть описание класса степеней и редставлений).
В представленной диссертации получены результаты по всем этим трем направлениям. Опишем их более подробно.
I) Исследование свойств вычислимых линейных порядков направлено на такие вопросы, как описание эффективной категоричности, разрешимости и п-разрешимости вычислимых линейных порядков, описание эффективных свойств отношений на них. Проще говоря, в этом направлении исследуются вычислимые линейные порядки на предмет дополнительных алгоритмических свойств.
С.С. Гончаровым и В.Д. Дзгоевым [1] и, независимо, Дж. Реммслом [48] было получено описание вычислимо категоричных вычислимых линейных порядков. (Вычислимый линейный порядок называется вычислимо категоричным, если любое его вычислимое представление ему вычислимо изоморфно.) А именно, ими было показано, что вычислимый линейный порядок является вычислимо категоричным тогда и только тогда, когда он содержит только лишь конечное число пар соседних элементов. (Два элемента линейного порядка называются парой соседних элементов, если между ними нет никакого другого элемента.) Другими словами, вычислимый линейный порядок является вычислимо категоричным тогда и только тогда, когда его можно представить в виде конечной суммы интервалов, каждый из которых имеет тип п

Осталось рассмотреть случай, когда множество С является вычислимым. Для этого покажем, что ВуврДЗисс) = Еф Пусть А является перечислимым множеством и {Ав}кМ есть его эффективное перечисление, то есть вычислимая последовательность конечных множеств такая, что Л6. С Дч+(,
А = и Ля, А) — 0 и |А,ц — Л.,1 = 1. Положим 0 <£, 2 <£, 4 <£ , а ггакже »ем
положим 2п <ь 2в + I <л 2п + 2 тогда и только тогда, когда п £ Ля.| I — Ля. Пе трудно понять, ч'1'О (М, <£) является вычислимым линейным порядком, (М, <л) — ш и Биссу, =т Л. Таким образом, ВдБрДБисс) = {Ь £ Е” | 0 < Ь} = Е?. □
Определение 1.1.7. Вычислимый линейный порядок называется с{-категоричным, если любое его вычислимое представление ему также и с{-вычислимо изоморфно.
Определение 1.1.8. Вычислимый линейный порядок называется относительно О1 -категоричным,, если любое его .-вычислимое представление является ему х'-вычислимо изоморфной.
Определение 1.1.9. Степенью категоричности вычислимого линейного порядка называется наименьшая степень Л (если :такая существует), что структура является Л-вычислимо категоричной.
Следствие 1.1.10. Степенями категоричности относительно 0'-вычислимо категоричного линейного порядка могут быть только лишь 0 и 0'.
Доказательство. Ч. МакКой [38] получил описание относительно О'-вычис-лимо категоричных линейных порядков. А именно, вычислимый линейный порядок является относительно О'-вычислимо категоричным тогда и только тогда, когда его можно представить в виде конечной суммы интервалов, каждый! из которых имеет тип п, ш. и>*, С или п 11, где каждый интервал п ?/ имеет наибольший и наименьший элементы.