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

• Фокина, Екатерина Борисовна
• кандидат физико-математических наук
• 2008

Оглавление диссертации кандидат физико-математических наук Фокина, Екатерина Борисовна

Введение

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] по теории вычислимых моделей.

Список литературы диссертационного исследования кандидат физико-математических наук Фокина, Екатерина Борисовна, 2008 год

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.