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

На правах рукописи <0-

□03172306

ПАВЛОВСКИЙ Евгений Николаевич

Оценка алгоритмической сложности классов вычислимых моделей

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

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук

1 в ко; 2ССЗ

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

003172306

Работа выполнена в Новосибирском государственном университете

Научный руководитель доктор физико-математических наук

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

Официальные оппоненты доктор физико-математических наук,

профессор Хисамиев Назиф Гарифуллинович

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

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

Автореферат разослан " U-itUin. 2008

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

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

Ученый секретарь диссертационного сове кандидат физико-математических наук

Ряскин А Н

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ Актуальность темы. Академик А И Мальцев предложил использовать нумерации как базовую концепцию для изучения алгоритмических свойств алгебраических систем и их подмножеств, в частности таких классических систем, как группы, кольца и поля

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

К настоящему времени известно достаточно много результатов об индексных множествах моделей, классов моделей, теорий [1], [2], [3], [4], [5],

[6], [7], [8], [9] Большую роль индексные множества сыграли в общей теории вычислимости и вычислимых нумераций (кн Ю Л Ершов Теория нумераций [10]) Открытые проблемы этого направления привлекли специалистов и обсуждались на нескольких логических конференциях, в частности, приведены в работе Гончарова и Хусаинова [11], Гончарова и Найт [12]

Гончаров и Найт предложили [12] общие подходы для изучения структурных и алгоритмических свойств классов вычислимых моделей на основе исследования индексных множеств Для многих классов индексное множество лежит на низком уровне гиперарифметической иерархии множество 1(К) является П^-множеством для следующих классов линейные порядки, булевы алгебры, абелевы р-группы, модели эквивалентности, векторные пространства над <0>, модели фиксированного вычислимого языка

В работе [6] даны точные оценки для индексных множеств конструктивных моделей с заданными условиями автоэквивалентности рассматриваемых конструктивизаций В работе [13] дана точная оценка индексного множества для локальных конусов Ряд работ В П Добрицы посвящено изучению различных индексных множеств конструктивных моделей [6], [14], [15], [13], [16]

Для некоторых классов индексное множество гиперарифметично (Клини, Спектор) множество 1(К) является Е}-полным для следующих классов полные порядки, суператомные булевы алгебры, редуцированные р-группы

