Автоморфизмы автоматных структур

Винокуров, Никита Сергеевич

Автоморфизмы автоматных структур тема автореферата и диссертации по математике, 01.01.06 ВАК РФ

Винокуров, Никита Сергеевич АВТОР

кандидата физико-математических наук УЧЕНАЯ СТЕПЕНЬ

Новосибирск МЕСТО ЗАЩИТЫ

2006 ГОД ЗАЩИТЫ

01.01.06 КОД ВАК РФ

Диссертация по математике на тему «Автоморфизмы автоматных структур»

Автореферат диссертации на тему "Автоморфизмы автоматных структур"

На правах рукописи УДК 510.51+51Д716.35

л''

Винокуров Никита Сергеевич/

Автоморфизмы автоматных структур

(01.01.06 - математическая логика, алгебра и теория чисел)

Автореферат

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

Новосибирск 2006

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

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

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

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

доктор физико-математических наук, доцент Иван Анатольевич Мальцев

Ведущая организация:

Иркутский государственный университет.

Защита диссертации состоится 1 июня 2006 г. в 15 час. 00 мин. на заседании Диссертационного Совета К 212.174.01 Новосибирского государственного университета по адресу: 630090, Новосибирск-90, ул. Пи-рогова, 2.

С диссертацией можно ознакомиться в библиотеке Новосибирского государственного университета.

Автореферат разослан апреля 2006 г.

Ученый секретарь совета

кандидат физико-математических наук

кандидат физико-математических наук, с.н.с. Николай Вячеславович Шилов

А.Д.Больбот

/&С.ЭЛ-

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность темы. Впервые понятие автоматной структуры появилось в 1995 году в работе Б. Хусаинова и А. Нероуда [14]. Напомним это определение

Определение 1 Пусть £ — некоторый конечный алфавит. Обозначим через Хф алфавит ¡С и {<)}, где <С> ^ £. Тогда конволюцией кортежа (шх,...,шп) 6 (£*)" назовём кортеж (шх€ полученный добавлением наименьшего числа символов О к правым концам шг,\ < г < п, так, чтобы все получившиеся слова имели одинаковую длину. Конволюцией отношения Я С (£*)" назовём отношение Я^ С (£ф)п, сформированного как множество конволюций всех кортежей в Я.

Определение 2 Будем говорить, что отношение Я С (£*)" распознаваемо конечным автоматом, если его конволюция Я^ распознаваема конечным автоматом над алфавитом

Определение 3 Будем говорить, что структура

автоматна над £, если её носитель Л С Е", и все отношения Я^ С (£*)"• распознаваемы конечными автоматами. Будем говорить, что структура автоматна, если она автоматна над некоторым алфавитом. Если существует изоморфизм между некоторой структурой В и автоматной структурой А, тогда В называется автоматно пред-ставимой (над 12), и структура А называется автоматной копией структуры В, а изоморфизм называется автоматным представлением структуры В.

Эти объекты сразу же привлекли внимание исследователей, потому что они , как было показано в работе Е.Грёделя и А.Блумензаца[12] , обладали разрешимой теорией. Более того соответствующий разрешающий алгоритм строится равномерно по автоматному представлению модели.

РОС. НАЦИОНАЛЬНАЯ БИБЛИОТЕКА С.-Петербург

03 ак>6>кт Ч(О

структур сложность проблемы изоморфизма была вычислена в совместной работе Б. Хусаинова, С.Рубина. А. Ниса и Ф. Штефана [19], и оказалась, несмотря на всю простоту автоматных моделей, максимально сложной, а именно Ej-полной.

Также естественным вопросом является характеризация различных классов автоматных структур. В этом направлении было получено несколько интересных результатов. Г. Оливером и P.M. Томасом в [22] полностью описаны конечнопорождённые автоматные группы, это в точности почти абелевы группы. Б. Хусаиновым, А.Нисом, С. Рубиным, Ф.Штефаном в [19] описаны автоматные булевы алгебры, это все конечные и алгебры вида ®шх„,п 6 ш. Там же описаны автоматные кольца целостности, это в точности все конечные. В [13] Ц. Делхом, В. Горанко, Т. Кнапик описали все автоматные ординалы, это все ординалы вида шп,п < и>, основываясь на этой работе Б. Хусаинов, С. Рубин, Ф. Ште-фан в [17] получили важное свойство автоматных линейных порядков: любой автоматный линейный порядок имеет конечный ранг. Проблема описания автоматных линейных порядков пока открыта. В совместной работе Б. Хусаинова, С. Рубина и X. Ишихары [16] была доказана теорема, в некотором смысле сводящая изучение автоматных структур к изучению автоматных графов. По любой автоматной структуре А эффективно строится автоматный граф С {Л), так что многие важные свойства со структур переносятся на графы например, если А\ = А2, то С{А\) — С(А2). В частности из этого следует, что для класса автоматных графов проблема изоморфизма £} -полна.

