На правах рукописи
ПАВЛОВСКИЙ Евгений Николаевич
Оценка алгоритмической сложности
классов вычислимых моделей
01.01.06 математическая логика, алгебра и теория чисел
Автореферат
диссертации на соискание учной степени
е
кандидата физико-математических наук
Новосибирск 2008
Работа выполнена в Новосибирском государственном университете.
Научный руководитель: доктор физико-математических наук профессор, член-корреспондент РАН Гончаров Сергей Савостьянович
Официальные оппоненты: доктор физико-математических наук, профессор Хисамиев Назиф Гарифуллинович доктор физико-математических наук, профессор Добрица Вячеслав Порфирьевич
Ведущая организация: Казанский государственный университет
Защита состоится “ 27 ” июня 2008 г. в 15 ч. 00 мин. на заседании Диссертационного Совета Д 003.015.02 при Институте математики им. С.Л. Соболева СО РАН, пр-т Ак.Коптюга, 4, г.Новосибирск, 630090.
С диссертацией можно ознакомиться в библиотеке Института математики им.
С.Л. Соболева СО РАН.
Автореферат разослан “26”мая 2008 г.
Учный секретарь диссертационного совета е кандидат физико-математических наук Ряскин А.Н.
ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ
Актуальность темы. Академик А.И.Мальцев предложил использовать нумерации как базовую концепцию для изучения алгоритмических свойств алгебраических систем и их подмножеств, в частности таких классических систем, как группы, кольца и поля.
В рамках теории конструктивных моделей на сегодня разработаны различные подходы к исследованию алгоритмической и структурной сложности вычислимых моделей и отношений. Задача изучения структурных свойств вычислимых моделей и классов вычислимых моделей рассматривается как в рамках изучения сложности их ранга и формул Скотта, так и через индексные множества в универсальной нумерации вычислимых структур. Исследования в этом направлении были начаты в работах А.И.Мальцева, А.В.Кузнецова, Д.Макинси, К.Эша и А.Нероуда. Одним из продуктивных методов здесь является метод определимости в рекурсивном фрагменте языка бесконечных формул и задача изучения выразительных возможностей этого фрагмента языка в отношении описания свойств моделей. В этой связи актуальной является проблема нахождения формул и рангов Скотта для конкретных алгебраических структур и устойчивых относительно автоморфизмов отношений на них, исследование влияния на ранг Скотта константных и других естественных обогащений для алгебр, различных операторов над моделями, а также соотношений рангов и сложности структур для образов и прообразов. Этими проблемами занимались как зарубежные, так и российские математики, такие как Ершов, Гончаров, Каллибеков, Селиванов, Арсланов, Перетятькин, Добрица, Хисамиев и другие. Одно из направлений исследований связано с решением проблемы определимости и ее степени сложности в языке бесконечных формул.
На этой основе могут быть получены верхние границы алгоритмической сложности, на основе теории вычислимых представлений алгебраических систем с различными свойствами, задаваемыми на декларативном языке спецификаций, нижние оценки алгоритмической сложности рассматриваемой алгебраической проблемы.
К настоящему времени известно достаточно много результатов об индексных множествах моделей, классов моделей, теорий [1], [2], [3], [4], [5], [6], [7], [8], [9]. Большую роль индексные множества сыграли в общей теории вычислимости и вычислимых нумераций (кн. Ю.Л.Ершов. Теория нумераций [10]). Открытые проблемы этого направления привлекли специалистов и обсуждались на нескольких логических конференциях, в частности, приведены в работе Гончарова и Хусаинова [11], Гончарова и Найт [12].
Гончаров и Найт предложили [12] общие подходы для изучения структурных и алгоритмических свойств классов вычислимых моделей на основе исследования индексных множеств. Для многих классов индексное множество лежит на низком уровне гиперарифметической иерархии: множество I(K) является 0 -множеством для следующих классов: линейные порядки, булевы алгебры, абелевы p-группы, модели эквивалентности, векторные пространства над Q, модели фиксированного вычислимого языка.
В работе [6] даны точные оценки для индексных множеств конструктивных моделей с заданными условиями автоэквивалентности рассматриваемых конструктивизаций. В работе [13] дана точная оценка индексного множества для локальных конусов. Ряд работ В.П. Добрицы посвящено изучению различных индексных множеств конструктивных моделей [6], [14], [15], [13], [16].
Для некоторых классов индексное множество гиперарифметично:
(Клини, Спектор) множество I(K) является 1 -полным для следующих классов: полные порядки, суператомные булевы алгебры, редуцированные p-группы.
Для решения вопроса о существовании вычислимой классификации классов в [12] предложен подход оценки проблемы изоморфизма в терминах индексных множеств и приводятся доказательства оценок проблемы изоморфизма для некоторых важных классов. Так, например, множество E(K) проблемы изоморфизма является 1 -полным для следующих классов K: абелевы p-группы, деревья, булевы алгебры, линейные порядки, произвольные модели языка, содержащего по крайней мере один предикатный символ местности большей или равной 2. Проблемы изоморфизма также исследуются в работах [1], [2] для векторных пространств, алгебраических полей фиксированной характеристики, [17] для классов конструктивных Iалгебр, [18] для классов автоматных моделей. Подход через индексные множества также позволяет оценить сложность семантических классов предложений, целая глава в монографии [19] посвящена оценкам алгоритмической сложности классов предложений, используемых в теории моделей и логике.
Настоящая работа посвящена исследованию вопроса о характеризации известных классов моделей через оценку сложности индексных множеств классов вычислимых моделей. С этой точки зрения можно рассмотреть классы специальных моделей (простые, однородные, насыщенные, универсальные), классы моделей с заданными свойствами теорий (теория допускает простую модель, счётная-категоричность теории, несчётная категоричность, Эренфойхтовость, разрешимость теории), классы моделей с фиксированными алгоритмическими свойствами (разрешимые модели, автоустойчивые, модели конечной(бесконечной) алгоритмической размерности, модели с вычислимым рангом Скотта, с невычислимым рангом Скотта, d-разрешимые счётно-категоричные модели, d-разрешимые простые модели). Решение вопроса об оценке сложности этих множеств находится в русле проблем, обсуждаемых в докладе Гончарова и Хусаинова [11], а именно с проблемами существования конструктивных моделей для определённых классов теорий, а также о максимальной сложности некоторых теорий, имеющих конструктивные модели [11, Problems 3, 5, 11, Question 6].
Из перечисленных классов уже построены точные оценки для класса d-разрешимых моделей (0,d ), d-разрешимых счётно-категоричных модеd лей (3 ) [9]. Для класса универсальных вычислимых моделей получена нижняя оценка 1 [18]. Е.Б. Фокиной также была получена точная оценка индексного множества моделей, имеющих разрешимые теории 2 [20].
В последнее время в совместной работе российских и зарубежных специалистов был получен важный результат об индексных множествах структур высокого ранга Скотта.
В данной работе применён подход понижения вычислительной сложности в теоретико-модельных конструкциях (подход Гончарова-Хусаинова на основе конструкции Маркера) [22] для получения нижних оценок алгоритмической сложности вычислимых представителей естественных классов моделей. В работе использованы синтаксические характеризации классов моделей, обладающих -категоричными теориями (РылльНардзевский [23]), обладающих 1 -категоричными теориями (ЛахланБалдвин [24], Еримбетов [25]), современные результаты о синтаксической характеризации Эренфойхтовых теорий (Судоплатов, [26]). Для тех классов, для которых получены точные оценки, фактически подтверждается тезис выдвинутый в работе [3] о том, что точная оценка индексного множества даётся некоторым оптимальным описанием модели. В настоящей работе доказано, что упомянутые синтаксические характеризации обладают наименьшей возможной вычислительной сложностью, т.е. являются наилучшими синтаксической характеризациями с точки зрения вычислимости.
Цель работы. Анализ взаимосвязи между структурными и алгоритмическими свойствами классов вычислимых моделей.
Общая методика исследований. В работе анализируется взаимосвязь определимости классов моделей с алгоритмической их сложностью посредством построения точных оценок индексных множеств классов вычислимых моделей в соответствующих иерархиях алгоритмической сложности множеств, а также с помощью явного построения алгоритмов, или доказательства отсутствия таковых для определённых классов задач.
Используется аппарат теории моделей, широко используются теоретикомодельные функторы, предложенные Гончаровым [31], [22], синтаксические характеризации теоретико-модельных свойств [23],[26], [25], методы теории вычислимости, теории квазимногообразий.
Научная новизна. В работе получены следующие результаты:
- для классов моделей, определимых квазитождествами в сигнатуре унаров показано существование алгоритма определяющего наличие свойства конечности в свободной структуре класса, для более сложных сигнатур показано, что общего алгоритма не существует;
- на основе введенного понятия маркеровского свойства получена универсальная нижняя оценка сложности (0 ) для различных классов вычислимых моделей;
- построены точные оценки следующих классов вычислимых моделей:
простые модели, d-разрешимые простые модели (относительно арифметической Тьюринговой степени d), модели с Эренфойхтовой теорией, модели, теории которых допускают бесконечное число счетных моделей;
- построены верхние и нижние оценки следующих классов: модели с -категоричной теорией, модели с 1 -категоричной теорией.
Все основные результаты работы являются новыми, опубликованы.
Теоретическая и практическая ценность. Все результаты работы теоретические. Результаты работы могут быть использованы для построения классификации вычислимых моделей.
Апробация работы. Результаты работы были доложены на Девятой Азиатской логической конференции (Новосибирск, 2005), на Международной научно-практической студенческой конференции "Студент и научно-технический прогресс"(Новосибирск, 2003, 2004, 2006), на Логическом Коллоквиуме (Вроцлав, Польша, 2007), на Летней международной школе по вычислимым моделям и нумерациям (Новосибирск, 2007), С результатами работы автор неоднократно выступал на семинаре "Конструктивные модели"(Новосибирск, НГУ, 2003 – 2008), семинаре "Алгебра и логика"(Новосибирск, НГУ, 2003, 2005).
Публикации. Основные результаты опубликованы в работах [35]источники входят в перечень ВАК ведущих рецензируемых научных журналов и изданий, в которых должны быть опубликованы основные научные результаты диссертации.
Объём и структура диссертации. Диссертация содержит 95 страниц и состоит из введения, четырёх глав, заключения, библиографии. Основные утверждения диссертации названы теоремами. Нумерация теорем сделана двумя индексами: первый означает номер главы, второй - номер теоремы внутри главы. Все остальные утверждения и определения занумерованы тройками индексов, из которых первый индекс указывает на номер главы, второй номер соответствующего параграфа, а третий порядковый номер утверждения в этом параграфе. Нумерация замечаний сквозная.
СОДЕРЖАНИЕ РАБОТЫ
Во введении описана актуальность проблемы, рассмотрены известные результаты по тематике индексных множеств. Даны основные определения используемые в работе.
В работе [27] было показано, что для любой конечной сигнатуры без функциональных символов существует универсальная вычислимая нумерация вычислимых моделей этой сигнатуры. Для случая же бесконечной сигнатуры существует универсальная вычислимая нумерация всех вычислимых моделей сигнатуры вместе со всеми конечными вычислимыми моделями конечных частей этой сигнатуры [28, §1.4], [34, §1.3].
Существование таких универсальных нумераций моделей позволяет получить характеризацию классов вычислимых моделей соотнесением индексных множеств конкретных классов моделей с уровнем подходящей алгоритмической иерархии. Характеризация классов алгебраических систем в сигнатуре с функциональными символами может быть построена на основе этого подхода представлением функций своими графиками – предикатами.
Пусть = {M0, M1,..., Mn,...} упомянутая универсальная вычислимая нумерация моделей для соответствующей сигнатуры. Пусть K некоторый класс моделей сигнатуры без функциональных символов.
Определение 1.4. Индексным множеством I(K) абстрактного класса моделей K (класса, замкнутого относительно изоморфизмов), называется множество I(K) := {i | Mi K}.
Индексным множеством I(K) класса вычислимых моделей K называется множество I(K) := {i | существует M K, что Mi вычислимо изоморфно M}.
Определение 1.5. Пусть – некоторый уровень сложности (например, 1, 0 ). Тогда:
1. I(K) является -множеством, если I(K) ;
2. I(K) является m-полным -множеством, если I(K) и для любого S существует равномерно вычислимая последовательность вычислимых моделей (Cn )n такая, что В определении гиперарифметической иерархии будем следовать обозначениям Роджерса [29, §14], например 0, 0. Верхний индекс 1 в 1 означает разность 0 -множеств (0 \ 0 ).
В главе 1 работы рассматривается вопрос об алгоритмической сложности определения теоретико-модельных свойств класса алгебраических систем, заданного некоторым набором формул. С этой позиции исследуется свойство конечности алгебраических систем. Исследование построено на анализе проблемы существования алгоритма, определяющего конечность свободной системы квазимногообразия, заданного с помощью конечного множества квазитождеств. В главе приводится алгоритм распознающий конечность свободной системы, заданной системой квазитождеств в сигнатуре с одной унарной операцией и, может быть, некоторым вычислимым множеством констант. Доказано отсутствие общего алгоритма определения конечности по системе квазитождеств в сигнатуре с, по крайней мере, двумя унарными операциями. Доказательство основано на алгоритмической нераспознаваемости свойства конечности конечно-определённых групп. Используется результат Адяна и Рабина [30]. Построено сведение рассматриваемой проблемы для сигнатур с одной бинарной операцией и одной константой к результату предыдущего параграфа, а значит и к несуществованию алгоритма. Построена точная оценка индексного множества класса конечных моделей 0. Результаты первой главы изложены в работах [38], [35].
В главе 2 работы развиты подходы Гончарова для построения нижних оценок индексных множеств. Доказано, что функтор построенный в [31] сохраняет важные свойства вычислимых моделей:
Теорема 2.1. Пусть - вычислимая сигнатура без функциональных символов с конечным числом предикатных символов. Тогда для любой модели M сигнатуры существует модель M сигнатуры графов, для которой:
1. M вычислима M вычислима;
2. M d-разрешима M d-разрешима;
3. количество счётных моделей теорий T h(M) и T h(M ) совпадает;
4. M проста M проста.
Данный результат используется в работе для построения нижних оценок для соответствующих сигнатур.
В параграфе 2.2 развит универсальный подход построения нижних оценок сложности для определённого класса теоретико-модельных свойств.
Этот класс определяется через понятие маркеровского расширения модели [22].
Определение 2.3.3. Теоретико-модельное свойство R называется маркеровским, если для любой модели M любой конечной предикатной сигнатуры : M обладает свойством R тогда и только тогда, когда маркеровские расширения M и M обладают свойством R.
Назовём свойство маркеровским*, если оно маркеровское и дополнительно для сигнатур, содержащих предикатный символ P местности n 1, существуют модели A и B этой сигнатуры, такие что:
(1*) A обладает свойством R, B – не обладает свойством R, (2*) модели A, B вычислимы, (3*) предикаты P A, P B являются бесконечными кобесконечными множествами.
Для классов вычислимых моделей, которые определены с помощью маркеровских* свойств получена нижняя оценка 0. Об этом свидетельствует Теорема 2.4. Для любого маркеровского* свойства R существует вычислимая функция fR (m, n) такая, что Mf (m,n) обладает свойством R, если m (n), и не обладает им, в противном случае.
Результаты второй главы опубликованы в [39], [40], [36], [41], [37].
Глава 3 посвящена оценке индексных множеств специальных классов вычислимых моделей. Найдена и доказана точная оценка для класса простых d-разрешимых моделей, для арифметической Тьюринговой степени d.
Назовём сигнатуру нетривиальной, если она содержит предикатный или функциональный символ местности 2. Пусть вычислимая нетривиальная сигнатура. Первый результат формулируется как Теорема 3.1. Для любой арифметической Тьюринговой степени d индексное множество P rimed всех d-разрешимых простых моделей вычислимой сигнатуры является m-полным 1,d множеством в универсальной вычислимой нумерации всех вычислимых моделей сигнатуры.
Установлена точная оценка для класса простых моделей, но уже для бесконечных сигнатур. Пусть теперь вычислимая сигнатура, содержащая бесконечное число предикатных символов местности 2.
Теорема 3.2. Индексное множество P rime всех простых вычислимых моделей сигнатуры является m-полным 0 множеством в универсальной вычислимой нумерации всех вычислимых моделей сигнатуры.
Результаты третьей главы опубликованы в статьях [36], [41].
В главе 4 рассмотрены классы моделей, определённые естественными свойствами своих теорий. Установлены нижняя и верхняя оценка для вычислимых моделей, имеющих -категоричные теории.
Теорема 4.1. Для сигнатуры, содержащей бесконечное число преCat является 0 -сложным 0 дикатных символов местности + множеством.
Верхняя оценка верна для произвольных сигнатур. Для построения верхней оценки использовалась синтаксическая характеризация счётнокатегоричных теорий, впервые полученная Рылль-Нардзевским [23]. Найдены нижняя и верхняя оценки для вычислимых моделей, имеющих 1 категоричные теории. Для построения верхней оценки используется синтаксическая характеризация 1 -категоричных теорий, впервые полученная Лахланом и Балдвином [24], и законченная в работах Еримбетова [25],[32].
Эта характеризация с точки зрения вычислимости, как показывает теорема, почти идеальна.
Теорема 4.2. Для вычислимой сигнатуры, содержащей для каждого натурального числа n предикатный символ местности n, множество U Cat является 0 -сложным 0 -множеством.
Доказана 1 -полнота класса вычислимых моделей, имеющих Эренфойхтову теорию:
Теорема 4.5. Индексное множество Ehr сигнатуры, содержащей бесконечное число предикатных символов местности 2, является 1 -полным множеством в универсальной вычислимой нумерации всех вычислимых моделей сигнатуры.
Доказательство верхней оценки построено на синтаксической характеризации Эренфойхтовых теорий, полученной сравнительно недавно Судоплатовым [26]. Оказывается, что эта характеризация неулучшаема с точки зрения теории вычислимости. Нижняя оценка базируется на результатах, полученных Лемппом и Сламаном [33], о сложности разрешимых Эренфойхтовых теорий.
Как следствие этой теоремы и синтаксической характеризации Судоплатова получается оценка для индексного множества моделей, теории которых допускают бесконечное число моделей.
Следствие 4.3.1. Индексное множество вычислимых моделей сигнатуры, содержащей бесконечное число предикатных символов местности 2, теории которых допускают бесконечное число счтных моделей является m-полным 1 множеством.
Результаты главы опубликованы в [37], [36].
Изложение работы заканчивается заключением и списком литературы.
Автор выражает глубокую признательность своему научному руководителю Сергею Севостьяновичу Гончарову за внимание к работе, терпение и поддержку, а также за постановку задач и приобщению к проблемам математической логики. Автор также благодарит Сибирской фонд алгебры и логики за моральную и материальную поддержку в проведении исследований.
Список литературы:
[1] Calvert W. The isomorphism problem for classes of computable elds // Archive for Mathematical Logic. 2004. Vol. 34, no. 3. Pp. 327–336.
[2] Calvert W. The isomorphism problem for computable abelian p-groups of [3] Калверт У., Каммингс Д., Найт Дж. Ф., Миллер С. Сравнение классов конечных структур // Алгебра и логика. 2004. Т. 43, № 6.
С. 666–701.
[4] Калверт У., Харизанова В., Найт Дж. Ф., Миллер С. Индексные [5] Csima B. F., Montalbn A., Shore R. A. Boolean algebras, tarski invariants, and index sets // Notre Dame Journal of Formal Logic.
[6] Добрица В. П. Сложность индексного множества конструктивной модели // Алгебра и логика. 1983. Т. 22, № 4. С. 372–381.
[7] White W. On the complexity of categoricity in computable structures // Mathematical Logic Quarterly. 2003. Vol. 49. Pp. 603–614.
[8] White W. Characterizations for Computable Structures: Ph.D. thesis / PhD dissertation. Cornell University, 2000.
[9] Фокина Е. Б. Индексные множества разрешимых моделей // [10] Ершов Ю. Л. Теория нумераций. М.: Наука, 1977.
«