Введение к работе
Объект исследования и актуальность темы К числу фундаментальных проблем, изучаемых в математической логике, относится исследования природы разрешимости и неразрешимости алгоритмических проблем на алгебраических структурах В рамках теории вычислимых моделей разработаны различные подходы к исследованию этой проблемы Основы теории вычислимых моделей были заложены в 50-е годы в работах А И Мальцева [8j, Р Воота [24], А Фролиха и Дж Шефердсона [12], О Рабина [23] Существенный вклад в развитие теории вычислимых моделей был сделан Ю Ершовым Определенное им понятие сильно конструктивной модели позволило изучать алгоритмические свойства моделей разрешимых элементарных теорий и построіп ь теорию разрешимых моделей Основные направления исследований в теории вычислимых моделей были отражены в двухтомном издании "Handbook of Recursive Mathematics" [15] под редакцией Ю Ершова, С Гончарова, А Нероуда, Дж Реммела, а также в обзорах по теории вычислимых моделей С С Гончарова и Б М Хусаинова [14] и С С Гончарова [13]
В теории вычислимых моделей одной из фундаментальных проблем является проблема существования вычислимых моделей с различными свойствами, заданными спецификацией в некотором формальном языке К числу наиболее актуальных проблем, привлекающих внимание специалистов, в настоящее время относятся проблемы существования вычислимых моделей для теорий с малым числом счетных моделей, в частности, категоричных в некоторой мощности, эренфойхтовых и т п
Известно, что в общем случае любая непротиворечивая разрешимая теория Т имеет разрешимую модель А Более того, такая модель А может быть построена эффективно по Т С другой стороны, если у теории существует вычислимая модель, то такая теория разрешима относительно 0W Добавим еще, что существуют примеры даже конечно аксиоматизируемых, а значит, вычислимо перечислимых теорий, которые не имеют вычислимых моделей [2]
Наиболее значительные результаты об условиях существования вычислимых моделей были получены для счетно-категоричных теорий В
[21] М Лерман и Дж Шмерл дали достаточные условия, чтобы счетно-категоричная теория имела вычислимую модель Одним из условий являлась арифметическая сложность теории В [20] Дж Найт усилила этот результат, после чего для существования вычислимой модели уже не предполагалась арифметичность теории Однако, долгое время все известные примеры счетно-категоричных теорий имели невысокую сложность Естественно возникающий вопрос о существовании счетно-категоричных теорий, удовлетворяющих условиям теорем из [20] или [21] для достаточно больших п, был задан Дж Найт и некоторое время оставался открытым С Гончаров и Б Хусаинов в [5] для любого п построили пример счетно-категоричной теории с вычислимой моделью сложности О"
В случае несчетно категоричных теорий первого порядка Л Харринг-тон в [16] и Н Хисамиев в [10] показали, что на самом деле все счетные модели разрешимой несчетно категоричной теории разрешимы Этот результат побудил изучать вычислимые модели Ni-категоричных неразрешимых теорий Если Т несчетно категорична, но неразрешима, то некоторые ее счетные модели могут быть вычислимы, а другие нет Например, С Гончаров в [1] показал, что существует Nj-категоричная теория, вычислимая с оракулом 0', для которой вычислима только простая модель Позже К Ку-дайбергенов обобщил этот результат в [7], построив для любого п пример Ягкатегоричной, вычислимой с оракулом 0' теории Т, у которой вычислимы лишь первые п моделей В ряду [17], [19], [22] последовавших за этим примеров Ni-категоричных теорий, имеющих вычислимую модель, все теории были разрешимы с оракулом О". С Гончаров и Б Хусаинов в [4, 5] построили для любого п > 1 пример Ni-категоричной теории, эквивалентной по Тьюрингу степени 0" и имеющей вычислимую модель
Другой вопрос в исследовании алгоритмических свойств алгебраических систем связан с решением проблемы определимости и ее степени сложности, и, на этой основе, получением верхней границы алгоритмической сложности Также представляет фундаментальный интерес задача построения нижней оценки алгоритмической сложности рассматриваемой алгебраической проблемы, на основе теории вычислимых представлений алгебраических систем с различными свойствами, задаваемыми на языке
спецификаций В рамках этой проблемы важно исследовать как отдельные классические и производные от них алгебраические структуры, так и их естественные классы и подклассы, структуры, семантики и алгоритмические проблемы языков спецификаций Это направление исследований является актуальным и привлекает внимание многих специалистов, таких как Ю Ершов, С Гончаров, А Морозов, В Добрица, Дж Найт, С Лемпп, А Нис, В Харизанова, Б Хусаинов и другие
Возможные методы изучения связей между определимостью и вычислимостью описаны в работе С Гончарова и Дж Найт [3] Один из таких методов связан с понятием индексного множества из теории нумераций Исследования по связи алгоритмических свойств индексных множеств и структурных свойств семейств множеств является классическим вопросом теории вычислимых нумераций Этот подход оказывается эффективным и при изучении классов вычислимых моделей через вычислимые нумерации классов моделей данной сигнатуры По известному результату А Нуртази-на [9] существует универсальная вычислимая нумерация всех вычислимых моделей конечной предикатной сигнатуры а Другими словами, существует равномерно вычислимая последовательность {Ап}пєи вычислимых моделей сигнатуры а, такая, что каждая вычислимая модель В сигнатуры а изоморфна некоторой An из последовательности (при этом п находится эффективно по В) Назовем индексным множеством, 1{К) класса К множество всех номеров п., соответствующих вычислимым моделям из К в данной нумерации В универсальной нумерации свойства сложности классов вычислимых моделей характеризуются через сложность их индексных множеств в этой нумерации Т е задача изучения связей между алгоритмическими и теоретико-модельными свойствами различных естественных классов моделей сводится к изучению сложности индексных множеств для этих классов В общем случае универсальные нумерации не существуют В этом случае наряду с вычислимыми моделями необходимо рассматривать и частичные вычислимые модели, для которых также можно построить универсальную вычислимую нумерацию
При получении результатов об алгоритмических свойствах моделей с интересными алгебраическими и теоретико-модельными свойствами часто
возникает вопрос о существовании моделей с подобными алгоритмическими свойствами в других важных классах Во многих случаях оказывается возможным осуществить перенос таких результатов, полученных для определенных моделей, на модели из других классов Один из возможных путей получить подобные обобщения заключается в кодировании исходной модели в модели из другого класса таким образом, чтобы сохранить интересующие алгоритмические свойства Наглядной иллюстрацией применения этих методов могут послужить работы [13] и [18], где предлагаются методы кодирования моделей, позволяющие свести алгоритмические вопросы для произвольных моделей к аналогичным вопросам для графов Интересным представляется вопрос об обобщении подобных результатов на классы моделей других сигнатур, в частности получение результатов для произвольных богатых сигнатур, т е сигнатур, содержащих хотя бы один бинарный предикатный или функциональный символ, или хотя бы два унарных функциональных символа
Цель работы Исследовать вопрос существования вычислимых моделей с фиксированными теоретико-модельными и алгоритмическими свойствами их теорий для случая счетно-категоричных и несчетно категоричных теорий Изучить алгоритмические свойства различных классов вычислимых моделей через их индексные множества Получить результаты об алгоритмических свойствах моделей различных сигнатур
Методы исследования В работе используются методы теории вычислимых нумераций [6], обобщения метода понижения сложности моделей из [5] и метода сведения сигнатур, разработанного в [13] Кроме того, разрабатываются различные методы построения моделей с заданными теоретико-модельными и алгоритмическими свойствами
Научная новизна Все результаты диссертации являются новыми и снабжены подробными доказательствами, они опубликованы автором диссертации в научных журналах из перечня ВАК ведущих рецензируемых научных журналов и изданий, в которых должны быть опубликованы основные научные результаты диссертации
Практическая ценность Работа носит теоретический характер Ее результаты могут найти применение в дальнейших исследованиях по теории
вычислимых моделей
Основные результаты В работе получены следующие результаты
Построены примеры счетно-категоричных и несчетно категоричных теорий произвольной арифметической сложности, имеющих вычислимые модели В частности, дан положительный ответ на вопрос Дж Найт о существовании счетно-категоричных теорий произвольной сложности с вычислимыми моделями для случая арифметических теорий
Получены точные оценки m-степеней индексных множеств для следующих классов
разрешимых моделей,
разрешимых моделей со счетно-категоричной теорией,
вычислимых моделей с разрешимой теорией
Кроме того, получены аналогичные оценки для вычислимых моделей из классов неориентированных графов, частичных порядков и решеток
3 Получен ряд результатов об алгоритмических свойствах классов мо
делей, сигнатура которых содержит два унарных функциональных
символа
Апробация Результаты диссертации были представлены на XL Международной научной студенческой конференции (Новосибирск, 2002), на Международной конференции "Мальцевские чтения" (Новосибирск, 2003 и пленарный доклад в 2007), на Международной конференции "Methods of Logic m Mathematics III" (Санкт-Петербург, 2006), на 2-ой Студенческой логической конференции (Нью-Йорк, США, 2007), на Международной конференции "Computabihty in Europe" (Сиена, Италия, 2007), на Международной конференции "Вычислимые модели и нумерации" (Новосибирск, 2007) Кроме того, результаты докладывались на семинаре "Конструктивные модели" Новосибирского государственного университета и Общеинститутском математическом семинаре Института математики СО РАН
Публикации Основные результаты диссертации опубликованы в работах автора [25]-[33]
Структура и объем работы Диссертация состоит из введения, четырех глав, разбитых на параграфы, и списка литературы Работа изложена на 83 страницах, список литературы содержит 74 наименования