Следует также отметить работу Д. Куске [20], в которой он доказывает некоторый автоматный аналог известной теоремы Кантора, говорящей о том, что любой счётный линейный порядок вкладывается в (Q, <). Он показывает, что для любого автоматного порядка L существует автоматное представление Ql рациональных чисел, такое что L автоматно вкладывается в Q^. Пока неизвестно, существует ли автоматное представление Q рациональных чисел, такое что любой автоматный порядок в него автоматно вкладывается. Кроме того он показывает автоматную однородность автоматной модели ({0,1}*, являющейся автоматным представлением рациональных чисел с порядком. Наличие автоматной однородности крайне важно для изучения группы автоматных автоморфизмов ({0,1}*, ^¡п).

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

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

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

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

Методы исследования.В работе используются методы построения автоматных моделей, развитые в работах [20, 23, 19, 16, 11, 17]. Научная новизна. Все результаты являются новыми, получены автором самостоятельно и снабжены подробными доказательствами. Практическая ценность. Работа носит теоретический характер. Ее результаты могут найти применение в дальнейших исследованиях в теории автоматных моделей.

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

зультаты:

1. Получены точные оценки ряда индексных множеств алгебраических свойств автоматных моделей (проблема автоматного изоморфизма, вложения, вычислимого изоморфизма и др.)

2. Получены точные оценки ряда индексных множеств теоретико-модельных свойств автоматных моделей (однородности, универсальности и др.)

•

3. Доказана неразрешимость групп автоматных автоморфизмов некоторых автоматных моделей.

4. Построены примеры теорий, автоматный спектр которых может.' принимать все значения кроме 2. Для 2 вопрос построения такой теории, пока остаётся открытым.

Апробация. Результаты работы были представлены на ХЫ международной научной студенческой конференции, на XXVI Конференции молодых ученых механико-математического факультета МГУ им. М.В.

Ломоносова, на IX азиатской логической конференции, на ХЫУ международной научной студенческой конференции. А также на семинарах "Автоматы и сложность вычислений" и "Конструктивные модели" Новосибирского государственного университета.

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

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

СОДЕРЖАНИЕ ДИССЕРТАЦИИ

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

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

Проблема вычислимого изоморфизма для различных классов моделей (важная подпроблема проблемы изоморфизма) интересовала многих исследователей. В частности, в совместной работе С.С. Гончарова и Дж. Найт [2] была найдена оценка проблемы вычислимого изоморфизма для ряда классов: линейных порядков, булевых алгебр, моделей эквивалентностей и др. В работе Н.Т. Когабаева [7] была найдена оценка проблемы вычислимого изоморфизма для вычислимых /-алгебр. Мы оценим проблему вычислимого изоморфизма для класса всех автоматных структур. Также мы будем оценивать и проблему автоматного изоморфизма, крайне естественную именно для автоматных структур.

Эти и сопутствующие им результаты изложены в теоремах 3,4,6,7 и следствиях 4,5,6. Все основные результаты первой главы вместе с известным результатом Б.Хусаинова, Рубина, Ниса и Штефана о полноте проблемы изоморфизма, доказанным в работе [19] отображены в следующей таблице:

проблема изоморфизма проблема автоморфизма проблема вложения проблема автоморфизма, переводящего выделенный элемент в выделенный элемент

автоматного «Ejf » Е? «Е*

вычислимого «ЕЗ > Е Ч «28

любого ~ V1 > Е" «Е{

В первой масти второй главы изучаются индексные множества таких свойств, как однородность и автоматная однородность. Зафиксируем гёделевскую нумерацию (21„)п6ш всех автоматных структур над алфавитом Е. Напомним, что модель 21 однородна, если для любых кортежей а, Ъ из выполнения условия (21, а) = (21, Ь) следует существование автоморфизма, переводящего кортеж а в кортеж Ь. Однородность модели — это важное теоретико-модельное свойство. Поэтому важно дать характеризацию классу всех автоматных однородных моделей. Оценка, полученная в следующей теореме:

Теорема 9. Множество Нот = {n | 21„ однородна } — -полно.,

оставляет надежду получить не очень сложную характеризацию класса всех автоматных моделей. Кроме того результат сам по себе является интересным, поскольку отвечает на вопрос: "Насколько сложно определить по виду автоматной структуры, является ли она однородной?"

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

Определение 4 Назовём автоматную структуру 21 автоматно однородной, если для любых кортежей а, Ь из выполнения условия (21, а) — (21, Ь) следует существование автоматного автоморфизма, переводящего кортеж а в кортеж Ь.

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

Теорема 10. Множество AHom = {п ¡ 21„ автоматно однородна } — полно.

Во второй части второй главы изучаются индексные множества таких свойств, как универсальность и универсальность в классе автоматных моделей. Напомним, что модель 21 универсальна, если для любой модели 03, такой что 21 = 03 и мощность модели © не превосходит мощности модели 21, существует элементарное вложение © в 21.

По аналогии с этим определением мы определим универсальность в классе автоматных моделей следующим образом:

Определение 5 Автоматная модель 21 универсальна в классе автоматных моделей, если для любой автоматной модели ©, такой что 21 = 03, существует элементарное вложение © в 21.

Основные результаты второй части второй главы, изложенные в теореме 11, и следствиях 7, 8 показывают, что проблема универсальности крайне сложна для распознавания.

Теорема 11. Множество Un = {п | 21„ универсальна в классе автоматных моделей} — -полно.

Следствие 7. Множество универсальных автоматных структур не менее чем Е]—полное.

