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

Одной из важных задач в теории алгоритмов является изучение алгоритмической сложности различных счетных алгебраических структур на основе построения эффективных представлений этих структур на множестве натуральных чисел. В данной работе мы исследуем такие алгебраические структуры, как линейные порядки и алгебры Ершова.

Исследования в этой области были начаты JI. Фейнером в конце 1960;х и продолжены в работах Дж. Реммела, С. С. Гончарова, Дж. Найт, К. Эша и других. В частности, было показано, что существуют вычислимо перечислимые булева алгебра и линейный порядок, не имеющие вычислимые изоморфные копии (см. [1] и [2]), другими словами, являющиеся неконструк-тивизируемыми.

В последние года активно изучаются такие вопросы, как описание спектра счетных алгебраических структур. Например, Т. Сламан (см. [3]) и С. Вей-нер (см. [4]) независимо друг от друга построили такую счетную структуру А, что Spec (A) — D — {0}, где D — класс всех тьюринговых степеней. Р. Миллер в [5] доказал, что существует такой линейный порядок L, что Spec (L) П = Д° — {0}. С. Гончаров, В. Харизанов, Дж. Найт, К. МакКой, Р. Миллер и Р. Соломон в [6] построили для любого п € ш такую структуру An, что Spec (An) = D — Ln, где Ln — класс всех п-низких степеней.

В этой работе мы докажем, что для любого п 6 ш существует такой линейный порядок Сп, что Spec (?n) П = А° — L".

В [7] Р. Доуни и М. Мозес показали, что любой дискретный линейный порядок низкой степени имеет вычислимую копию. Мы обобщим этот результат, доказав, что каждый 2-низкий квазидискретный (и, следовательно, дискретный) линейный порядок изоморфен вычислимому порядку. Причем, покажем, что для 3-низких квазидискретных порядков этот результат не верен.

Также Р. Доуни спросил, какие еще существуют свойства линейных порядков Р, что для любого низкого линейного порядка L из P (L) следует существование вычислимой копии. В этом направлении мы докажем, что каждый низкий линейный порядок, «сильно похожий» на ?/, изоморфен вычислимому порядку (причем для 2-низких это не верно).

Отечественными и зарубежными учеными активно исследуется также вопрос о та-низких булевых алгебрах и алгебрах Ершова. В [1] JI. Фейнер построил вычислимо перечислимую булеву алгебру, не изоморфную никакой вычислимой алгебре. Построенная им булева алгебра не изоморфна никакой n-низкой алгебре, ни для какого натурального п. Естественно возникает вопрос: каждая ли та-низкая (для любого п € ш) булева алгебра имеет вычислимую копию? Постановку этого вопроса можно найти, например, в [8].

В общем случае ответ на этот вопрос пока неизвестен, известны частичные ответы. В [9] Р. Доуни и К. Джокуш доказали, что каждая низкая булева алгебра изоморфна вычислимой алгебре. В [8] Дж. Найт и М. Стоб доказали, что любая 4-низкая булева алгебра имеет вычислимую копию. В этой работе мы покажем, что каждая 3-низкая алгебра Ершова изоморфна вычислимой алгебре.

В теории вычислимости особое место занимают исследования теоретико-множественных свойств различных структур, особенно теоретико-множественные свойства класса вычислимо перечислимых множеств относительно вычислимых множеств.

В третьей главе данной работы изучается теоретико-множественная структура класса вычислимых множеств относительно полиномиально вычислимых и примитивно рекурсивных. В этой главе вводится классификация вычислимых множеств и доказывается, что каждый класс введенной классификации не пуст.

В третьей главе вводятся и изучаются две так называемые теоретико-множественные сводимости. Доказаны теоремы о нормальной форме для каждой сводимости, критерии минимальности и плотности. Используя критерий плотности, на классе вычислимых множеств доказано, что первая введенная теоретико-множественная сводимость порождает плотный частичный порядок.

При доказательстве теорем диссертации использовались методы конечных расширений, приоритета с конечными нарушениями (метод 0'-приоритета), приоритета с бесконечными нарушениями (метод 0″ -приоритета). Например, теоремы 3.1.5, 3.3.11 доказывались методом конечных расширений, теорема 2.1.2 — методом приоритета с конечными нарушениями, а теорема 1.2.3 — методом приоритета с бесконечными нарушениями.

Содержание диссертации представлено в собственных публикациях автора [11] — [24]. Результаты, изложенные в данной работе, докладывались на международных конференциях «Logic Colloquium'2001» (Вена, Австрия, август 2001 г.), «Logic Colloquium'2002» (Мюнстер, Германия, август 2002 г.), «Колмогоров и современная математика» (Москва, апрель 2003 г.), «Logic Colloquium'2003» (Хельсинки, Финляндия, август 2003 г.), «Мальцевские чтения» (Новосибирск, 2003 г.), «Logic Colloquium'2004» (Турин, Италия, июль 2004 г.), а также на научных семинарахпо математической логике в Казанском государственном университете.

Автор выражает глубокую признательность своему научному руководителю профессору Арсланову Марату Мирзаевичу за постановку задач, интерес к исследованиям автора и поддержку в работе.

В изложении теории вычислимости (теории алгоритмов) мы следуем в основном [10], в изложении теории счетных булевых алгебр, алгебр Ершова и линейных порядков — [25].

Ниже содержатся основные определения и обозначения, необходимые для дальнейшего изложения.

Обозначения и терминология.

Теория вычислимости. Через ш обозначается множество всех натуральных чисел с 0.

Функция (ж, у) = (ж2 + 2ху 4- у2 + Зж + у)/2 — стандартная вычислимая биекция из и> • ш в ш.

Теоретико-множественную разность множеств X С ш и Y С ш будем обозначать через X—Y] дополнение множества X С. ш — через X =dfn ш—Х.

