О тьюринговой сложности классов моделей и теорий тема автореферата и диссертации по математике, 01.01.06 ВАК РФ

На правах рукописи

□ОЗ172237

Фокина Екатерина Борисовна

О ТЬЮРИНГОВОЙ СЛОЖНОСТИ КЛАССОВ МОДЕЛЕЙ И ТЕОРИЙ

01 01 06 — математическая логика, алгебра и теория чисел

Автореферат диссертации на соискание ученой степени кандидата физико-математических наук

Новосибирск — 2008

1 6 ¡>т 2т

003172237

Работа выполнена в Институте математики им С J1 Соболева СО РАН

Научный руководитель

Официальные оппоненты

доктор физико-математических наук, профессор, член-корреспондент РАН Гончаров Сергей Савостьянович

доктор физико-математических наук, профессор Добрица Вячеслав Порфирьевич

доктор физико-математических наук, профессор Хисамиев Назиф Гарифуллино-вич

Ведущая организация Казанский государственный университет

Защита состоится "27" июня 2008г в _14_ ч _00_ мин на заседании диссертационного совета Д 003 015 02 при Институте математики им С Л Соболева СО РАН по адресу пр-т Академика Коптюга 4, Новосибирск, 630090

С диссертацией можно ознакомиться в библиотеке ИМ СО РАН

Автореферат разослан "¿2, " ^tcc-i 2008 г

Ученый секретарь диссертационного совета

кандидат физико-математических наук .^/С/йЙ^ А Н Ряскин

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ Объект исследования и актуальность темы К числу фундаментальных проблем, изучаемых в математической логике, относятся исследования природы разрешимости и неразрешимости алгоритмических проблем на алгебраических структурах В рамках теории вычислимых моделей разработаны различные подходы к исследованию этой проблемы Основы теории вычислимых моделей были заложены в 50-е годы в работах А И Мальцева [8j, Р Воота [24], А Фролиха и Дж Шефердсона [12], О Рабина [23] Существенный вклад в развитие теории вычислимых моделей был сделан Ю Ершовым Определенное им понятие сильно конструктивной модели позволило изучать алгоритмические свойства моделей разрешимых элементарных теорий и построй! ь теорию разрешимых моделей Основные направления исследований в теории вычислимых моделей были отражены в двухтомном издании "Handbook of Recursive Mathematics" [15] под редакцией Ю Ершова, С Гончарова, А Нероуда, Дж Реммела, а также в обзорах по теории вычислимых моделей С С Гончарова и Б М Хусаинова [14] и С С Гончарова [13]

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

Известно, что в общем случае любая непротиворечивая разрешимая теория Т имеет разрешимую модель А Более того, такая модель А может быть построена эффективно по Т С другой стороны, если у теории существует вычислимая модель, то такая теория разрешима относительно 0W Добавим еще, что существуют примеры даже конечно аксиоматизируемых, а значит, вычислимо перечислимых теорий, которые не имеют вычислимых моделей [2]

Наиболее значительные результаты об условиях существования вычислимых моделей были получены для счетно-категоричных теорий В

[21] М Лерман и Дж Шмерл дали достаточные условия, чтобы счетно-категоричная теория имела вычислимую модель Одним из условий являлась арифметическая сложность теории В [20] Дж Найт усилила этот результат, после чего для существования вычислимой модели уже не предполагалась арифметичность теории Однако, долгое время все известные примеры счетно-категоричных теорий имели невысокую сложность Естественно возникающий вопрос о существовании счетно-категоричных теорий, удовлетворяющих условиям теорем из [20] или [21] для достаточно больших п, был задан Дж Найт и некоторое время оставался открытым С Гончаров и Б Хусаинов в [5] для любого п построили пример счетно-категоричной теории с вычислимой моделью сложности О"

В случае несчетно категоричных теорий первого порядка Л Харринг-тон в [16] и Н Хисамиев в [10] показали, что на самом деле все счетные модели разрешимой несчетно категоричной теории разрешимы Этот результат побудил изучать вычислимые модели Кгкатегоричных неразрешимых теорий Если Т несчетно категорична, но неразрешима, то некоторые ее счетные модели могут быть вычислимы, а другие нет Например, С Гончаров в [1] показал, что существует ^-категоричная теория, вычислимая с оракулом 0', для которой вычислима только простая модель Позже К Ку-дайбергенов обобщил этот результат в [7], построив для любого п пример ^-категоричной, вычислимой с оракулом 0' теории Т, у которой вычислимы лишь первые п моделей В ряду [17], [19], [22] последовавших за этим примеров ^-категоричных теорий, имеющих вычислимую модель, все теории были разрешимы с оракулом О". С Гончаров и Б Хусаинов в [4, 5] построили для любого п > 1 пример ^-категоричной теории, эквивалентной по Тьюрингу степени 0" и имеющей вычислимую модель

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

спецификаций В рамках этой проблемы важно исследовать как отдельные классические и производные от них алгебраические структуры, так и их естественные классы и подклассы, структуры, семантики и алгоритмические проблемы языков спецификаций Это направление исследований является актуальным и привлекает внимание многих специалистов, таких как Ю Ершов, С Гончаров, А Морозов, В Добрица, Дж Найт, С Лемпп, А Нис, В Харизанова, Б Хусаинов и другие

Возможные методы изучения связей между определимостью и вычислимостью описаны в работе С Гончарова и Дж Найт [3] Один из таких методов связан с понятием индексного множества из теории нумераций Исследования по связи алгоритмических свойств индексных множеств и структурных свойств семейств множеств является классическим вопросом теории вычислимых нумераций Этот подход оказывается эффективным и при изучении классов вычислимых моделей через вычислимые нумерации классов моделей данной сигнатуры По известному результату А Нуртази-на [9] существует универсальная вычислимая нумерация всех вычислимых моделей конечной предикатной сигнатуры а Другими словами, существует равномерно вычислимая последовательность {Лп}пби1 вычислимых моделей сигнатуры сг, такая, что каждая вычислимая модель В сигнатуры а изоморфна некоторой Ап из последовательности (при этом п находится эффективно по В) Назовем индексным множеством 1{К) класса К множество всех номеров п, соответствующих вычислимым моделям из К в данной нумерации В универсальной нумерации свойства сложности классов вычислимых моделей характеризуются через сложность их индексных множеств в этой нумерации Т е задача изучения связей между алгоритмическими и теоретико-модельными свойствами различных естественных классов моделей сводится к изучению сложности индексных множеств для этих классов В общем случае универсальные нумерации не существуют В этом случае наряду с вычислимыми моделями необходимо рассматривать и частичные вычислимые модели, для которых также можно построить универсальную вычислимую нумерацию

При получении результатов об алгоритмических свойствах моделей с интересными алгебраическими и теоретико-модельными свойствами часто

возникает вопрос о существовании моделей с подобными алгоритмическими свойствами в других важных классах Во многих случаях оказывается возможным осуществить перенос таких результатов, полученных для определенных моделей, на модели из других классов Один из возможных путей получить подобные обобщения заключается в кодировании исходной модели в модели из другого класса таким образом, чтобы сохранить интересующие алгоритмические свойства Наглядной иллюстрацией применения этих методов могут послужить работы [13] и [18], где предлагаются методы кодирования моделей, позволяющие свести алгоритмические вопросы для произвольных моделей к аналогичным вопросам для графов Интересным представляется вопрос об обобщении подобных результатов на классы моделей других сигнатур, в частности получение результатов для произвольных богатых сигнатур, т е сигнатур, содержащих хотя бы один бинарный предикатный или функциональный символ, или хотя бы два унарных функциональных символа

Цель работы Исследовать вопрос существования вычислимых моделей с фиксированными теоретико-модельными и алгоритмическими свойствами их теорий для случая счетно-категоричных и несчетно категоричных теорий Изучить алгоритмические свойства различных классов вычислимых моделей через их индексные множества Получить результаты об алгоритмических свойствах моделей различных сигнатур

Методы исследования В работе используются методы теории вычислимых нумераций [6], обобщения метода понижения сложности моделей из [5] и метода сведения сигнатур, разработанного в [13] Кроме того, разрабатываются различные методы построения моделей с заданными теоретико-модельными и алгоритмическими свойствами

Научная новизна Все результаты диссертации являются новыми и снабжены подробными доказательствами, они опубликованы автором диссертации в научных журналах из перечня ВАК ведущих рецензируемых научных журналов и изданий, в которых должны быть опубликованы основные научные результаты диссертации

Практическая ценность Работа носит теоретический характер Ее результаты могут найти применение в дальнейших исследованиях по теории

вычислимых моделей

Основные результаты В работе получены следующие результаты

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

2 Получены точные оценки m-степеней индексных множеств для следующих классов

(a) разрешимых моделей,

(b) разрешимых моделей со счетно-категоричной теорией,

(c) вычислимых моделей с разрешимой теорией

Кроме того, получены аналогичные оценки для вычислимых моделей из классов неориентированных графов, частичных порядков и решеток

3 Получен ряд результатов об алгоритмических свойствах классов моделей, сигнатура которых содержит два унарных функциональных символа

Апробация Результаты диссертации были представлены на XL Международной научной студенческой конференции (Новосибирск, 2002), на Международной конференции "Мальцевские чтения" (Новосибирск, 2003 и пленарный доклад в 2007), на Международной конференции "Methods of Logic m Mathematics III" (Санкт-Петербург, 2006), на 2-ой Студенческой логической конференции (Нью-Йорк, США, 2007), на Международной конференции "Computabihty in Europe" (Сиена, Италия, 2007), на Международной конференции "Вычислимые модели и нумерации" (Новосибирск, 2007) Кроме того, результаты докладывались на семинаре "Конструктивные модели" Новосибирского государственного университета и Общеинститутском математическом семинаре Института математики СО РАН

Публикации Основные результаты диссертации опубликованы в работах автора [25]—[33]

Структура и объем работы Диссертация состоит из введения, четырех глав, разбитых на параграфы, и списка литературы Работа изложена на 83 страницах, список литературы содержит 74 наименования

СОДЕРЖАНИЕ РАБОТЫ

Во введении обоснована актуальность проводимых исследований, приводится краткая история вопроса Также во введении даны необходимые предварительные сведения и определения, формулируются основные положение диссертации

В главе 1 рассматриваются два метода работы с моделями, вычислимыми относительно заданных степеней Эти методы позволяют преобразовывать построенные модели и классы моделей, изменять их сигнатуру, понижать их алгоритмическую сложность, сохраняя при этом многие алгоритмические и теоретико-модельные свойства Методы используются для получения дальнейших результатов диссертации Первый метод позволяет равномерно понижать сложность моделей, сохраняя при этом необходимые теоретико-модельные и алгоритмические свойства моделей Метод основан на понятиях маркеровских 3- и У-расширений предикатов и моделей, а также однозначного представления предикатов

Теорема 1. Пусть <1 — произвольная арифметическая тъюримова степень Пусть {Мп}п£ч> — вычислимая последовательность моделей сигнатуры а, равномерно вычислимых с оракулом <!', и носители всех моделей вычислимы Пусть о* С о, и все предикаты из а" = а \ а' во всех моделях равномерно й-вычислимы Пусть для каждого п и для каждого Р £ а' в Мп существует бесконечное вычислимое подмножество Зп,р, и Р\Бп>р бесконечно Тогда существует вычислимая последовательность (1-вычислимых моделей {Мп}пеи>, для которой каждый Я = Дд (где Р 6 сг1) в каждой М*п обладает бесконечным вычислимым подмножеством Б* я С Д, и Д \ 5* н бесконечно, а кроме того

1 Мп разрешима 4=Ф- Л4* разрешима,

2 Мп а-категоричиа }Л'п а-категорична (для произвольного бесконечно го а),