Следствие 8. Множество универсальных вычислимых структур не менее чем Ej —полное.

Первая часть третьей главы посвящена изучению автоматного спектра теории,

Определение 6 Назовём автоматным спектром Sp а (Г) полной теории Т число попарно неизоморфных моделей теории Т, имеющих автоматное представление. Если у теории Т таких моделей нет, то спектр теории Spа(Т) = 0. Если у теории Т существует бесконечно таких моделей, то спектр теории БрДТ1) = ш.

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

Теорема 12. Для любого п > 3 существует теория Тп, такая что выполнено равенство Spa(T„) = п.

Легко строятся примеры теорий с автоматными спектрами равными 0,1.и, таким образом пока остаётся открытым вопрос, может ли автоматный спектр теории принимать значение в точности равное 2.

Вторая часть третьей главы посвящена рассмотрению групп автоматных автоморфизмов некоторых автоматных структур. А именно, рассматриваются группа автоматных перестановок счётного множества и группа автоматных автоморфизмов модели Q = ({0,1}*, -<их) — автоматного представления множества рациональных чисел с порядком. В работе [5] A.C. Морозов показал, что группа вычислимых перестановок счётного множества имеет неразрешимую теорию, более того элементарная теория этой группы вычислимо изоморфна множеству всех предложений истинных в арифметике. В теореме 13 и следствии 9 доказывается автоматный аналог этого результата.

Теорема 13. В Auta({0,1}*) определима с параметрами стандартная модель арифметики. При этом класс таких параметров также является формульным.

Следствие 9. Элементарная, теория группы Auto({0,1}*) неразрешима. Более того, она вычислимо изоморфна множеству всех предложений, истинных в стандартной модели арифметики.

Заметим, что доказательство этого утверждения остается верным также и для любой группы Aut a{L), где L — произвольный бесконечный регулярный язык. Также с точки зрения теории автоматных моделей интересно следующее следствие:

Следствие 10. Пусть L произвольный бесконечный регулярный язык. Тогда группа Auta(L) не имеет автоматного представления.