Для решения вопроса о существовании вычислимой классификации классов в [12] предложен подход оценки проблемы изоморфизма в терминах индексных множеств и приводятся доказательства оценок проблемы изоморфизма для некоторых важных классов Так, например, множество Е(К) проблемы изоморфизма является ¡[¡¡-полным для следующих классов К абелевы р-группы, деревья, булевы алгебры, линейные порядки, произвольные модели языка, содержащего по крайней мере один предикатный символ местности большей или равной 2 Проблемы изоморфизма также исследуются в работах [1], [2] для векторных пространств, алгебраических полей фиксированной характеристики, [17] для классов конструктивных I-

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

Настоящая работа посвящена исследованию вопроса о характериза-ции известных классов моделей через оценку сложности индексных множеств классов вычислимых моделей С этой точки зрения можно рассмотреть классы специальных моделей (простые, однородные, насыщенные, универсальные), классы моделей с заданными свойствами теорий (теория допускает простую модель, счетная-категоричность теории, несчетная категоричность, Эренфойхтовость, разрешимость теории), классы моделей с фиксированными алгоритмическими свойствами (разрешимые модели, автоустойчивые, модели конечной(бесконечной) алгоритмической размерности, модели с вычислимым рангом Скотта, с невычислимым рангом Скотта, (¿-разрешимые счетно-категоричные модели, ¿¿-разрешимые простые модели) Решение вопроса об оценке сложности этих множеств находится в русле проблем, обсуждаемых в докладе Гончарова и Хусаинова [11], а именно с проблемами существования конструктивных моделей для определенных классов теорий, а также о максимальной сложности некоторых теорий, имеющих конструктивные модели [11, Problems 3, 5, 11, Question 6]

Из перечисленных классов уже построены точные оценки для класса (¿-разрешимых моделей (S^), (¿-разрешимых счетно-категоричных моделей (Е31,d) [9] Для класса универсальных вычислимых моделей получена нижняя оценка Е{ [lSj Е Б Фокиной также была получена точная оценка индексного множества моделей, имеющих разрешимые теории Е^'0' ' [20]

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

В данной работе применен подход понижения вычислительной сложности в теоретико-модельных конструкциях (подход Гончарова-Хусаинова на основе конструкции Маркера) [22] для получения нижних оценок алгоритмической сложности вычислимых представителей естественных

классов моделей В работе использованы синтаксические характериза-ции классов моделей, обладающих (^-категоричными теориями (Рылль-Нардзевский [23]), обладающих ¿^-категоричными теориями (Лахлан-Балдвин [24], Еримбетов [25]), современные результаты о синтаксической характеризации Эренфойхтовых теорий (Судоплатов, [26]) Для тех классов, для которых получены точные оценки, фактически подтверждается тезис выдвинутый в работе [3] о том, что точная оценка индексного множества дается некоторым «оптимальным» описанием модели В настоящей работе доказано, что упомянутые синтаксические характеризации обладают наименьшей возможной вычислительной сложностью, те являются наилучшими синтаксической характеризациями с точки зрения вычислимости

Цель работы. Анализ взаимосвязи между структурными и алгоритмическими свойствами классов вычислимых моделей

Общая методика исследований. В работе анализируется взаимосвязь определимости классов моделей с алгоритмической их сложностью посредством построения точных оценок индексных множеств классов вычислимых моделей в соответствующих иерархиях алгоритмической сложности множеств, а также с помощью явного построения алгоритмов, или доказательства отсутствия таковых для определенных классов задач Используется аппарат теории моделей, широко используются теоретико-модельные функторы, предложенные Гончаровым [31], [22], синтаксические характеризации теоретико-модельных свойств [23],[26], [25], методы теории вычислимости, теории квазимногообразий

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

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

- на основе введенного понятия маркеровского свойства получена универсальная нижняя оценка сложности (Д°) для различных классов вычислимых моделей,

- построены точные оценки следующих классов вычислимых моделей простые модели, (¿-разрешимые простые модели (относительно арифметической Тьюринговой степени (Г), модели с Эренфойхтовой теорией, модели, теории которых допускают бесконечное число счетных моделей,

- построены верхние и нижние оценки следующих классов модели с ш-категоричной теорией, модели с ^-категоричной теорией

Все основные результаты работы являются новыми, опубликованы

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

Апробация работы. Результаты работы были доложены на Девятой Азиатской логической конференции (Новосибирск, 2005), на Международной научно-практической студенческой конференции "Студент и научно-технический прогресс"(Новосибирск, 2003, 2004, 2006), на Логическом Коллоквиуме (Вроцлав, Польша, 2007), на Летней международной школе по вычислимым моделям и нумерациям (Новосибирск, 2007),

С результатами работы автор неоднократно выступал на семинаре "Конструктивные модели "(Новосибирск, НГУ, 2003 - 2008), семинаре "Алгебра и логика"(Новосибирск, НГУ, 2003, 2005)

Публикации Основные результаты опубликованы в работах [35]-[37], источники входят в перечень ВАК ведущих рецензируемых научных журналов и изданий, в которых должны быть опубликованы основные научные результаты диссертации

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

СОДЕРЖАНИЕ РАБОТЫ Во введении описана актуальность проблемы, рассмотрены известные результаты по тематике индексных множеств Даны основные определения используемые в работе

В работе [27] было показало, что для любой конечной сигнатуры без функциональных символов существует универсальная вычислимая нумерация вычислимых моделей этой сигнатуры Для случая же бесконечной сигнатуры а существует универсальная вычислимая нумерация всех вычислимых моделей сигнатуры а вместе со всеми конечными вычислимыми моделями конечных частей этой сигнатуры [28, §1 4], [34, §1 3]

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

Пусть иа = {Мо, Л^ь , Мп, } упомянутая универсальная вычислимая нумерация моделей для соответствующей сигнатуры а Пусть К — некоторый класс моделей сигнатуры а без функциональных символов

Определение 1.4 Индексным множеством 1{К) абстрактного класса моделей К (класса, замкнутого относительно изоморфизмов), называется множество 1{К) = {г | Мг€ К}

Индексным множеством 1{К) класса вычислимых моделей К называется множество 1{К) = {г [ существует М € К, что Мг вычислимо изоморфно М}

Определение 1 5 Пусть Г - некоторый уровень сложности (например, П}, Е°+2) Тогда

1 1{К) является V-множеством, если 1(К) 6 Г,

2 1(К) является т-полным Г -множеством, если ЦК) 6 Г и для любого 5 6 Г существует равномерно вычислимая последовательность вычисли-

мых моделей (Сп)п£и такая, что

п € 5 тогда и только тогда, когда Сп € К

В определении гиперарифметической иерархии будем следовать обозначениям Роджерса [29, §14], например Е°+1, Верхний индекс —1 в Е^1 означает разность Е^-множеств (Е® \Е°)

В главе 1 работы рассматривается вопрос об алгоритмической сложности определения теоретико-модельных свойств класса алгебраических систем, заданного некоторым набором формул С этой позиции исследуется свойство конечности алгебраических систем Исследование построено на анализе проблемы существования алгоритма, определяющего конечность свободной системы квазимногообразия, заданного с помощью конечного множества квазитождеств В главе приводится алгоритм распознающий конечность свободной системы, заданной системой квазитождеств в сигнатуре с одной унарной операцией и, может быть, некоторым вычислимым множеством констант Доказано отсутствие общего алгоритма определения конечности по системе квазитождеств в сигнатуре с, по крайней мере, двумя унарными операциями Доказательство основано на алгоритмической нераспознаваемости свойства конечности конечно-определенных групп Используется результат Адяна и Рабина [30] Построено сведение рассматриваемой проблемы для сигнатур с одной бинарной операцией и одной константой к результату предыдущего параграфа, а значит и к несуществованию алгоритма Построена точная оценка индексного множества класса конечных моделей Результаты первой главы изложены в работах [38], [35]

В главе 2 работы развиты подходы Гончарова для построения нижних оценок индексных множеств Доказано, что функтор построенный в [31] сохраняет важные свойства вычислимых моделей

Теорема 2 1 Пусть а - вычислимая сигнатура без функциональных символов с конечным числом предикатных символов Тогда для любой модели М сигнатуры а существует модель М! сигнатуры графов, для которой

1 М вычислима <=>■ М! вычислима,

2 М <1-разрешима М' й-разрешима,

3 количество счетных моделей теорий Тк(М) и Тк(Л4') совпадает,

4 М проста М' проста

Далный результат используется в работе для построения нижних оценок для соответствующих сигнатур

В параграфе 2 2 развит универсальный подход построения нижних оценок сложности для определенного класса теоретико-модельных свойств Этот класс определяется через понятие маркеровского расширения модели [221

Определение 2.3.3 Теоретико-модельное свойство К называется маркеровским, если для любой модели М любой конечной предикатной сигнатуры а М. обладает свойством К тогда и только тогда, когда марке-ровские расширения Л^з и М\/ обладают свойством К Назовем свойство маркеровским*, если оно маркеровское и дополнительно для сигнатур а, содержащих предикатный символ Р местности п ^ 1, существуют модели А и В этой сигнатуры, такие что (1*) А обладает свойством К, В - не обладает свойством К, (2*) модели А, В вычислимы,

(3*) предикаты Рл, Рв являются бесконечными кобесконечными множествами

Для классов вычислимых моделей, которые определены с помощью маркеровских* свойств получена нижняя оценка Д® Об этом свидетельствует

Теорема 2 4 Для любого маркеровского* свойства К существует вычислимая функция }к.{т,п) такая, что М/(т,п) обладает свойством К, если т 6 и не обладает им, в противном случае

Результаты второй главы опубликованы в [39], [40], [36], [41], [37]

Глава 3 посвящена оценке индексных множеств специальных классов вычислимых моделей Найдена и доказана точная оценка для класса простых (¿-разрешимых моделей, для арифметической Тьюринговой степени й Назовем сигнатуру нетривиальной, если она содержит предикатный или функциональный символ местности ^ 2 Пусть а вычислимая нетривиаль-

ная сигнатура Первый результат формулируется как

Теорема 3 1 Для любой арифметической Тьюринговой степени d индексное множество Рггте% всех d-разрешимых простых моделей вычислимой сигнатуры а является т-полным EJ1'^ множеством в универсальной вычислимой нумерации всех вычислимых моделей сигнатуры а

Установлена точная оценка для класса простых моделей, но уже для бесконечных сигнатур Пусть теперь а вычислимая сигнатура, содержащая бесконечное число предикатных символов местности > 2

Теорема 3 2 Индексное множество Рггтеа всех простых вычислимых моделей сигнатуры о является тть-полным множеством в универсальной вычислимой нумерации всех вычислимых моделей сигнатуры а

Результаты третьей главы опубликованы в статьях [36], [41] В главе 4 рассмотрены классы моделей, определенные естественными свойствами своих теорий Установлены нижняя и верхняя оценка для вычислимых моделей, имеющих w-категоричные теории

Теорема 4 1 Для сигнатуры а, содержащей бесконечное число предикатных символов местности ^ 2, Cata является Tl^-сложным множеством

Верхняя оценка верна для произвольных сигнатур Для построения верхней оценки использовалась синтаксическая характеризация счетно-категоричных теорий, впервые полученная Рылль-Нардзевским [23] Найдены нижняя и верхняя оценки для вычислимых моделей, имеющих wi-категоричные теории Для построения верхней оценки используется синтаксическая характеризация ¿¿¡-категоричных теорий, впервые полученная Лахланом и Балдвином [24], и законченная в работах Еримбетова [25],[32] Эта характеризация с точки зрения вычислимости, как показывает теорема, почти идеальна

Теорема 4.2 Для вычислимой сигнатуры сг, содержащей для каждого натурального числа п предикатный символ местности ^ п, множество UCata является А° -слооюным +1 -множест в ом

Доказана П}-полнота класса вычислимых моделей, имеющих Эрен-

фойхтову теорию

Теорема 4.5 Индексное множество Ehr„ сигнатуры а, содержащей бесконечное число предикатных символов местности > 2, является П|-полным множеством в универсальной вычислимой нумерации всех вычислимых моделей сигнатуры а

Доказательство верхней оценки построено на синтаксической харак-теризации Эренфойхтовых теорий, полученной сравнительно недавно Су-доплатовым [26] Оказывается, что эта характеризация неулучшаема с точки зрения теории вычислимости Нижняя оценка базируется на результатах, полученных Лемппом и Сламаном [33], о сложности разрешимых Эренфойхтовых теорий

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

Следствие 4 3 1 Индексное множество вычислимых моделей сигнатуры а, содержащей бесконечное число предикатных символов местности ^ 2, теории которых допускают бесконечное число счетных моделей является тп-полным £} множеством

Результаты главы опубликованы в [37], [36]

Изложение работы заканчивается заключением и списком литературы

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

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

[lj Calvert W The isomorphism problem for classes of computable fields // Archive for Mathematical Logic - 2004 - Vol 34, no 3 - Pp 327-336

[2] Calvert W The isomorphism problem for computable abelian p-groups of bounded length // J Symbolic Logic - 2005 - Vol 70, no 1 - Pp 331345

[3] Калверт У, Каммингс Д , НайтДж Ф , Миллер С Сравнение классов конечных структур // Алгебра и логика — 2004 — Т 43, № 6 — С 666-701

[4] Калверт У, Харизанова В, Найт Дж Ф , Миллер С Индексные множества вычислимых моделей // Алгебра и логика — 2006 — Т 45, № 5 - С 538-574

[5] Csima В F, Montalban А , Shore R A Boolean algebras, tarski invariants, and index sets // Notre Dame Journal of Formal Logic — 2006 - Vol 47, no 1 - Pp 1-23

[6] Добрица В П Сложность индексного множества конструктивной модели // Алгебра и логика - 1983 - Т 22, № 4 - С 372-381

[7] White W On the complexity of categoricity m 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] Фокина E Б Индексные множества разрешимых моделей // Сиб мат журн - 2007 - Т 48, if« 5 - С 1167-1179

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

[11] Goncharov S, Khoussamov В Open problems m the theory of constructive algebraic systems // Computability Theory and Its Applications Current Trends and Open Problems — Vol 257 — American Mathematical Society 2000 - Pp 145-169

[12] Гончаров С С, Найт Д Вычислимые структурные и антиструктурные теоремы // Алгебра и логика — 2002 — Т 41, № 6 — С 639-681

[13] Добрица В П Вычислимость некоторых подклассов вычислимого класса конструктивных моделей // Сиб мат журн — 1989 — Т 30, №3 - С 45-51

[14] Добрица В П Сложность индексных множеств вычислимых классов с конечным числом конструктивных систем // Сиб мат журн — 1986 - Т 27, № 5 - С 68-74

[15] Добрица В П Структурные свойства вычислимых классов конструктивных моделей // Алгебра и логика — 1987 — Т 26, № 1 — С 36-62

[16] Добрица В П Индексные множества в обобщенных вычислимых нумерациях // Мат журн 2 - 2002 - Т 3, № 1 - С 38-42

[17] Когабаев Н Т Сложность некоторых естественных проблем на классе вычислимых 7-алгебр // Сиб мат журн — 2006 — Т 47, № 2 — С 352-360

[18[ Винокуров Н С Индексные множества классов автоматных структур // Сиб мат журн - 2006 — Т 47, № 5 — С 1019-1030

[19] Перетятькин М Г Конечно аксиоматизируемые классы — Новосибирск Научная книга, 1997

[20] Fokina Е В Index sets of computable structures with decidable theories // Computation and Logic in the Real World - Third Conference of Computability m Europe (CiE) 2007 — Vol 4497 of Lecture Notes m Computer Science — Siena, Italy June 2007 — Pp 290-296

[21] Calvert W, Fokina E, Goncharov S S et al Index sets for classes of high rank structures // J Symbolic Logic — 2007 — Vol 72, no 4 — Pp 1418-1432

[22] Гончаров С С, Хусаинов Б X. Сложность теорий вычислимых категоричных моделей // Алгебра и логика — 2004 — Т 43, № 6 — С 650665

[23] Ryll-Nardzeuiski С On the categoricity in power < No // Bull Acad Pol Sci Ser Math , Astron , Phys - 1959 - Vol 7 - Pp 545-548

[24] Baldwin J T, Lachlan AH On strongly minimal sets // J Symbolic Logic - 1971 - Vol 36, no 1 - Pp 79-96

[25] Еримбетов MM О полных теориях с 1-кардинальными формулами // Алгебра и логика - 1975 - Т 14, № 3 - С 245-257

[26] Судоплатов С В Полные теории с конечным числом счетных моделей 1 // Алгебра и логика - 2004 -Т 43, № 1 - С 110-124

[27] Нуртазин А Т Вычислимые классы и алгебраические критерии автоустойчивости Дисс канд физ -мат наук / АН Казахской ССР Ин-т математики и механики Лаб алгебры и логики — АлмагАта, 1974

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

[29] Роджерс X Теория рекурсивных функций и эффективная вычислимость — М Мир, 1972

[30] Адян С И, Дурнев В Г Алгоритмические проблемы для групп и полугрупп // Успехи мат наук — 2000 — Vol 55, по 2 — Рр 4-94

[31] Гончаров С С Проблема числа неавтоэквивалентных конструктиви-заций // Алгебра и логика - 1980 — Т 19, № 6 — С 621-639

[32] Еримбетов М М Категоричность в мощности и недвукардинальность формулы конечного ранга // Алгебра и логика — 1974 — Т 13, № 5 — С 493-500

[33] Lempp S, Slaman Т A The complexity of the index sets of No-categorical theories and of ehrenfeucht theories // Proc of the North Texas Logic Conference, October 8-10, 2004 - 2004

[34] Goncharov S S Computability and computable models // Mathematical problems from applied logic II / Ed by S S G Dov M Gabbay, M Zakharyaschev — New York Springer, 2006 — Logics for the XXIst century

РАБОТЫ АВТОРА ПО ТЕМЕ ДИССЕРТАЦИИ

[35] Павловский Е Н Алгоритмическая распознаваемость свойства конечности конечно-определенных систем // Вестник НГУ Серия математика, механика, информатика — 2006 — Т 6, № 4 — С 83-92

[36] Павловский Е Н Оценка алгоритмической сложности классов вычислимых моделей // Сиб мат журн — 2008 - Т 49, № 3 - С 635-649

[37] Павловский Е Н Сложность индексных множеств некоторых классов моделей // Вестник НГУ Серия математика, механика, информатика - 2008 - Т 8, № 1 - С 71-76

[38] Павловский Е Н Алгоритмическая распознаваемость свойства конечности конечно-определенных систем // Материалы XLII международной научной студенческой конференции Студент и научно-технический прогресс — Математика — Новосибирск 2004 — С 1415

[39] Павловский Е Н Оценка алгоритмической сложности классов вычислимых моделей // Материалы XL1V международной научной студенческой конференции Студент и научно-технический прогресс — Математика - Новосибирск 2006 — С 76-77

[40] Pavlovsky Е N Estimation of algorithmic complexity of computable models classes // Book of abstracts, Logic Colloquium'07 — Wroclaw, Poland 2007 - P 91

[41] Павловский E H Индексные множества простых моделей // Сибирские электронные математические известия — 2008 — Т 5 — С 200-210

Подписано в печать Л\0Г Of Формат 60 х 84 Уч -изд л 1 Заказ № 213 Тираж 100 экз

Редакционно-издательский центр НГУ 630090, Новосибирск-90, ул Пирогова, 2

Введение

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

2. Общая характеристика результатов работы

Глава 1. Конечные модели.

1.1. Обозначения и предварительные результаты

1.2. Сигнатура с одной унарной операции.

1.3. Сигнатура с несколькими унарными операциями

1.4. Случай произвольной сигнатуры

1.5. Индексное множество конечных моделей

Глава 2. Теоретико-модельные конструкции

2.1. Сведение произвольной сигнатуры к сигнатуре графов.

2.2. Понижение алгоритмической сложности

2.3. Маркеровские расширения

2.4. Построение нижних оценок для маркеровских свойств

Глава 3. Индексные множества специальных классов моделей

3.1. Простые модели

Глава 4. Индексные множества классов моделей с заданными свойствами теорий.

4.1. Модели с иькатегоричной теорией.

4.2. Множество вычислимых о^-категоричных моделей

4.3. Эренфойхтовы теории.

Академик А.И.Мальцев предложил использовать нумерации как базовую концепцию для изучения алгоритмических свойств алгебраических систем и их подмножеств, в частности таких классических систем, как группы, кольца и поля. Развивая это направление во взаимосвязи с общей теорией нумераций, С.С.Гончаров совместно с итальянским математиком А.Сорби предложили и разработали общий подход к понятию вычислимой нумерации, основанный на семантиках формальных языков. Изучение общих структурных свойств таких вычислимых нумераций на основе как соответствующих полурешеток Роджерса, так и в рамках локальных (внутренних) свойств таких нумераций через индексные множества в этих нумерациях является одной из важнейших исследовательских задач.

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

К настоящему времени известно достаточно много результатов об индексных множествах моделей, классов моделей, теорий [1], [2], [3], [4], [5], [6], [7], [8], [9]. Большую роль индексные множества сыграли в общей теории вычислимости и вычислимых нумераций (кн. Ю.Л.Ершов. Теория нумераций [10]). Открытые проблемы этого направления привлекли специалистов и обсуждались на нескольких логических конференциях, в частности, приведены в работе Гончарова и Хусаинова [11], Гончарова и Найт [12].

Гончаров и Найт предложили [12] общие подходы для изучения структурных и алгоритмических свойств классов вычислимых моделей на основе исследования индексных множеств. Для многих классов индексное множество лежит на низком уровне гиперарифметической иерархии:

Предложение 0.1. Множество 1(К) является П^-множеством для следующих классов:

1. линейные порядки;

2. булевы алгебры;

3. абелевы р-группы;

4■ модели эквивалентности;

5. векторные пространства над Q;

6. модели фиксированного вычислимого языка.

В работе [6] даны точные оценки для индексных множеств конструктивных моделей с заданными условиями автоэквивалентности рассматриваемых конструктивизаций. В работе [13] дана точная оценка индексного множества для локальных конусов. Ряд работ В.П. Добрицы посвящено изучению различных индексных множеств конструктивных моделей [6], [14], [15], [13], [16]. Для некоторых классов индексное множество гиперарифметично:

Предложение 0.2 (Клини, Спектор) Множество 1{К) является пол-ным для следующих классов:

1. полные порядки;

2. суператомные булевы алгебры;

3. редуцированные р-группы.

Для решения вопроса о существовании вычислимой классификации классов в [12] предложен подход оценки проблемы изоморфизма в терминах индексных множеств и приводятся доказательства оценок проблемы изоморфизма для некоторых важных классов.

Теорема 0.1. Множество Е(К) проблемы изоморфизма является полным для следующих классов К:

1. абелевы р-группы;

2. деревья;

3. булевы алгебры;

4■ линейные порядки;

5. произвольные модели языка, содержащего по крайней мере один предикатный символ местности большей или равной 2.

Проблемы изоморфизма также исследуются в работах [1], [2] для вектор-пых пространств, алгебраических полей фиксированной характеристики, [17] для классов конструктивных /-алгебр, [18] для классов автоматных моделей.

Подход через индексные множества также позволяет оценить сложность семантических классов предложений, целая глава в монографии [19] посвящена оценкам алгоритмической сложности классов предложений, используемых в теории моделей и логике.

Настоящая работа посвящена исследованию вопроса о характеризации известных классов моделей через оценку сложности индексных множеств классов вычислимых моделей. С этой точки зрения можно рассмотреть классы специальных моделей (простые, однородные, насыщенные, универсальные), классы моделей с заданными свойствами теорий (теория допускает простую модель, счётная-категоричность теории, несчётная категоричность, Эренфойхтовость, разрешимость теории), классы моделей с фиксированными алгоритмическими свойствами (разрешимые модели, автоустойчивые, модели конечной(бесконечной) алгоритмической размерности, модели с вычислимым рангом Скотта, с невычислимым рангом Скотта, ^-разрешимые счётно-категоричные модели, af-разрешимые простые модели). Решение вопроса об оценке сложности этих множеств находится в русле проблем, обсуждаемых в докладе Гончарова и Хусаинова [И], а именно с проблемами существования конструктивных моделей для определённых классов теорий, а также о максимальной сложности некоторых теорий, имеющих конструктивные модели

11, Problems 3, 5, 11, Question 6].

Из перечисленных классов уже построены точные оценки для класса d-разрешимых моделей:

Теорема 0.2 ([9]) Для любой арифметической Тьюринговой степени d индексное множество всех d-разрешимых моделей нетривиальной сигнатуры viO 4 является т-полпым множеством.

Для класса ^-разрешимых счётно-категоричных моделей:

Теорема 0.3 ([9]) Для любой арифметической Тьюринговой степени d индексное множество всех d-разрешимых счётно-категоричных моделей нетривиальной сигнатуры является т-полным Е3l,d множеством.

Для класса универсальных вычислимых моделей получена нижняя оценка:

Теорема 0.4 ([18]) Множество универсальных вычислимых моделей не менее чем Т,\-полное.

Е.Б. Фокиной также была получена точная оценка индексного множества моделей, имеющих разрешимые теории:

Теорема 0.5 ([20]) Индексное мноэ/сество вычислимых моделей с разрешимом^ мыми теориями является т-полным Ъ2 множеством.

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

Теорема 0.6 ([21]) Индексное множество класса вычислимых моделей:

1) имеющих невычислимый ранг Скотта является Т\-полным;

2) имеющих ранг Скотта является И^-полным относительно системы обозначений Клини О;

3) имеющих ранг Скотта u>iK + 1 является Т^-полным относительно системы обозначений Клини О.

В данной работе применён подход понижения вычислительной сложности в теоретико-модельных конструкциях (подход Гончарова-Хусаинова на основе конструкции Маркера) [22] для получения нижних оценок алгоритмической сложности вычислимых представителей естественных классов моделей.

В работе использованы синтаксические характеризации классов моделей, обладающих о;-категоричными теориями (Рылль-Нардзевский [23]), обладающих а^-категоричными теориями (Лахлан-Балдвин [24], Еримбетов [25]), современные результаты о синтаксической характеризации Эренфойхтовых теорий (Судоплатов, [26]). Для тех классов, для которых получены точные оценки, фактически подтверждается тезис выдвинутый в работе [3] о том, что точная оценка индексного множества даётся некоторым «оптимальным» описанием модели. В настоящей работе доказано, что упомянутые синтаксические характеризации обладают наименьшей возможной вычислительной сложностью, т.е. являются наилучшими синтаксической характеризациями с точки зрения вычислимости.

Заключение

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

1. Для сигнатуры унаров существует общий алгоритм распознания конечности свободной системы по конечному набору квазитождеств.

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

Кроме того, для конечных моделей показана Е^-полнота соответствующего индексного множества.

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

Были даны нижние и верхние оценки сложности индексных множеств вычислимых моделей с и ^i- категоричными теориями. Представлен универсальный способ получения нижних оценок для маркеровских свойств, т.е. таких теоретико-модельных свойств, которые сохраняются при маркеровских расширениях моделей. В качестве продолжения исследований в этом направлении можно рассматривать вопросы об оценке индексных множеств других классов моделей:

• однородные модели;

• насыщенные модели;

• допускающие разрешимое представление (допускающие п-разрешимое представление);

• автоустойчивые модели;

• модели бесконечной алгоритмической размерности;

• модели конечной алгоритмической размерности;

• с тотально-трансцендентной (No-стабильной) теорией;

• автоустойчивые относительно Да-изоморфизмов;

1. Calvert W. The isomorphism problem for classes of computable fields // Archive for Mathematical Logic. — 2004. — Vol. 34, no. 3. — Pp. 327-336.

2. Calvert W. The isomorphism problem for computable abelian p-groups of bounded length j I J. of Symbolic Logic. — 2005. — Vol. 70, no. 1. — Pp. 331345.

3. Калверт У., Каммингс Д., Найт Дж. Ф., Миллер С. Сравнение классов конечных структур // Алгебра и логика. — 2004. — Т. 43, № 6. — С. 666701.

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

5. Csima В. F., Montalban A., Shore R. A. Boolean algebras, tarski invariants, and index sets // Notre Dame Journal of Formal Logic. — 2006. — Vol. 47, no. 1. Pp. 1-23.

6. Dobritsa V. P. Complexity of the index set of a constructive model // Algebra and Logic. 1983. - Vol. 22. - Pp. 269-276.

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. Фокина E. Б. Индексные множества разрешимых моделей // Сиб.мат.журн. 2007. - Т. 48, Ш 5. - С. 1167-1179.

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

11. Goncharov S., Khoussainov В. Open problems in the theory of constructive algebraic systems // Computability Theory and Its Applications: Current Trends and Open Problems. — Vol. 257. — American Mathematical Society: 2000. Pp. 145-169.

12. Гончаров С. С., Найт Дж. Вычислимые структурные и антиструктурные теоремы // Алгебра и логика. — 2002. — Т. 41, № 6. — С. 639-681.

13. Добрица В. П. Вычислимость некоторых подклассов вычислимого класса конструктивных моделей // Сиб.мат.журн.— 1989.— Т. 30, № 3. — С. 45-51.

14. Добрица В. П. Сложность индексных множеств вычислимых классов с конечным числом конструктивных систем // Сиб.мат.жур.— 1986.— Т. 27, № 5. С. 68-74.

15. Добрица В. П. Структурные свойства вычислимых классов конструктивных моделей // Алгебра и логика. — 1987. — Т. 26, Я2 1. — С. 36-62.

16. Добрица В. П. Индексные множества в обобщённых вычислимых нумерациях // Мат.жури.2. 2002. - Т. 3, № 1. - С. 38-42.

17. Когабаев Н. Т. Сложность некоторых естественных проблем на классе вычислимых /-алгебр // Сиб. мат. журн. — 2006. — Т. 47, № 2. — С. 352360.

18. Винокуров Н. С. Индексные множества классов автоматных структур j j Сиб. мат. журн. 2006. - Т. 47, № 5. - С. 1019-1030.

19. Перетятькин М. Г. Конечно аксиоматизируемые классы. — Новосибирск: Научная книга, 1997.

20. Calvert W., Fokina E., Goncharov S. S. et al. Index sets for classes of high rank structures // J. Symbolic Logic. — 2007.— Vol. 72, no. 4.— Pp. 14181432.

21. Гончаров С. С., Хусаинов Б. X. Сложность теорий вычислимых категоричных моделей // Алгебра и логика. — 2004. — Т. 43, № 6. — С. 650-665.

22. Ryll-Nardzewski С. On the categoricity in power ^ No // Bull. Acad. Pol. Sci. Ser. Math., Astron., Phys. 1959. - Vol. 7. - Pp. 545-548.

23. Baldwin J. Т., Lachlan A. H. On strongly minimal sets // The J. of Symbolic Logic. 1971. - Vol. 36, no. 1. - Pp. 79-96.

24. Еримбетов M. M. О полных теориях с 1-кардинальными формулами // Алгебра и логика. 1975. — Т. 14, № 3. - С. 245-257.

25. Судоплатов С. В. Полные теории с конечным числом счетных моделей, i // Алгебра и логика. 2004. - Т. 43, № 1. - С. 110-124.

26. Нуртазин А. Т. Вычислимые классы и алгебраические критерии автоустойчивости: Дисс. .канд.физ.-мат. наук. / АН Казахской ССР. Ин-т математики и механики. Лаб. алгебры и логики. — Алма-Ата, 1974.

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

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

29. Адян С. И., Дурнев В. Г. Алгоритмические проблемы для групп и полугрупп // Успехи математических наук. — 2000. — Vol. 55, по. 2. — Pp. 4-94.

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

31. Еримбетов М. М. Категоричность в мощности и недвукардинальность формулы конечного ранга // Алгебра и логика. — 1974. — Т. 13, JY2 5. — С. 493-500.

32. Lempp S., Slaman Т. A. The complexity of the index sets of tto-categorical theories and of ehrenfeucht theories // Proc. of the North Texas Logic Conference, October 8-10, 2004. 2004.

33. Мальцев А. И. Алгебраические системы. — M.: Наука, 1970.— Pp. 312— 322.

34. Горбунов В. А. Алгебраическая теория квазимногообразий.— Новосибирск: Научная книга, 1999.

35. Goncharov S. S. Computability and computable models // Mathematical problems from applied logic. II / Ed. by S. S. G. Dov M. Gabbay, M. Za-kharyaschev. — New York: Springer, 2006. — Logics for the XXIst century.

36. Marker D. Non-En-axiomatizable almost strongly minimal theories // J. of Symbolic Logic. 1989. - Vol. 54. - Pp. 921-927.

37. Гаврюшкин A. H. Сложность эренфойхтовых моделей // Алгебра и логика. 2006. - Т. 45, № 5. - С. 507-519.

38. Marker D. Model theory: an introduction. Graduate texts in mathematics no. 217. — New York: Springer-Verlag, 2002.

39. Sacks G. E. Higher recursion theory // Perspectives in Mathematical Logic. — Berlin: Springer-Verlag, 1990.

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

41. Reed R. С. A decidable ehrenfeucht theory with exactly two hyperarithmetic models // Ann. Pure Appl. Logic. 1991. - Vol. 53, no. 1. - Pp. 135-168.

42. Гончаров С. С. Модели данных и языки их описаний // Вычислительные системы. — по. 107. — Pp. 52-70.

43. Ильичева О. А. О семантике квазитождеств определяющих модели констант // Вычислительные системы. — по. 116,— Pp. 16-32.

44. Касымов Н. X., Морозов А. С. Логические аспекты теории абстрактных типов данных // Вычислительные системы. — по. 122.— Pp. 73-96.

45. Мальцев А. И. Алгоритмы и рекурсивные функции. — М.: Наука, 1986. — С. 254-263.

46. Марков А. А. Теория алгорифмов // Труды мат.ин-та им. Стеклова. — 1954. № 42.

47. Попов В. Ю. Марковские свойства бернсайдовских многообразий групп // Алгебра и логика. 2003. - Т. 42, № 1. - С. 94-106.

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

49. Dobritsa V. P. Structural properties of computable classes of constructive models // Algebra i Logika. 1987. - Vol. 26, no. 1.- Pp. 24-41.

50. Павловский E. H. Алгоритмическая распознаваемость свойства конечности конечно-определённых систем // Материалы XLII международной научной студенческой конференции Студент и научно-технический прогресс. — Математика. — Новосибирск: 2004. — С. 14-15.

51. Павловский Е. Н. Оценка алгоритмической сложности классов вычислимых моделей // Материалы XLIV международной научной студенческой конференции Студент и научно-технический прогресс. — Математика. — Новосибирск: 2006. С. 76-77.

52. Павловский Е. Н. Алгоритмическая распознаваемость свойства конечности конечно-определённых систем // Вестник НГУ. Серия: математика, механика, информатика. — 2006. — Т. 6, № 4. — С. 83-92.

53. Pavlovsky Е. N. Estimation of algorithmic complexity of computable models classes // Book of abstracts, Logic Colloquium'07. — Wroclaw, Poland: 2007.-P. 91.

54. Павловский E. H. Оценка алгоритмической сложности классов вычислимых моделей // Сиб. мат. журн. — 2008. — Т. 49, № 3.

55. Павловский Е. Н. Индексные множества простых моделей // Сибирские электронные математические известия. — 2008. — Т. 5.

56. Павловский Е. Н. Сложность индексных множеств некоторых классов моделей // Вестник НГУ. Серия: математика, механика, информатика. 2008. - Т. 8, № 1. - С. 71-76.