3 ТЦМп) =Т тцм:)

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

Теорема 2 Для вычислимой последовательности моделей {Мп}п^и, произвольной конечной сигнатуры а существует вычислимая последовательность графов {Сп}п6ш такая, что

1 Мп вычислима -й- С„ вычислим,

2 Мп разрешима Сп разрешим,

3 ТЪ.(Мп) разрешима ТЬ((3П) разрешима,

4 ТЪ(.Мп) счетно-категорична ТЬ(Сп) счетно-категорична

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

Глава 2 посвящена изучению вопроса существования вычислимых моделей с различными спецификациями, тес заданными алгоритмическими и теоретико-модельными свойствами, а также вопроса сложности теорий таких моделей Рассматриваются такие важные классы теорий, как класс несчетно категоричных и класс счетно-категоричных теорий Теории, категоричные в некоторой бесконечной мощности, являются одним из классических объектов в теории моделей В связи с этим вопрос об алгоритмических свойствах таких теорий и их моделей представляет особый интерес В данной главе мы рассматриваем вопрос существования категоричных теорий высокой алгоритмической сложности с вычислимыми моделями Более точно, по произвольной арифметической тьюринговой степени мы строим примеры категоричных теорий в точности заданной сложности, имеющих вычислимые модели

Основные результаты главы сформулированы в следующих теоремах

Теорема 3. Для любой арифметической степени существует несчетно категоричная теория Т конечной сигнатуры с вычислимой моделью, по Тьюрингу эквивалентная этой степени Кроме того, все счетные модели этой теории Т имеют, вычислимое представление

Теорема 4 Для любой арифметической степени существует счетно-категоричная теория Т конечной сигнатуры с вычислимой моделью, по Тьюрингу эквивалентная этой степени

В частности, теорема 4 дает положительный ответ на вопрос Дж Найт из [20] для всех арифметических тьюринговых степеней

В главе 3 исследуются взаимосвязи между определимостью и вычислимостью моделей Изучение алгоритмической сложности различных важных классов вычислимых моделей проводится на основе понятия индексного множества класса моделей, т е множества индексов вычислимых членов класса в универсальной вычислимой нумерации всех вычислимых моделей фиксированной сигнатуры При таком подходе задача изучения алгоритмических свойств класса моделей сводится к получению точной оценки сложности индексного множества данного класса Индексное множество 1{К) класса К называется т-полным в некотором классе сложности Г, если существует вычислимая последовательность моделей {Сп}пеи, для которой п 6 5 тогда и только тогда, когда С„& К

В рамках этого подхода для произвольной арифметической степени с1 мы исследуем алгоритмическую сложность следующих естественных классов вычислимых моделей ¿-разрешимых моделей, с1-разрешимых моделей со счетно-категоричной теорией, вычислимых моделей с разрешимой теорией

Теорема 5. Для любой арифметической тьюринговой степени с! индексное множество СКЛ всех с1-разрешимых моделей является т-полным Бз'"1 множеством в универсальной вычислимой нумерации всех вычислимых моделей произвольной конечной богатой сигнатуры

Следствие 6. Индексное множество всех разрешимых моделей произвольной конечной богатой сигнатуры имеет Тъюрингову степень 0"

Теорема 7. Для любой арифметической тъюрингоеой степени с1 индексное множество СК$ всех <1-разрешимых счетно-категоричных моделей является т-полным Е^ — -множеством в универсальной вычислимой нумерации, оссх бш1.иыч1мои, миделей произвольной конечной богатой сигнатуры (т е Сявляется т-полным в классе разностей двух множеств )

Теорема 8 Индексное множество ВТ всех вычислимых моделей с разрешимыми теориями является т-полным ь2 множеством (или в обозначениях из [И] т-полным в универсальной вычислимой нумерации вычислимых моделей произвольной конечной богатой сигнатуры

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

В главе 4 исследуется вопрос о переносе алгоритмических свойств, полученных для моделей из одних классов, на модели из других классов Предлагается метод кодирования моделей, позволяющий гарантировать сохранение многих алгоритмических и теоретико-модельных свойств при переходе от графов к моделям, сигнатура которых содержит два одноместных функциональных символа В частности, сохраняется вычислимость моделей, разрешимость моделей и их теорий, счетная категоричность Также сохраняется <1-вычислимая размерность моделей (т е число вычислимых представлений модели с точностью до (¿-вычислимого изоморфизма) Сохраняется спектр степеней DgSp(Л) счетной модели А, те множество всех степеней представлений А, и спектр степеней дополнительных отношений на модели

Теорема 9 Пусть С — граф Тогда существует модель А сигнатуры сто с двумя одноместными функциональными символами, построенная по О так, что

1 А вычислима <=> С вычислим,

£ А разрешима <=> С разрешим,

3 разрешима ТЬ(С) разрешима,

4 ТЬ(„Д) счетно-категорична Т11(С?) счетно-категорична,

5 Б88р(Д) = ^(в),

6 Если (? вычислимо представим, то

(a) для любой степени (1 А обладает той же самой <1-вычислилюй размерностью, что б,

(b) для любого х € |С| существует Ь 6 и(А), такой что (А,Ь) обладает той же вычислимой размерностью, что ((?, х),

(c) если Б С ¡(?|, то существует множество V С \и{А)\, такое что DgSp_д(V) = DgSpG(5) и если Б наследственно вычислимо перечислимо, то таковым же является и V

Как следствие, получаем следующие результаты

Следствие 10. Для любого 1 < п < и существует модель А сигнатуры сто с двумя одноместными функциональными символами, вычислимая размерность которой равна п

Следствие 11. Для любого 1 < п < и существует вычислимо категоричная модель А сигнатуры сто и элемент а 6 |.А|, такие, что вычислимая размерность модели (Л, а) равна п

Следствие 12 Существует модель сигнатуры сто, имеющая представления во всех степенях, кроме О

Следствие 13. Для любого вычислимого ординала а существует вычислимая модель А сигнатуры сто, которая является Д®-категоричной, но не относительно /^-категоричной

Таким образом, полученные результаты, в совокупности с ранее известными, дают информацию о многих алгоритмических свойствах классов моделей произвольных богатых сигнатур

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

Список литературы

[1] Гончаров С С Конструктивные модели wj-категоричных теорий //

Л«______ . „<•.., л О.,. m 19 Мй 1П70 ~ ООС ООО

iUatVjmuitii^k.[inV/ v^uivii*! х .Li^tW, v* uuu uoiJ

[2] Гончаров С С, Ершов Ю Л Конструктивные модели, Новосибирск, Научная книга, 1999, 360 с

[3] Гончаров С С , Найт Дж Ф Вычислимые структурные и антиструктурные теоремы // Алгебра и логика, т 41, N6, 2002, с 639-681

[4] Гончаров С С , Хусаинов Б М О сложности теорий вычислимых категоричных моделей // Вестник НГУ, Мат-Мех-Информ , т 1, N2, 2001, с 63-76

[5] Гончаров С С, Хусаинов Б М Сложность теорий вычислимых категоричных моделей // Алгебра и логика, т 43, N6, 2004, с 365-373

[6] Ершов Ю Л Теория нумераций, М , Наука, 1977

[7] Кудайбергенов КЗ О конструктивных моделях неразрешимых теорий // Сиб Маг Ж , т 21, N5,1980, с 155-158

[8] Мальцев А И О рекурсивных абелевых группах // Доклады Акад наук СССР, г 146, N5, 1962, с 1009-1012

[9] Нуртазин А Т Вычислимые классы и алгебраический критерий автоустойчивости // Канд диссертация, Институт математики и механики, Алма-Ата (1974)

[10] Хисамиев Н Г Сильно конструктивные модели разрешимой теории // Изв Акад Наук Казах ССР, Сер Физ -Мат, т 35, N1, 1974, с 83-84

[И] Ash С J., Knight J F, Computable Structures and the Hyperarithmetical Hierarchy Studies m Logic and the Foundations of Mathematics, 144 North-Holland Publishing Co , Amsterdam, 2000

[12] Frohhch A , Shepherdson J Effective procedures in field theory // Philos Trans Roy Soc London, Ser A, v 248, 1956, pp 407-432

[13] Goncharov S S Computabihty and Computable Models // Mathematical problems from applied logic 11 Logics for the XXIst century Edited by Dov M Gabbay, Sergey S Goncharov and Michael Zakharyaschev International Mathematical Series (New York), Springer, New York, 2007, pp 99-216

[14] Goncharov S , Khoussainov B Open problems in the theory of constructive algebraic systems // Computabihty theory and its applications (Boulder, CO), 1999, pp 145-170

[15] Handbook of Recursive Mathematics In 2 v / Ed Yu L Ershov, S S Goncharov, A Nerode, J Remmel, New York Elsevier, 1998

[16] Harrington L Recursively Presentable Prime Models//J Symbolic Logic, v 39, N2, 1974, pp 305-309

[17] Hirschfeldt D R, Khoussainov B, Semukhm P An Uncountably Categorical Theory Whose Only Computably Presentable Model Is Saturated // Notre Dame J Formal Logic, v 47, N1, 2006, pp 63-71

[18] Hirschfeldt D R , Khoussainov B, Shore R A , Shnko A , Degree specti a and computable dimensions in algebraic structures 11 Ann Pure Appl Logic, v 115, N1-3, 2002, pp 71-113

[19] Khoussainov B , Nies A , Shore R A On Recursive Models of Theories // Notre Dame J Formal Logic, v 38, N2, 1997, pp 165-178

[20] Knight J F Nonanthmetical No-categorical Theories with Recursive Models // J Symbolic Logic, v 59, N1,1994, pp 106-112

[21] Lerrnan M, Schmerl J Theories With Recursive Models //J Symbolic Logic, v 44, N1, 1979, pp 59-76

[22] Nies A A new spectrum of recursive models // Notre Dame J Formal Logic, v 40, N3, 1999, pp 307-314

[23] Rabin M 0 Effective computabihty of winning strategies//Contributions to the Theory of Games, v 3, Princeton Umv Press, Princeton, 1957, pp 147-157

[24] Vaught R L Sentences true in all constructive models // J Symbolic Logic, v 25, N1, 1960, pp 39-58

Работы автора по теме диссертации

[25] Fokma ЕВ On degrees of uncountably categorical theories with computable models // Proceeding of Workshop "Computability and models Almaty, June 24-28, 2002, pp 32

[26] Фокина E Б О сложности категоричных теорий с вычислимыми моделями // Вестник НГУ, т 5, N2, 2005, с 78-86

[27] Фокина Е Б О спектрах вычислимых моделей // Вестник НГУ, т 6, N6, 2006, с 69-73

[28] Fokma Е В Arithmetical Turing Degrees and Categorical Theories of Computable Models // Mathematical Logic in Asia Proceedings of the 9th Asian Logic Conference, 2006, pp 58-69

[29] Фокина E Б Индексные множества разрешимых моделей // Сиб Мат Ж , т 48, N5, 2007, с 1167-1179

[30] Fokma Е В Index Sets of Computable Structures with Decidable Theories // Computation and Logic m the Real World - Thud Conference of Computability in Europe, CiE 2007, Siena, Italy, June 2007, Proceedings, Lecture Notes m Computer Science, v 4497, 2007, pp 290-296

[31] Фокина E Б Алгоритмические свойства моделей сигнатуры с двумя одноместными функциональными символами // Вестник НГУ, т 8, N1, 2008, с 90-101

[32] Fokma Е В Index Sets for some classes of structures // принята в Ann Pure Appl Logic

[33] Calvert W, Fokma E, Goncharov S S, Knight J F , Kudmov О V, Morozov A S, Puzarenko V Index sets for classes of high rank structures 11 J Symbolic Logic, v 72, N4, 2007, pp 1418-1446

Фокина Екатерина Борисовна

О тьюринговой сложности классов моделей и теорий

Автореферат диссертации на соискание ученой степени кандидата физико-математических наук

Подписано в печать 19 05 08 Формат 60x84 1/16 Уел печ л 1,0 Уч -изд л 1,0 Тираж 100 экз Заказ №95

Отпечатано в ООО "Омега Принт" 630090, Новосибирск, пр Лаврентьева, 6

Введение

1 Методы преобразования моделей

1.1 Метод понижения сложности.

1.2 Метод сведения сигнатур.

1.3 Функторы для сведения к сигнатуре графов.

2 Сложность теорий с вычислимыми моделями

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

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

3 Индексные множества

3.1 Разрешимые модели.

3.2 Разрешимые счетно-категоричные модели.

3.3 Модели с разрешимой теорией.

Формализация понятия алгоритма и исследование феномена вычислимости породили интерес к изучению эффективных математических объектов, следствием чего стало развитие такого направления теории вычислимости, как теория вычислимых моделей. Основы теории вычислимых моделей были заложены в 50-е годы в работах А. И. Мальцева [25], Р. Во-ота [64], А. Фролиха и Дж. Шефердсона [42], О. Рабина [60]. В работе А. И. Мальцева [24] были намечены основные направления развития этой теории. Существенный вклад в развитие теории вычислимых моделей был сделан Ю. Ершовым. Предложенное им понятие сильно конструктивной модели [17] было базисным для развития теории разрешимых моделей, которая явилась синтезом абстрактной теории моделей и теории вычислимости. Понятие сильно конструктивной модели позволило изучать алгоритмические свойства моделей разрешимых элементарных теорий. Основные направления исследований в теории вычислимых моделей в мире были отражены в двухтомном издании "Handbook of Recursive Mathematics" [41] под редакцией Ю. J1. Ершова, С. С. Гончарова, А. Нероуда, Дж. Ремме-ла. Развитие теории вычислимых моделей в России нашло отражение в монографии Ю. JL Ершова и С. С. Гончарова [10]. Наиболее актуальные проблемы и современные пути развития теории вычислимых моделей были отражены в работах С. С. Гончарова и Б. Хусаинова [43] и С. С. Гончарова [40].

Понятие вычислимой (конструктивной) модели было введено в связи с изучением алгоритмических проблем как в математической логике, так и в алгебре. Основной задачей теории вычислимых моделей является выявление и описание взаимосвязей между алгебраическими, теоретико-модельными и алгоритмическими свойствами моделей. Одно из важных направлений теории вычислимых моделей связано с изучением условий существования вычислимых моделей с заданными элементарными свойствами. Другой вопрос, связанный с первым, — найти связи между алгоритмической сложностью моделей и различными теоретико-модельными свойствами их теорий. Это направление исследований является актуальным и привлекает внимание многих специалистов, таких как Ю. Ершов, С. Гончаров, А. Морозов, В. Добрица, Дж. Найт, С. Лемпп, А. Нис, В. Ха-ризанова, Б. Хусаииов и другие.

Введем основные определения. Зафиксируем вычислимую геделев-скую нумерацию сигнатуры а. Считаем, что носители моделей содержатся в ш, которое мы рассматриваем как вычислимое множество констант.

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

Мы отождествляем формулы с их геделевскими номерами. Тогда вычислимость модели эквивалентна условию, что атомная диаграмма Т>{А) этой модели вычислима, где Т>(А) = атомная формула или отрицание атомной формулы без свободных переменных сигнатуры а а и А |= </?}. То есть на элементах вычислимой модели А мы можем эффективно проверить истинность бескванторных формул.

Определение 0.0.2. Модель А сигнатуры и разрешима, если вычислима ее полная диаграмма Т>С(А) = предложение сигнатуры а а и А |= </?}. Другими словами, мы можем эффективно определить истинность любых формул с кванторной приставкой произвольной длины на элементах модели А.

Определение 0.0.3. Полная теория Т называется а-категоричной. или категоричной в мощности а, если все модели теории Т мощности а изоморфны.

М. Морли [22] показал, что любая теория, категоричная в некоторой несчетной мощности, будет категорична в любой несчетной мощности. Поэтому, если а — несчетный кардинал, то мы не будем различать понятия а-категоричной, ^i-категоричной и несчетно категоричной теории.

Определение 0.0.4. Модель Л4 называется а-категоричной, если теория ТЬ(Л4) этой модели а-категорична.

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

Известно, что в общем случае любая непротиворечивая разрешимая теория Т имеет разрешимую модель А■ Более того, такая модель Л может быть построена эффективно по Т. С другой стороны, если у теории существует вычислимая модель, то такая теория разрешима относительно 0Ш. Например, теория арифметики {и, S, +, х, <, 0) эквивалентна 0W. При этом ее стандартная модель вычислима, однако [10] все ее другие счетные модели имеют уже неарифметическую сложность. Добавим еще, что существуют примеры даже конечно аксиоматизируемых, а значит, вычислимо перечислимых теорий, которые не имеют вычислимых моделей [10].

Наиболее значительные результаты об условиях существования вычислимых моделей были получены для счетно-категоричных теорий. В [57] М. Лерман и Дж. Шмерл дали достаточные условия, чтобы счетно-категоричная теория имела вычислимую модель. А именно, они показали, что если теория Т имеет арифметическую сложность и для каждого п множество En+i предложений является £п множеством, то счетная модель Т имеет вычислимое представление. В [54] Дж. Найт усилила этот результат, опуская условие арифметичности теории, но предполагая равномерность условия на сложность предложений. Долгое время все известные примеры счетно-категоричных теорий имели достаточно невысокую сложность. Естественно возникающий вопрос о существовании счетно-категоричных теорий, удовлетворяющих условиям теорем из [54] или [57] для больших п, был задан Дж. Найт и некоторое время оставался открытым. С. Гончаров и Б. Хусаинов в [15] для любого п построили пример счетно-категоричной теории с вычислимой моделью сложности 0П. Используя технику из [15], по произвольной заданной арифметической степени d мы построим пример счетно-категоричной теории с вычислимой моделью, имеющую сложность d. Тем самым получаем ответ на вопрос Дж. Найт для теорий любой арифметической сложности.

В случае несчетно категоричных теорий первого порядка Л. Харринг-тон в [48] и Н. Хисамиев в [30] показали, что на самом деле все счетные модели такой теории разрешимы. Если Т несчетно категорична, но неразрешима, то некоторые ее счетные модели могут быть вычислимы, а другие нет. В статье Дж. Балдвина и А. Лахлана [34] доказано, что все счетные модели ^-категоричной теории могут быть представлены цепью элементарных расширений Ло ■< Л\ Лч ^ . •. Ли, где Ло простая модель, Ли насыщенная модель, а любая модель является минимальным собственным элементарным расширением модели Лг. Тогда спектр вычислимых моделей теории Т есть SCM{T) = {г | Лг имеет вычислимое представление}. Таким образом, результат JI. Харрингтона и Н. Хисамиева может быть представлен в виде SCM{T) = o;(J{u;}. Этот результат побудил изучать вычислимые модели несчетно категоричных неразрешимых теорий. С. Гончаров в [3] показал, что существует ^i-категоричная теория, вычислимая с оракулом 0', для которой SCM(T) = {0}. Позже К. Кудайбергенов обобщил этот результат в [23], построив пример ^i-категоричной, вычислимой с оракулом 0' теории Т с SCM(T) — {0,1. ,п}. Б. Хусаинов, А. Нис, Р. Шор в [52] построили примеры Ni-категоричных теорий Т\ и Т2, вычислимых с оракулом 0", таких, что SCM(Ti) = и и SCM(T2) = и U(w}\{0}-П. Семухин, Д. Хиршфилд, Б. Хусаинов в [49] построили 0"-вычислимую теорию Т с SCM(T) = {о;}. Кроме того, А. Нис в [59] построил пример Ki-категоричной теории Т, для которой SCM(T) = {1}, и доказал, что для произвольной fti-категоричной теории Т SCM(T) G Е®^). Заметим, что все приведенные примеры Ki-категоричных теорий, имеющих вычислимую модель, разрешимы с оракулом О". С. Гончаров и Б. Хусаинов в [14, 15] построили для любого п > 1 пример ^i-категоричной теории, эквивалентной по Тьюрингу степени 0П и имеющей вычислимую модель. Используя некоторую модификацию конструкции из [15], мы по любой арифметической степени d построим ^i-категоричную теорию, по Тьюрингу эквивалентную d, имеющую вычислимую модель. Кроме того, будет показано, что на самом деле все модели этой теории имеют вычислимое представление, т. е. SCM{T)=UJ UM

В связи с этим интересным является вопрос об оценке сложности несчетно категоричных теорий с вычислимыми моделями, а также о сложности счетных моделей для несчетно категоричных теорий, имеющих вычислимую модель. Этот вопрос исследовался [8, 45] для такого важного подкласса несчетно категоричных теорий, как класс сильно минимальных теорий. Полная теория Т называется сильно минимальной, если в любой ее модели любое формульное подмножество основного множества этой модели, определимое с параметрами из этой модели, является конечным либо его дополнение конечно, то есть в ней тождественно истинная формула является сильно минимальной формулой. Сильно минимальная теория называется тривиальной, а более точно с тривиальной предгеометрией, если для любого подмножества А С М, выполнено равенство acl(A) = (J acl({o}). а&А

В [45] был доказан следующий результат о сложности сильно минимальных теорий и их моделей.

Теорема 0.0.1. Пусть Л4 — вычислимая сильно минимальная модель с тривиальной предгеометрией. Тогда ее теория Th(.M) 0"-разрешима, и все счетные модели ее теории 0"-разрешимы, в частности, 0"- вычислимы.

В [8] С. С. Гончаров доказал следующий результат.

Теорема 0.0.2. Если АЛ — вычислимая модель сильно минимальной теории, то все ее счетные модели 0"-вычислимы.

Другой вопрос в исследовании алгоритмических свойств алгебраических систем связан с решением проблемы определимости и ее степени сложности. В связи с этим вопросом исследуется алгоритмическая сложность различных классов вычислимых моделей, что позволяет установить взаимосвязь между определимостью классов вычислимых моделей и их алгоритмической сложностью. Вопрос характеризации классов вычислимых моделей можно сформулировать следующим образом. Пусть К — некоторый класс моделей. Обозначим через Кс множество вычислимых моделей из К. Вычислимая характеризация класса К должна отделять вычислимые модели из класса К от всех остальных (будь то не из К или невычислимых). Возможные подходы к изучению вычислимой характеризации классов описаны в работе С. Гончарова и Дж. Найт [11]. Один из таких подходов к изучению связей между определимостью и вычислимостью классов моделей связан с понятием индексного множества из классической теории нумераций [1], [18], [29]. Рассмотрим последовательность {An}nzu> вычислимых моделей.

Определение 0.0.5. Последовательность {Лп}пеш называется вычислимой, если последовательность вычислимых индексов для носителей моделей Лп из последовательности и всех предикатов и констант вычислима.

Другими словами, по номеру модели в последовательности можем вычислить индекс атомной диаграммы этой модели, т. е. можем эффективно проверить истинность атомарных формул на элементах этой модели. Известный результат А. Нуртазина [26] показывает, что существует универсальная вычислимая нумерация всех вычислимых моделей фиксированной конечной предикатной сигнатуры а. Т. е. существует вычислимая последовательность {Лп}п&ш вычислимых моделей сигнатуры а такая, что для каждой вычислимой модели В сигнатуры а мы можем эффективно найти Лп, которая изоморфна В.

Определение 0.0.6. Индексным множеством модели В сигнатуры и будем называть множество 1(B) всех индексов вычислимых (изоморфных) копий В в данной нумерации. Для класса К моделей, замкнутого относительно изоморфизма, индексным множеством называется множество 1(К) всех индексов вычислимых моделей из К.

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

Работы по индексным множествам моделей можно найти у многих авторов (см., например, [11], [16], [20], [21], [35], [36], [38] и др.). В рамках этого подхода, на основе ранее разработанных методов, с использованием фактов из теории нумераций [19], в работе изучается алгоритмическая сложность таких естественных классов моделей, как класс разрешимых моделей, класс разрешимых моделей со счетно-категоричной теорией, класс моделей с разрешимой теорией сигнатуры графов. Кроме того, получены аналогичные результаты для таких известных классов моделей, как ориентированные графы, частичные порядки и решетки.

Задача изучения структурных свойств вычислимых моделей и классов вычислимых моделей может рассматриваться не только через точную оценку их индексных множеств, но и в рамках изучения сложности их ранга и формул Скотта. Ранг Скотта является мерой теоретико-модельной сложности алгебраических систем через сложность бесконечных вычислимых формул, определяющих эти алгебраические системы. Известно, что ранг Скотта произвольной вычислимой модели не превосходит + 1, и что все ординалы, не превосходящие UiK + 1, реализуются как ранги Скотта некоторых вычислимых моделей (где — первый невычислимый ординал). В [74] изучались индексные множества классов моделей с различными рангами Скотта. Были установлены следующие точные оценки.

Теорема 0.0.3. (С. Гончаров, У. Калверт, О. Кудинов, А. Морозов, Дж. Найт, В. Пузаренко, Е. Фокина в [74]).

• Индексное мноо/сество 1(Кпсотр) вычислимых моделей с невычислимыми рангами Скотта является т-полным Е* мноэ/сеством.

• Индексное множество I(Кшск) вычислимых моделей с рангом Скотта u>iK является т-полным множеством вида (У)(Э)(П;| — П}).

• Индексное множество /(i^wcK+1) вычислимых моделей с рангом Скотта +1 является т-полным множеством вида

3)(У)(П}-П}).

Перейдем к другим подходам к изучению алгоритмических свойств вычислимых моделей. Ниже перечислим некоторые из них. Более детальные обзоры можно найти в [40] и [51].

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

Определение 0.0.7. Если d — тьюрингова степень, то d-вычислимой размерностью вычислимо представимой модели А называется число вычислимых представлений модели А с точностью до d-вычислимого изоморфизма. Если d-вычислимая размерность А равна 1, то А называется d-вычислимо категоричной (или d-автоустойчивой).

Для любого 1 < п < uj существуют примеры моделей, вычислимая размерность которых равна п. Более того, множество таких примеров найдено среди моделей из известных классов. См., например, [4], [5], [6], [7], [9], [12], [55], [61].

Теорема 0.0.4 (С. Гончаров, В. Харизанова, Дж. Найт, Ч. МакКой, Р. Миллер, Р. Соломон в [46]). Для каждого непредельного ординала а существует вычислимая модель, которая Д^ категорична, но не относительно Д® категорична.

Теорема 0.0.5 (Дж. Чисхолм, Е. Фокина, С. Гончаров, В. Харизанова, Дж. Найт, С. Миллер в [37]). Для каждого вычислимого предельного ординала а существует вычислимая модель Л такая, что Л Д® категорична, но не относительно Л® категорична.

Связанный с этим вопрос заключается в изучении вычислимой размерности обогащения конечным числом констант вычислимо категоричной модели. Следующие результаты показывают, что вычислимая категоричность сохраняется не всегда.

Теорема 0.0.6 (С. Гончаров, Б. Хусаинов, П. Чолак, Р. Шор в [44]). Для каждого натурального к > 0 существует вычислимо категоричная модель Л и элемент а Е |.А|, такие, что вычислимая размерность (Л, а) равна к.

Теорема 0.0.7 (Д. Хиршфилд, Б. Хусаинов, Р. Шор в [50]). Существует вычислимо категоричная модель Л и элемент a G \Л\ такие, что вычислимая размерность (Л, а) равна и.

Определение 0.0.8. Если d — некоторая степень, то модель Л с вычислимым носителем |Д| называется вычислимой, если ее атомная диаграмма d-вычислима. Степенью Л, обозначаемой через deg(„4), называется наименьшая степень d (она всегда существует) такая, что Л d-вычислима. Изоморфизм из В на d-вычислимую модель с вычислимым носителем называется d-вычислимым представлением модели В. Степенью представления будем называть степень образа представления. Если у В есть d-вычислимое представление, то также будем называть ее d-вычислимо представимой

Определение 0.0.9. Спектром степеней DgSp(.4) счетной модели Л называется множество всех степеней представлений Л.

Теорема 0.0.8 (Т. Сламан в [63]; С. Венер в [65]). Существует модель Л, имеющая представления в каждой степени кроме 0 (т. е. DgSp(.A) = V — {0}; где Т> — множество всех степеней).

Теорема 0.0.9 (С. Гончаров, В. Харизанова, Дж. Найт, Ч. МакКой, Р. Миллер, Р. Соломон в [46]). Для каждого вычислимого последовательного ординала а существует модель, имеющая представления в точности в тех степенях множеств X, для которых Д°(.Х) не равно Д®. В частности, для каждого конечного'п существует модель с представлениями в точности в не-low„ степенях.

Другой подход к изучению вычислимых представлений модели — сравнение образов дополнительных отношений в этих представлениях. В таком случае получаем понятия спектра степеней отношений на моделях.

Определение 0.0.10. Спектром степеней DgSp^(U) отношения U на носителе вычислимой модели Л называется множество степеней образов U во всех вычислимых представлениях Л.

Существует множество интересных примеров вычислимых моделей и отношений на их носителях, которые имеют различные спектры степеней (см. [47], [53], и др.).

Теорема 0.0.10 (С. Гончаров, В. Харизанова, Дж. Найт, Ч. МакКой, Р. Миллер, Р. Соломон в [46]). Для каждого вычислимого непредельного ординала а существует вычислимая модель и отношение на ней, которое является наследственно но не относительно наследственно Е®.

Теорема 0.0.11 (Дж. Чисхолм, Е. Фокина, С. С. Гончаров, В. Харизанова, Дж. Найт, С. Миллер в [37]). Для любого вычислимого предельного ординала а существует вычислимая модель Л и некоторое Е® отношение Р на этой вычислимой модели такие, что Л категорична, но отношение Р не Е^.-вычислимо определимо.

Эффективные трансформации классов моделей из [40] и [51] показывают, что многие вопросы об алгоритмических свойствах моделей могут быть сведены к вопросам о свойствах графов. С другой стороны, мы можем эффективно перейти от графов к моделям произвольной конечной сигнатуры, содержащей хотя бы один n-местных предикатный символ, где п >2. Таким образом, в графах могут быть реализованы все алгоритмические свойства произвольных вычислимых моделей, в частности, перечисленные выше. Кроме того, графы являются очень важным инструментом для изучения конкретных классических классов объектов, таких, как алгебры групп и колец, и других специальных классов моделей.

Скажем несколько слов о структуре диссертации.

В главе 1 рассматриваются два метода работы с моделями, вычислимыми относительно заданных степеней. Эти методы позволяют преобразовывать построенные модели и классы моделей, изменять их сигнатуру, понижать их алгоритмическую сложность, сохраняя при этом многие алгоритмические и теоретико-модельные свойства. Методы используются для получения дальнейших результатов диссертации. Первый метод позволяет равномерно понижать сложность моделей, сохраняя при этом необходимые теоретико-модельные и алгоритмические свойства моделей. Метод основан на понятиях маркеровских 3- и V-расширений предикатов и моделей [58], а также однозначного представления предикатов [15]. Второй метод позволяет равномерно переходить от моделей произвольной конечной сигнатуры к графам с сохранением нужных свойств и основан на идеях [40] и [51]. Более того, в главе 1 предлагаются некоторые достаточные условия, выполнение которых гарантирует сохранение необходимых алгоритмических и теоретико-модельных свойств при переходах к моделям новых сигнатур.

Глава 2 посвящена изучению вопроса существования вычислимых моделей с различными спецификациями, т. е. с заданными алгоритмическими и теоретико-модельными свойствами, а также вопроса сложности теорий таких моделей. Рассматриваются такие важные классы теорий, как класс несчетно категоричных и класс счетно-категоричных теорий. Как было показано выше, вопрос об алгоритмических свойствах таких теорий и их моделей представляет особый интерес. В главе 2 мы рассматриваем вопрос существования категоричных теорий высокой алгоритмической сложности с вычислимыми моделями. Более точно, по произвольной арифметической тыоринговой степени мы строим примеры категоричных теорий в точности заданной сложности, имеющих вычислимые модели.

В главе 3 исследуются взаимосвязи между определимостью и вычислимостью моделей. Изучение алгоритмической сложности различных важных классов вычислимых моделей проводится через оценку их индексных множеств в арифметической иерархии, в иерархии Ершова ([2], [18]). В рамках этого подхода для произвольной арифметической степени d мы исследуем алгоритмическую сложность следующих естественных классов вычислимых моделей: d-разрешимых моделей, d-разрешимых моделей со счетно-категоричной теорией, вычислимых моделей с разрешимой теорией. Кроме того, как приложение полученных результатов, устанавливаем аналогичные точные оценки индексных множеств для моделей из классов неориентированных графов, частичных порядков и решеток.

В главе 4 исследуется вопрос о переносе алгоритмических свойств, полученных для моделей из одних классов, на модели из других классов. Предлагается метод кодирования моделей, позволяющий гарантировать сохранение многих алгоритмических и теоретико-модельных свойств при переходе от графов к моделям, сигнатура которых содержит два одноместных функциональных символа. В частности, сохраняется вычислимость моделей, разрешимость моделей и их теорий, счетная категоричность. Также сохраняется d-вычислимая размерность моделей, спектр степеней DgSp(.A) счетной модели Л и спектр степеней дополнительных отношений на модели. Полученные результаты, в совокупности с ранее известными, дают информацию о многих алгоритмических свойствах классов моделей произвольных богатых сигнатур, т. е. сигнатур, содержащих n-местный предикатный или функциональный символ, где п > 2, или хотя бы два одноместных функциональных символа.

В работе используются стандартные понятия и обозначения из теории моделей и теории вычислимости, например, такие, как арифметическая иерархия, концепция Х-вычислимых множеств (т. е. множеств вычислимых с оракулом X), оператор скачка X',d' для подмножеств X С ш и степеней d. Ссылки следуют книгам [22] по теории моделей, [28] по теории вычислимых функций, и [10], [32] по теории вычислимых моделей.

1. Лрсланов М. М. Полнота в арифметической иерархии и неподвижные точки // Алгебра и логика, т. 28, N1, 1989, с. 3-17.

2. Арсланов М. М. Иерархия Ершова. Казань: Казанский государственный универститет, 2007, 86 с.

3. Гончаров С. С. Конструктивные модели о^-категоричных теорий // Математические Заметки, т. 23, N6, 1978, с. 885-888.

4. Гончаров С. С. Проблема числа неавтоэквивалентных конструктиви-заций // Алгебра и логика т. 19, N6, 1980, с. 621-639.

5. Гончаров С. С. Группы с конечным числом конструктивизаций // Доклады АН СССР, т. 256, N2, 1981, с. 269-272.

6. Гончаров С. С. Предельно эквивалентные конструктивизации // Математическая логика и теория алгоритмов, Труды Института Математики, т. 2, Новосибирск: Наука, Сиб. отделение, 1982, с. 4-12.

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

8. Гончаров С. С. О двух проблемах тьюринговой сложности для сильно минимальных теорий //В печати в Доклады РАН.

9. Гончаров С. С., Дзгоев В. Д. Автоустойчивость моделей // Алгебра и логика, т. 19 N1, 1980, с. 45-58.

10. Гончаров С. С., Ершов Ю. J1. Конструктивные модели, Новосибирск: Научная книга, 1999, 360 с.

11. Гончаров С. С., Найт Док. Ф. Вычислимые структурные и антиструктурные теоремы // Алгебра и логика, т. 41, N6, 2002, с. 639-681.

12. Гончаров С. С., Молоков А. В., Романовский Н. С. Нильпотентные группы конечной алгоритмической размерности // Сиб. Мат. Ж., т. 30, N1, 1989, с. 82-88.

13. Гончаров С. С., Хусаинов Б. М. Сложность категоричных теорий с вычислимыми моделями // Доклады РАН, т. 385, 3, 2002, с. 299-301.

14. Гончаров С. С., Хусаинов В. М. О сложности теорий вычислимых ^i-категоричных моделей // Вестник НГУ, Мат.-Мех.-Информ., т. 1, N2, 2001, с. 63-76.

15. Гончаров С. С., Хусаинов Б. М. Сложность теорий вычислимых категоричных моделей // Алгебра и логика, т. 43, N6, 2004, с. 365-373.

16. Добрица В. П. Сложность индексного множества конструктивной модели // Алгебра и логика, т. 22, N4, 1983, с. 372-381.

17. Ершов Ю. JI. Конструктивные модели // Избранные вопросы алгебры и логики, Новосибирск: Наука, 1973, с. 111-130.

18. Ершов Ю. Л. Теория нумераций.3, Новосибирск: Новосибирский государственный университет, 1974.

19. Ершов Ю. Л. Теория нумераций, М.: Наука, 1977.

20. Калверт У., Каммингс Д., Найт Дж. Ф., Миллер С. Сравнение классов конечных структур // Алгебра и логика, т. 43, N6, 2004, с. 666-701.

21. Калверт У., Харизанов В., Найт Дж. Ф., Миллер С. Индексные множества вычислимых моделей // Алгебра и логика, т. 45, N5, 2006, с. 538-574.

22. Кейслер Г., Чэн Ч. Ч. Теория моделей, М.: Мир, 1977, 614 с.

23. Кудайбергенов К. 3. О конструктивных моделях неразрешимых теорий // Сиб. Мат. Ж., т. 21, N5, 1980, с. 155-158.

24. Мальцев А. И. Конструктивные алгебры // Успехи мат. наук, т. 16, N3, 1961, с. 3-60.

25. Мальцев А. И. О рекурсивных абелевых группах // Доклады Акад. наук СССР, т. 146, N5, 1962, с. 1009-1012.

26. Нуртазин А. Т. Вычислимые классы и алгебраический критерий автоустойчивости // Канд. диссертация, Институт математики и механики, Алма-Ата, 1974.

27. Перетятъкин М. Г. О полных теориях с конечным числом счетных моделей // Алгебра и логика, т. 12, N5, 1973, с. 550-576.

28. Роджерс X. Теория рекурсивных функций и эффективная вычислимость, М.: Мир, 1972, 624 с.

29. Соар Р. И. Вычислимо перечислимые множества и степени. Казань: Казанское математическое общество, 2000, 576 с.

30. Хисамиев Н. Г. Сильно конструктивные модели разрешимой теории // Изв. Акад. Наук Казах. ССР, Сер. Физ.-Мат., т. 35, N1, 1974, с. 8384.

31. Хусаинов В., Шор Р.А. Решение проблемы Гончарова-Эша и проблемы спектра в теории вычислимых моделей // Доклады РАН, т. 371, N1, 2000, с. 30-31.

32. Ash С. J., Knight J. F. Computable Structures and the Hyperarithmetical Hierarchy. Studies in Logic and the Foundations of Mathematics, 144. North-Holland Publishing Co., Amsterdam, 2000.

33. Ash С. J., Knight J. F. Pairs of recursive structures // Ann. Pure Appl. Logic, v. 46, N3, 1990, pp. 211-234.

34. Baldwin J., Lachlan A. On Strongly Minimal Sets //J. Symb. Logic, v. 36, 1971, pp. 79-96.

35. Calvert W. The isomorphism problem for classes of computable fields // Archive for Mathematical Logic, 43, N3, 2004, pp. 327-336.

36. Calvert W. The isomorphism problem for computable Abelian ^-groups of bounded length // J. Symb. Logic, v. 70, N1, 2005, pp. 331-345.

37. Chisholm J., Fokina E., Gocharov S., Harizanov V., Knight J., Miller S. Intrinsic bounds on complexity and definability at limit levels // Submitted to Journal of Mathematical Logic.

38. Csima B. F., Montalban A., Shore R. A. Boolean algebras, Tarski invariants, and index sets // Notre Dame J. Formal Logic, v. 47, N1, 2006, pp. 1-23.

39. Fokina E. B. Index Sets for some classes of structures // принята в Ann. Pure Appl. Logic.

40. Handbook of Recursive Mathematics: In 2 v./ Ed. Yu. L. Ershov, S. S. Goncharov, A. Nerode, J. Remmel, New York: Elsevier, 1998.

41. Frohlich AShepherdson J. Effective procedures in field theory // Philos. Trans. Roy. Soc. London, Ser. A, v. 248, 1956, pp. 407-432.

42. Goncharov S., Khoussainov B. Open problems in the theory of constructive algebraic systems // Computability theory and its applications (Boulder, CO), 1999, pp. 145-170.

43. Cholak P., Goncharov S. S., Khoussainov В., Shore R. A. Computably categorical structures and expansions by constants //J. Symbolic Logic, v. 64, N1, 1999, 13-37.

44. Goncharov S., Harizanov V., Laskowski M., Lempp S., McCoy C. Trivial, strongly minimal theories are model complete after naming constants // Proceedings of American Mathematical Society, v. 131, N12, 2003, pp. 3901-3912.

45. Goncharov S., Harizanov V., Knight J. F., McCoy C., Miller R., Solomon R. Enumerations in computable structure theory // Annals of Pure and Applied Logic, v. 136, N3, 2005, pp. 219-246.

46. Harizanov V. The possible Turing degree of the nonzero member in a two element degree spectrum // Ann. Pure Appl. Logic, v. 60, N1, 1993, pp. 1-30.

47. Harrington L. Recursively Presentable Prime Models //J. Symbolic Logic, v. 39, 1974, pp. 305-309.

48. Hirschfeldt D. R., Khoussainov В., Semukhin P. An Uncountably Categorical Theory Whose Only Computably Presentable Model Is Saturated // Notre Dame J. Formal Logic, v. 47, N1, 2006, pp. 63-71.

49. Hirschfeldt D. R., Khoussainov В., Shore R. A. A computably categorical structure whose expansion by a constant has infinite computable dimension // J. Symbolic Logic, v. 68, N4, 2003, pp. 1199-1241.

50. Hirschfeldt D. R., Khoussainov В., Shore R. A., Slinko A., Degreespectra and computable dimensions in algebraic structures // Ann. Pure Appl. Logic, v. 115, N1-3, 2002, pp. 71-113.

51. Khoussainov В., Nies A., Shore R. A. On Recursive Models of Theories // Notre Dame J. Formal Logic, v. 38, N2, 1997, pp. 165-178.

52. Khoussainov В., Shore R. A. Computable isomorphisms, degree spectra of relations, and Scott families // Ann. Pure Appl. Logic, v. 93, N1-3, 1998, pp. 153-193.

53. Knight J. F. Nonarithmetical Ko-categorical Theories with Recursive Models // J. Symbolic Logic, v. 59, N1, 1994, pp. 106-112.

54. Lempp S., McCoy C., Miller R.; Solomon R. Computable categoricity of trees of finite height // J. Symbolic Logic, v. 70, N1, 2005, pp. 151-215.

55. Lerman M., Schmerl J. Theories With Recursive Models //J. Symbolic Logic, v. 44, N1, 1979, pp. 59-76.

56. Marker D. Non-£n-axiomatizable almost strongly minimal theories // J. Symbolic Logic, v. 54, N3, 1989, pp. 921-927.

57. Nies A. A new spectrum of recursive models // Notre Dame J. Formal Logic, v. 40, N3, 1999, pp. 307-314.

58. Rabin M. 0. Effective computability of winning strategies // Contributions to the Theory of Games, v. 3, Princeton Univ. Press, Princeton, 1957, pp. 147-157.

59. Remmel J. В. Recursively categorical linear orderings // Proc. Amer. Math. Soc., v. 83, N2, 1981, pp. 387-391.

60. Schmerl J. H. A decidable Ko"categorical theory with a nonrecursive Ryll-Nardzewski function // Fund. Math. v. 98, N2, 1978, pp. 121-125.

61. Slaman T. A. Relative to any nonrecursive set // Proc. Amer. Math. Soc., v. 126, N7, 1998, pp. 2117-2122.

62. Vaught R. L. Sentences true in all constructive models // J. Symbolic Logic, v. 25, N1, 1960, pp. 39-58.

63. Wehner S. Enumerations, countable structures, and Turing degrees j j Proc. Amer. Math. Soc., v. 126, N7, 1998, pp. 2131-2139.

64. White W. On the complexity of categoricity in computable structures // Mathematical Logic Quarterly, v. 49, N6, 2003, pp. 603-614.Работы автора по теме диссертации

65. Fokina Е. В. On degrees of uncountably categorical theories with computable models If Proceeding of Workshop "Computability and models Almaty, June 24-28, 2002, pp. 32.

66. Фокина E. Б. О сложности категоричных теорий с вычислимыми моделями // Вестник НГУ, Мат.-Мех.-Информ., т. 5, N2, 2005, с. 78-86.

67. Фокина Е. Б. О спектрах вычислимых моделей // Вестник НГУ, Мат.-Мех.-Информ., т. 6, N6, 2006, с. 69-73.

68. Fokina Е. В. Arithmetical Turing Degrees and Categorical Theories of Computable Models // Mathematical Logic in Asia. Proceedings of the 9th Asian Logic Conference, 2006, pp. 58-69.

69. Фокина E. Б. Индексные множества разрешимых моделей // Сиб.Мат.Ж., т. 48, N5, 2007, с. 1167-1179.

70. Фокина E. Б. Алгоритмические свойства моделей сигнатуры с двумя одноместными функциональными символами // Вестник НГУ, Мат.-Мех.-Информ., т. 8, N1, 2008, с. 90-101.

71. Calvert W., Fokina Е., Goncharov S. S., Knight J. F., Kudinov О. V., Morozov A. S., Puzarenko V. Index sets for classes of high rank structures // J. Symbolic Logic, v. 72, N4, 2007, pp. 1418-1446.