Мы будем иногда отождествлять множество, А Cw с его характеристической функцией.

Г 1, если ж 6 А, Хл (х) = < 0, в противном случае, так что запись А (х) — 1 означает, что х 6 А, а А{ж) = 0 эквивалентно х? А.

Запись X =* Y означает, что симметрическая разность (X — У) и (У — X) конечна.

Будем писать, А С* В, если А— В конечно. Пишем, А Соо В, если, А С.* В и В%* А.

Тьюринговые степени будем обозначать жирными строчными латинскими буквами а, b, ., тьюринговую степень множества, А обозначаем через deg (A).

Если / — некоторая функция, то dom (f) — область ее определения, rang (f) — область ее значений, graph (f) — график функции /: graph (f) = {(ж, у) | у = /(ж)}.

Если последовательность функций /я: о> —и> поточечно сходится к функции /, то будем писать / = lims f3.

Функция называется примитивно рекурсивной, если она принадлежит наименьшему классу, содержащему функции 0(х) = 0, s (x) =dfn жf- 1, /£(ж1,., жп) —dfn хт и замкнутому относительно суперпозиции и примитивной рекурсии.

Функция называется вычислимой (частично вычислимой), если существует машина Тьюринга, вычисляющая эту функцию.

Функция называется полиномиально вычислимой, если она вычислима на машине Тьюринга за количество шагов, ограниченное некоторым наперед заданным полиномом.

Множество называется полиномиально вычислимым, примитивно рекурсивным, вычислимым, если его характеристическая функция является полиномиально вычислимой, примитивно рекурсивной или вычислимой, соответственно.

Множество называется вычислимо перечислимым, если оно является областью определения некоторой частично вычислимой функции. ф£ — одноместная частично вычислимая функция, вычислимая на машине Тьюринга с оракулом, А с гёделевым номером еби.

Для каждого е полагаем W^ —dfn <1от (ф?).

Оператором скачка множества, А является А' — {е | е? Wj1}. По индукции можем определить n-ый скачек множества A: = (А^)'.

Для № G w множество, А <т 0' называется? г-низким (или та-высоким), если <т (или 0(n+1) <т А'" ', соответственно). Тьюринговая степень, а называется га-низкой или та-высокой, если некоторое множество, А? а является п-низким или п-высоким, соответственно. 1-низкое (1-высокое) множество или степень называется просто низким (высоким, соответственно).

Булевы алгебры, алгебры Ершова, линейные порядки и их тью-ринговы степени.

Алгеброй Ершова называется дистрибутивная решетка с относительными дополнениями, имеющая наименьший элемент. Булевой алгеброй называется дистрибутивная решетка с относительными дополнениями, имеющая наименьший и наибольшие элементы.

Идеалом Фреше булевой алгебры V называется идеал Т{ТУ) = {а <Е Т> Вах,., ап, где а- — атом или нуль, 1 < i < га}.

Под понятием решетки множеств понимается класс множеств V С V (u) — {А | А С о-}, замкнутый относительно операций объединения и пересечения (то есть A U В, Л П В? Р для любых множеств А, В G Т>).

Решеткой множеств с наименьшим (с наибольшим) элементом назовем решетку множеств Т>, если 0 € Т> (или ш G Т>, соответственно).

Под алгеброй множеств понимается решетка множеств с наименьшим и наибольшим элементами, замкнутая относительно операции теоретико-множественной разности (то есть, А — В € Z? для любых А, В € Т>).

Автоморфизмом алгебры множеств, А называется такая биекция <р: А —> Л, что для любых А, В е A.

(АГВ).

Степень структуры В, обозначается deg (#), — это тьюринговая степень ее атомной диаграммы, закодированной геделевскои нумерацией как подмножество ш. Если сигнатура структуры В конечна, то тьюринговой степенью В является deg (0) = deg (|B|) V (V?=0 deg (/-)) V (V?0 deg (Pi)), где B — основное множество, {fi}i.

Мы рассматриваем только счетные структуры, основным множеством которых является и).

Спектром структуры Л называется класс Spec (A) = {deg (B) | В = Л}.

Если С — некоторый класс степеней, то С-спектром называется класс Spec0(Л) = С nSpec (A).