В совместной работе A.C. Морозова и Дж. К. Трасса [21] показывается, что группа вычислимых автоморфизмов рациональных чисел с порядком имеет неразрешимую теорию, более того элементарная теория этой группы вычислимо изоморфна множеству всех предложений истинных в арифметике. И опять же интересен вопрос есть ли автоматный аналог этого результата. В теореме 14 и следствии 11, доказывается более слабый результат, а именно, показывается, что теория структуры Aut а (Q) наследственно неразрешима.

Теорема 14. В группе автоматных автоморфизмов Aut а (Q) структуры Q определяется с параметрами арифметика.

Следствие 11. Теория структуры Aut a(Q) наследственно неразрешима.

К сожалению, пока неизвестно верно ли, что элементарная теория группы Aut а (Q) вычислимо изоморфна множеству всех предложений истинных в арифметике. Также интересно и следующее следствие.

Следствие 12. Структура Aut a(Q) не имеет автоматного представления.

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

Автор выражает глубокую признательность своему научному руководителю A.C. Морозову за постановку задач, постоянное внимание к работе и всестороннюю поддержку.

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

[1] С.С. Гончаров, Ю.Л.Ершов. Теория конструктивных моделей, Новосибирск, Научная книга, 1999.

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

[3] Ю.Л.Ершов Неразрешимость теорий симметрических и простых конечных групп // ДАН СССР, 158, №4, 1964, стр. 777-779.

[4] Ю Л.Ершов Проблемы разрешимости и конструктивные модели, М.: Наука, 1980.

[5] A.C. Морозов. Перестановки и неявная определимость // Алгебра и логика, Т. 27, №1, стр. 19-36, 1988.

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

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

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

[9] Дж.Е. Сакс- Теория насыщенных моделей, М., Мир, 1976.

[10] Bennett С. Logical reversibility of computation //IBM J. Res. Develop. 1973. V. 17. P. 525-532.

[11] Blumensath A. Diploma thesis. RWTH Aachen, 1999.

[12] Blumensath A., Grddel Automatic structures // Proc. 15th IEEE Symp. on Logic in Computer Science. Santa Barbara (California), 2000. P. 51-62.

[13] C. Delhomme, V. Goranko, T. Knapik Automatic linear orderings. Not published, 2003.

[14] B. Khoussainov, A. Nerode Automatic presentations of structures // Lecture notes in computer science, 960:367-392, 1995.

[15] Khoussainov В., Nerode A.. Automata theory and its applications. 2001. Birkhauser, Boston etc.

[16] Khoussainov В., Rubin S., Ishihara H. On isomorphism invariants of some automatic structures // Proc. 17th IEEE Symp. on Logic in Computer Science, 2002, Copenhagen (Denmark), pp. 43-53.

[17] Khoussainov В., S. Rubin, F. Stephan Automatic linear orders and trees // 2003a. CDMTSC technical report 208, department of computer science, university of Auckland.

[18] Khoussainov В., S. Rubin, F. Stephan Definability and regularity in automatic presentations of subsystems of arithmetic // 2003b. CDMTSC technical report 209, department of computer science, university of Auckland.

[19] Khoussainov В., Nies A., Rubin S., Stephan F. Automatic structures: richness and limitations // Proc. 19th IEEE Symp. on Logic in Computer Science, 2004, Turku (Finland), pp 44-53.

[20] D. Kuske. Is Cantor's theorem automatic? // Proceedings of the 10th International Conferenca on Logic for Programming, Artificial Intelligence, and Reasoning (LPAR). 2850:332-345, 2003.

[21] A.S. Morozov, J.К. Truss. On computable automorphism of the rational numbers // The Journal of symbolic Logic, v.66, №3, pp 1458 - 1469, 2001.

[22] G. Oliver and R.M. Thomas. Automatic Presentations of Finitely Generated Groups, V. Diekert and B. Durand (Eds.): STACS '05, Logic Notes in computer science 3404, pp. 693-704, 2005 University of Stuttgart, Germany.

[23] S. Rubin. Automata structures. PhD thesis. University of Auckland, 2004.

[24] J.K. Truss. On recovering structures from quotients of their automorphism groups // Ordered groups and infinite permutations groups (W. Carles Holland, editor), Kltiwer, 1996, pp 63-95.

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

[25] Я. С. Винокуров. Сложность некоторых естественных проблем в автоматных структурах // Сибирский математический журнал, т.46, №1, стр. 71 - 78, 2005.