Мы будем рассматривать толькоспектры счетных линейных порядков, то есть С = Ag — класс всех таких степеней а, что, а <т О', где О — степень вычислимых множеств.

Мы будем говорить, что структура Л вычислима (n-низкой степени или п-высокой степени), если его степень deg (A) вычислима (n-низкая или п-высокая, соответственно).

1. L.J. Feiner Hierarchies of Boolean algebras / / The Journal of Symbolic Logic, 35, 1970, 365 — 373.

2. L.J. Feiner Orderings and Boolean algebras not isomorphic to recursive one II PhD. thesis, MIT, 1967.

3. T. Slaman, Relative to any nonrecursive set // Proceedings of the American Mathematical Society, 126, 1998, 2117 2122.

4. S. Wehner, Enumeration, countable structure and Turing degrees // Proceedings of the American Mathematical Society, 126, 1998, 2131 2139.

5. R. Miller, The spectrum of a linear ordering // The Journal of Symbolic Logic, 66, 2001, 470 486.

6. S.S. Goncharov, V.S. Harizanov, J.F. Knight, C. McCoy, R. Miller, R. Solomon, Enumerations in computable structure theory //в печати.

7. R.G. Downey and M.F. Moses, On choice sets and strongly nontrivial self-embeddings of recursive linear orderings // Z. Math. Logik Grunall. Math., 35, 1989, 237 246.

8. J.F. Knight and M. Stob Computable Boolean algebras, The Journal of Symbolic Logic, 65, 2000, No 4, 1605 1623.

9. R.G. Downey and C.G. Jockusch, Every low Boolean algebra is isomorphic to a recursive one / / Proceedings of the American Mathematical Society, 122, 1994, No 3, 871 880.

10. R.I. Soaxe Recursively enumerable sets and degrees, Heidelberg: Springer-Verlag, 1987 (см. русский перевод: Coap P. И. Вычислимо перечислимые множества и степени Казань: Казанское мат. общество, 2000, 576 с.).

11. А. Н. Фролов Теоретико-множественная структура вычислимых множеств // Известии вузов. Математика, 2003, 10 (497), 70 76.

12. А. Н. Фролов Теоретико-множественные сводимости по решетке множеств // Известии вузов. Математика, принята к печати.

13. А. Н. Фролов SET-1-сводимость на классе вычислимых множеств // Известии вузов. Математика, принята к печати.

14. А. Н. Фролов копии линейных порядков // Алгебра и логика, в печати.

15. А. Н. Фролов Вычислимые алгебры Ершова // Казань: Казанское математическое общество, 2004, Препринт 04/2.

16. A.N. Frolov On the class of recursive sets // Proceedings of «Logic Colloquium'2001», Vienna (Austria), August 2001, p. 144.

17. A.N. Frolov Set-theoretical properties of classes of computable sets // Proceedings of «Logic Colloquium'2002», Munster (Germany), August 2002, p. 33.

18. А. Н. Фролов Теоретико-множественная структура вычислимых множеств // Труды XXIV конференции молодых ученых, апрель 2002, МГУ, т. II, 179 182.

19. А. Н. Фролов Структура вычислимых множеств // тезисы лучших докладов итоговой научной студенческой конференции 2001 года, Казанский государственный университет, 2002, 41 42.

20. А. Н. Фролов Алгебры Ершова, имеющие вычислимую копию // тезисы конференции «Колмогоров и современная математика», апрель 2003, 709 710.

21. A.N. Frolov Computable copies of Boolean and Ershov algebras // Proceedings of «Logic Colloquium'2003», Helsinki (Finland), August 2003.

22. A.H. Фролов Алгебры рекурсивных множеств // тезисы лучших докладов итоговой научной студенческой конференции 2002 года, Казанский государственный университет, 2003, 130 131.

23. A.N. Frolov Computable copies of distributive lattices with relative complements and linear orderings // Proceedings of «Logic Colloquium'2004», Turin (Italy), July 2004, p. 78.

24. A.H. Фролов Дд-спектры линейных порядков // тезисы конференции «Алгебра и анализ-2004», Казань, июнь 2004, с. 71.

25. С. С. Гончаров Счетные булевы алгебры и разрешимость. Новосибирск: Научная книга, 1996.-364 с.

26. R.G. Downey, On presentations of algebraic structures, in Complexity, Logic, and Recursion Theory, ed. A. Sorbi (New York: Dekker, 1997), 157 205.

27. R.G. Downey and J.F. Knight, Orderings with a-th jump degree // Proceedings of the American Mathematical Society, 14, 1992, 545 552.

28. R. Watnik, A generalization of Tennenbaum’s theorem on effectively finite recursive linear orderings // The Journal of Symbolic Logic, 49, 1984, 563 569.

29. K. Ambos-Spies Honest polinomial time reducibilities and the P=NP problem // J. Comput. System Sci., 1989, vol. 39, pp. 250 281.

30. А. И. Мальцев Алгоритмы и рекурсивные функции Москва: «Наука», 1986, 367 с.