[26] Н. С. Винокуров. Индексные множества классов автоматных структур // Сибирский математический журнал, принята к печати.

[27] Н.С. Винокуров. Группы автоматных автоморфизмов некоторых автоматных структур // Сибирские электронные математические известия, http://semr.math.nsc.ruT. 3, стр. 145-152, 2006.

[28] Н.С Винокуров.Индексные множества классов автоматных структур // Сибирские электронные математические известия, http://semr.math.nsc.ru т.З, стр. 153-154, 2006.

[29] Н С. Винокуров. Об автоматных структурах // Материалы XLI международной научной студенческой конференции "Студент и научно технический прогресс", Новосибирск, 2003, стр 3.

[30] Н.С. Винокуров. Об автоматном спектре теорий // Материалы XLIV международной научной студенческой конференции "Студент и научно технический прогресс", Новосибирск, 2006, стр. 66.

И. С Винокуров. Сложность проблем автоматного изоморфизма и автоморфизма в автоматных структурах // Материалы XXVI конференции молодых учёных механико-математического факультета МГУ им. М.В. Ломоносова, Москва, 2004, стр 30.

Винокуров Никита Сергеевич

АВТОМОРФИЗМЫ АВТОМАТНЫХ СТРУКТУР

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

Подписано в печать 25.04.06 Формат 60x84 1/16

Печать офсетная Усл.печ.л. 1.0

Заказ № 200 Тираж 100

Лицензия ЛР №021285 от 6 мая 1998 г. Отпечатано на полиграфическом участке НГУ, 630090, Новосибирск 90, ул.Пирогова 2

[

ACOéA

-fGLbJL

P 1 02 32

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

1 Введение

1.1 Основные определения и предварительные сведения.

2 Индексные множества алгебраических свойств автоматных структур

2.1 Автоматные алгебраические свойства.

2.2 Вычислимые алгебраические свойства.

2.3 Общие алгебраические свойства.

3 Индексные множества теоретико-модельных свойств автоматных структур

3.1 Однородность

3.2 Универсальность.

4 Теоретико-модельные свойства автоматных структур

4.1 Автоматный спектр теорий.

4.2 Группы автоматных автоморфизмов некоторых автоматных структур

Введение диссертация по математике, на тему "Автоморфизмы автоматных структур"

На сегодняшний момент получила широкое распространение теория конструктивных моделей (см. книги С.С. Гончарова, Ю.Л. Ершова [1], Ю.Л. Ершова [4]), появившаяся на стыке теории моделей (см. книгу Г. Кейслера, Ч.Ч. Чэна [6], Дж.Е. Сакса [9]) и теории вычислимости (см. монографию X. Роджерса [8]), изучающая свойства объектов, вычисляемых произвольными алгоритмами (машинами Тьюринга). В связи с резким развитием вычислительной техники появилась потребность в изучении не каких-то абстрактных вычислимых объектов, а вполне конкретных, вычисляемых за определённое время, т.е. надо было каким то образом сделать ограничение на вычисляющий алгоритм (вы-числяющеую машину), чтобы вычисляемый объект обладал достачно хорошими свойствами.

Появился ряд различных определений: структуры, вычислимые за полиномиальное время, вычислимые на машинах Тьюринга с ограниченной лентой и т.д. В частности в 1995 году в работе Б. Хусаинова и А. Нероуда [14] появилось понятие автоматной структуры, т.е. структуры, вычислимой с помощью конечного автомата. Напомним это определение.

Пусть А обозначает пустое слово. Пусть £ — некоторый конечный алфавит. Тогда £* будет обзначать множество всех слов над этим алфавитом, а £+ будет обозначать Е* \ {Л}.

Определение 1 Пусть Е — некоторый конечный алфавит. Обозначим через £<> алфавит £и{0}, где 0 ^ Е. Тогда конволюцией кортео/са (wi, .,шп) € (£*)" назовём кортеж (uii, 6 (££>)", полученный добавлением наименьшего числа символов ф к правым концам 1 < г < п, так, чтобы все получившиеся слова имели одинаковую длину. Конволюцией отношения R С (Е*)п назовём отношение R^ С (Е^)п, сформированного как множество конволюций всех кортежей в R.

Определение 2 Будем говорить, что отношение R С (£*)" распознаваемо конечным автоматом, если его конволюция R? распознаваема конечным автоматом над алфавитом (Е^)71.

Определение 3 Будем говорить, что структура автоматна над Е, если её носитель А С £*, и все отношения Rf С (£*)"' распознаваемы конечными автоматами. Будем говорить, что структура автоматна, если она автоматна над некоторым алфавитом. Если существует изоморфизм между некоторой структурой В и автоматной структурой А, тогда В называется автоматно представимой (над Е), и структура А называется автоматной копией структуры В, а изоморфизм называется автоматным представлением структуры В.

Эти объекты сразу же привлекли внимание исследователей, т.к. с ними было довольно просто работать, кроме того автоматные модели, как было показано в работе Е.Грёделя и А.Блумензаца[12], обладали разрешимой теорией, а именно была доказана следующая теорема:

Теорема 1 ([12]) Для любой автоматной структуры А, множество всех FO(3-предложений, истинных в структуре А, разрешимо, где F0(3°°) язык первого порядка, обогащенный квантором 3°° (существует бесконечно много).

Из доказательства этой теоремы следует, что соответствующий разрешающий алгоритм строится равномерно по автоматному представлению модели. Из доказательства теоремы также легко получается следующее важное замечание:

Замечание 1 Любые формульные отношения языка FO(3°°) на автоматной структуре являются автоматными.

В теории моделей хорошо известно понятие относительной элементарной определимости, введённое Ю.Л. Ершовым в работе [4]. Оказалось, что любая структура, относительно элементарно определимая в автоматной, также является автоматной. Кроме того существуют автоматные структуры, являющиеся полными относительно определимости. Например,

Wk = (e*,(ffe)a6e,^p,eo, где £ = {О,.,А; — 1}, бинарное отношение аа выполняется на парах (w,wa), бинарное отношение -<р есть отношение приставки и бинарное отношение el выполняется на словах равной длины. В работе А. Блумензаца [11] появилась характеризация автоматных структур в терминах этих полных структур. Автоматные модели это в точности те модели, которые относительно элементарно определимы в W* для к > 2.

Естественный вопрос, возникающий при задании бесконечного объекта конечным, это по двум данным конечным объектам, задающим разные бесконечные, понять изоморфны ли эти бесконечные объекты. Эта проблема называется проблемой изоморфизма. Для автоматных структур сложность проблемы изоморфизма была вычислена в совместной работе Б. Хусаинова, С.Рубина, А. Ниса и Ф. Штефана [19], и оказалась, несмотря на всю простоту автоматных моделей, максимально сложной, а именно £}-полной.

Штефан в [17] получили важное свойство автоматных линейных порядков: любой автоматный линейный порядок имеет конечный ранг. Проблема описания автоматных линейных порядков пока открыта. В совместной работе Б. Хусаи-нова, С. Рубина и X. Ишихары [16] была доказана теорема, в некотором смысле сводящая изучение автоматных структур к изучению автоматных графов. По любой автоматной структуре Л эффективно строится автоматный граф С {Л), так что многие важные свойства со структур переносятся на графы например, если Л\ = Л2, то С(А\) = С(Лг). В частности из этого следует, что для класса автоматных графов проблема изоморфизма £{-полна.

Следует также отметить работу Д.Куске [20], в которой он доказывает некоторый автоматный аналог известной теоремы Кантора, говорящей о том, что любой счётный линейный порядок вкладывается в (Q, <). Он показывает, что для любого автоматного порядка L существует автоматное представление <Q>£ рациональных чисел, такое что L автоматно вкладывается в Q^. Пока неизвестно, существует ли автоматное представление Q рациональных чисел, такое что любой автоматный порядок в него автоматно вкладывается. Кроме того он показывает автоматную однородность автоматной модели ({0,1}*, z</ei), являющейся автоматным представлением рациональных чисел с порядком. Наличие автоматной однородности крайне важно для изучения группы автоматных автоморфизмов ({0, 1}*, -<1ех)

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

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

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

3. Доказана неразрешимость групп автоматных автоморфизмов некоторых автоматных моделей.

4. Построены примеры теорий, автоматный спектр которых может принимать все значения кроме 2. Для 2 вопрос построения такой теории, пока остаётся открытым.

В работе используются методы построения автоматных моделей, развитые в работах [20, 23, 19, 1С, 11, 17].

Результаты работы были представлены на XLI международной научной студенческой конференции, на XXVI Конференции молодых ученых механико-математического факультета МГУ им. М.В. Ломоносова, на IX азиатской логической конференции, на XLIV международной научной студенческой конференции. А также на семинарах "Автоматы и сложность вычислений" и "Конструктивные модели" Новосибирского государственного университета.

Все основные результаты диссертации опубликованы в работах [25], [26], [27], [28], [29], [30], [31]

Диссертация состоит из введения, трёх глав, разбитых на параграфы, и списка литературы. Нумерация утверждений сквозная. Список литературы содержит 30 наименований. Объём диссертации составляет 63 страницы.

Список источников диссертации и автореферата по математике, кандидата физико-математических наук, Винокуров, Никита Сергеевич, Новосибирск

1. Blumensath A., Gradel ^.Automatic structures // Proc. 15th IEEE Symp. on Logic in Computer Science. Santa Barbara (California), 2000. P. 51-62.

2. С. Delhomme, V. Goranko, Т. Knapik Automatic linear orderings. Not published, 2003.

3. B. Khoussainov, A. N erode Automatic presentations of structures // Lecture notes in computer science, 960:367-392, 1995.

4. Khoussainov В., Nerode A. Automata theory and its applications. 2001. Birkhauser, Boston etc.

5. Khoussainov В., Rubin S., Ishihara H. On isomorphism invariants of some automatic structures // Proc. 17th IEEE Symp. on Logic in Computer Science, 2002, Copenhagen (Denmark), pp. 43-53.

6. Khoussainov В., S. Rubin, F. Stephan Automatic linear orders and trees // 2003a. CDMTSC technical report 208, department of computer science, university of Auckland.

7. Khoussainov В., S. Rubin, F. Stephan Definability and regularity in automatic presentations of subsystems of arithmetic // 2003b. CDMTSC technical report 209, department of computer science, university of Auckland.

8. Khoussainov В., Nies A., Rubin S., Stephan F. Automatic structures: richness and limitations // Proc. 19th IEEE Symp. on Logic in Computer Science, 2004, Turku (Finland), pp 44-53.

9. D. Kuske. Is Cantor's theorem automatic? // Proceedings of the 10th International Conferenca on Logic for Programming, Artificial Intelligence, and Reasoning(LPAR). 2850:332-345, 2003.

10. A.S. Morozov, J.K. Truss. On computable automorphism of the rational numbers // The Journal of symbolic Logic, v.66, №3, pp 1458 1469, 2001.

11. G. Oliver and R.M. Thomas. Automatic Presentations of Finitely Generated Groups, V. Diekert and B. Durand (Eds.): STACS '05, Logic Notes in computer science 3404, pp. 693-704, 2005 University of Stuttgart, Germany.

12. S. Rubin. Automata structures. PhD thesis. University of Auckland, 2004.

13. J.K. Truss. On recovering structures from quotients of their automorphism groups // Ordered groups and infinite permutations groups (W. Carles Holland, editor), Kluwer, 1996, pp 63-95.РАБОТЫ АВТОРА ПО ТЕМЕ ДИССЕРТАЦИИ

14. Н.С. Винокуров. Сложность некоторых естественных проблем в автоматных структурах // Сибирский математический журнал, т.46, №1, стр. 71 -78, 2005.

15. Н.С. Винокуров. Индексные множества классов автоматных структур // Сибирский математический журнал, принята к печати.

16. Н.С. Винокуров. Группы автоматных автоморфизмов некоторых автоматных структур // Сибирские электронные математические известия, http://semr.math.nsc.ru, т. 3, стр. 145-152, 2006.

17. Н.С. Винокуров. Индексные множества классов автоматных структур // Сибирские электронные математические известия, http://semr.math.nsc.ru, т.З, стр. 153-154, 2006.

18. Н.С. Винокуров. Об автоматных структурах // Материалы XLI международной научной студенческой конференции "Студент и научно технический прогресс", Новосибирск, 2003, стр 3.