Содержание к диссертации
Введение
1.1 Основные определения и предварительные сведения 13
2 Индексные множества алгебраических свойств автоматных структур 17
2.1 Автоматные алгебраические свойства 17
2.2 Вычислимые алгебраические свойства 24
2.3 Общие алгебраические свойства 26
3 Индексные множества теоретико-модельных свойств автоматных структур 30
3.1 Однородность 30
3.2 Универсальность 35
4 Теоретико-модельные свойства автоматных структур 42
4.1 Автоматный спектр теорий 42
4.2 Группы автоматных автоморфизмов некоторых автоматных структур 48
Список литературы
- Вычислимые алгебраические свойства
- Общие алгебраические свойства
- Универсальность
- Группы автоматных автоморфизмов некоторых автоматных структур
Введение к работе
На сегодняшний момент получила широкое распространение теория конструктивных моделей (см. книги С.С. Гончарова, Ю.Л. Ершова [1], Ю.Л. Ершова [4]), появившаяся на стыке теории моделей (см. книгу Г. Кейслера, Ч.Ч. Чэна [6], Дж.Е. Сакса [9]) и теории вычислимости (см. монографию X. Роджерса [8]), изучающая свойства объектов, вычисляемых произвольными алгоритмами (машинами Тьюринга). В связи с резким развитием вычислительной техники появилась потребность в изучении не каких-то абстрактных вычислимых объектов, а вполне конкретных, вычисляемых за определённое время, т.е. надо было каким то образом сделать ограничение на вычисляющий алгоритм (вы-числяющеую машину), чтобы вычисляемый объект обладал достачно хорошими свойствами.
Появился ряд различных определений: структуры, вычислимые за полиномиальное время, вычислимые на машинах Тьюринга с ограниченной лентой и т.д. В частности в 1995 году в работе Б. Хусаинова и А. Нероуда [14] появилось понятие автоматной структуры, т.е. структуры, вычислимой с помощью конечного автомата. Напомним это определение.
Пусть Л обозначает пустое слово. Пусть Е — некоторый конечный алфавит. Тогда Е* будет обзначать множество всех слов над этим алфавитом, а Е+ будет обозначать Е* \ {Л}.
Определение 1 Пусть Е — некоторый конечный алфавит. Обозначим через Еф алфавит Еи{0}, где 0 . Е. Тогда конволюцией кортеоіса (wi,..., ип) Є (Е*)п назовём кортеж (wi, ...,tun)^ Є (Е^)", полученный добавлением наименьшего числа символов ф к правым концам Ші, 1 < г < п, так, чтобы все получившиеся слова имели одинаковую длину. Конволюцией отношения R С (Е*)п назовём отношение R^ С (Ел)п, сформированного как множество конволюций всех кортежей в R.
Определение 2 Будем говорить, что отношение R С (*)" распознаваемо конечным автоматом, если его конволюция R? распознаваема конечным автоматом над алфавитом (Е^).
Определение 3 Будем говорить, что cmpyKmxjpa
A=(A,R*,...,R,ci,...,c*)
автоматна над Е, если её носитель А С *, и все отношения Rf С (Е*)Пі распознаваемы конечными автоматами. Будем говорить, что структура автоматна, если она автоматна над некоторым алфавитом. Если существует изоморфизм между некоторой структурой В и автоматной структурой А, тогда В называется автоматно представимой (над Т,), и структура А называется автоматной копией структуры В, а изоморфизм называется автоматным представлением структуры В.
Эти объекты сразу же привлекли внимание исследователей, т.к. с ними было довольно просто работать, кроме того автоматные модели, как было показано в работе Е.Грёделя и А.Блумензаца[12], обладали разрешимой теорией, а именно была доказана следующая теорема:
Теорема 1 ([12]) Для любой автоматной структуры А, множество всех FO(3)-предложений, истинных в структуре А, разрешимо, где F0(3) язык первого порядка, обогащенный квантором 3 (существует бесконечно много).
Из доказательства этой теоремы следует, что соответствующий разрешающий алгоритм строится равномерно по автоматному представлению модели. Из доказательства теоремы также легко получается следующее важное замечание:
Замечание 1 Любые формульные отношения языка FO(3) па автоматной структуре являются автоматными.
В теории моделей хорошо известно понятие относительной элементарной определимости, введённое Ю.Л. Ершовым в работе [4]. Оказалось, что любая структура, относительно элементарно определимая в автоматной, также является автоматной. Кроме того существуют автоматные структуры, являющиеся полными относительно определимости. Например,
Wk = (Е*,(ав)аЄЕі^ріЄОі
где = {0,...,к — 1}, бинарное отношение аа выполняется на парах (w,wa), бинарное отношение -<р есть отношение приставки и бинарное отношение el выполняется на словах равной длины. В работе А. Блумепзаца [11] появилась характеризация автоматных структур в терминах этих полных структур. Автоматные модели это в точности те модели, которые относительно элементарно определимы в Wk для к > 2.
Естественный вопрос, возникающий при задании бесконечного объекта конечным, это по двум данным конечным объектам, задающим разные бесконечные, понять изоморфны ли эти бесконечные объекты. Эта проблема называется проблемой изоморфизма. Для автоматных структур сложность проблемы изоморфизма была вычислена в совместной работе Б. Хусаинова, С.Рубина, А. Ниса и Ф. Штефана [19], и оказалась, несмотря на всю простоту автоматных моделей, максимально сложной, а именно }-полной.
Также естественным вопросом является характеризация различных классов автоматных структур. В этом направлении было получено несколько интересных результатов. Г. Оливером и P.M. Томасом в [22] полностью описаны конеч-нопорождённые автоматные группы, это в точности почти абелевы группы. Б. Хусаиновым, А.Нисом, С. Рубиным, Ф.Штефаном в [19] описаны автоматные булевы алгебры, это все конечные и алгебры вида Q3w><n,n Є ш. Там же описаны автоматные кольца целостности, это в точности все конечные. В [13] Ц. Делхом, В. Горанко, Т. Кнапик описали все автоматные ординалы, это все ординалы вида шп,п < со, основываясь на этой работе Б. Хусаинов, С. Рубин, Ф.
Штефан в [17] получили важное свойство автоматных линейных порядков: любой автоматный линейный порядок имеет конечный ранг. Проблема описания автоматных линейных порядков пока открыта. В совместной работе Б. Хусаи-нова, С. Рубина и X. Ишихары [16] была доказана теорема, в некотором смысле сводящая изучение автоматных структур к изучению автоматных графов. По любой автоматной структуре Л эффективно строится автоматный граф С (Л), так что многие важные свойства со структур переносятся на графы например, если Л\ = Л2, то С(Л\) = С(Лг). В частности из этого следует, что для класса автоматных графов проблема изоморфизма Ej-полна.
Следует также отметить работу Д.Куске [20], в которой он доказывает некоторый автоматный аналог известной теоремы Кантора, говорящей о том, что любой счётный линейный порядок вкладывается в (Q, <). Он показывает, что для любого автоматного порядка L существует автоматное представление Qi рациональных чисел, такое что L автоматно вкладывается в Ql. Пока неизвестно, существует ли автоматное представление Q рациональных чисел, такое что любой автоматный порядок в него автоматно вкладывается. Кроме того он показывает автоматную однородность автоматной модели ({0,1}*, zei), являющейся автоматным представлением рациональных чисел с порядком. Наличие автоматной однородности крайне важно для изучения группы автоматных автоморфизмов ({0,1}*, -<1ех)-
В данной работе делается попытка изучения автоматных структур с точки зрения теории вычислимости. А именно, проводится исследование сложности индексных множеств.
Определение сложности индексных множеств различных свойств автоматных структур важно с нескольких точек зрения :
1. Если сложность оказывается не очень высокая, то как правило структуры, обладающие этими свойствами, можно описать в терминах каких-нибудь не очень сложных инвариантов, т.е. изучение индексных множеств каких-
либо свойств напрямую связано с описанием моделей, обладающих этими свойствами.
2. Сложность определения по конечному заданию бесконечного объекта каких либо свойств этого объекта — задача сама по себе естественная и представляет особый интерес.
В работе получены следующие основные результаты:
Получены точные оценки ряда индексных множеств алгебраических свойств автоматных моделей (проблема автоматного изоморфизма, вложения, вычислимого изоморфизма и др.)
Получены точные оценки ряда индексных множеств теоретико-модельных свойств автоматных моделей (однородности, универсальности и др.)
Доказана неразрешимость групп автоматных автоморфизмов некоторых автоматных моделей.
Построены примеры теорий, автоматный спектр которых может принимать все значения кроме 2. Для 2 вопрос построения такой теории, пока остаётся открытым.
В работе используются методы построения автоматных моделей, развитые в работах [20, 23, 19, 1С, 11, 17].
Результаты работы были представлены на XLI международной научной студенческой конференции, на XXVI Конференции молодых ученых механико-математического факультета МГУ им. М.В. Ломоносова, на IX азиатской логической конференции, на XLIV международной научной студенческой конференции. А также на семинарах "Автоматы и сложность вычислений" и "Конструктивные модели" Новосибирского государственного университета.
Все основные результаты диссертации опубликованы в работах [25], [26], [27], [28], [29], [30], [31]
Диссертация состоит из введения, трёх глав, разбитых на параграфы, и списка литературы. Нумерация утверждений сквозная. Список литературы содержит 30 наименований. Объём диссертации составляет 63 страницы.
Перейдём к изложению содержания диссертации. Глава 1 посвящена изучению алгебраических свойств индексных множеств. Наравне с проблемой изоморфизма в некотором классе также является естественным и интересным вопрос о проблеме изоморфизма, с наложением на изоморфизм некоторых ограничений, таких как вычислимость, автоматность.
Проблема вычислимого изоморфизма для различных классов моделей (важная подпроблема проблемы изоморфизма) интересовала многих исследователей. В частности, в совместной работе С.С. Гончарова и Дж. Найт [2] была найдена оценка проблемы вычислимого изоморфизма для ряда классов: линейных порядков, булевых алгебр, моделей эквивалентностей и др. В работе Н.Т. Когабаева [7] была найдена оценка проблемы вычислимого изоморфизма для вычислимых /—алгебр. Мы оценим проблему вычислимого изоморфизма для класса всех автоматных структур. Также мы будем оценивать и проблему автоматного изоморфизма, крайне естественную именно для автоматных структур.
Эти и сопутствующие им результаты изложены в теоремах 4, 3, 6, 7 и следствиях 4, 5, б. Все основные результаты первой главы вместе с известным результатом Б.Хусаинова, Рубина, Ниса и Штефана о } полноте проблемы изоморфизма, доказанным в работе [19] отображены в следующей таблице:
В первой части второй главы изучаются индексные множества таких свойств,
как однородность и автоматная однородность. Напомним, что модель 21 однородна, если для любых кортежей а, Ъ из выполнения условия (21, а) = (21,6) следует существование автоморфизма, переводящего кортеж а в кортеж Ъ. Однородность модели — это важное теоретико-модельное свойство. Поэтому важно дать характеризацию классу всех автоматных однородных моделей. Оценка, полученная в следующей теореме:
Теорема 9. Множество Нот = {п | 21п однородна } — И-полно.,
оставляет надежду получить не очень сложную характеризацию класса всех автоматных моделей. Кроме того результат сам по себе является интересным, поскольку отвечает на вопрос: "Насколько сложно определить по виду автоматной структуры является ли она однородной?"
И опять как и в случае проблемы автоматного изморфизма понятие автоматной однородности, естественное усиление однородности для автоматных моделей.
Определение 4 Назовём автоматную структуру 21 автоматно однородной, если для любых кортежей a, b из выполнения условия (21, а) = (21, Ь) следует существование автоматного автоморфизма, переводящего кортеоїс а в кортеоїс b
Заметим, что наличие автоматной однородности очень полезно для изучения групп автоматных автоморфизмов. И первый шаг к характеризации класса автоматно однородных моделей это опять же оценка индексного множества, которая получена в следующей теореме:
Теорема 10. Множество АНот = {п | 21п автоматно однородна } — П^-полно.
Во второй части второй главы изучаются индексные множества таких свойств, как универсальность и универсальность в классе автоматных моделей. Напомним, что модель 21 универсальна, если для любой модели Ш, такой что 21 = 53
и мощность модели 03 не превосходит мощности модели 21, существует элементарное вложение 03 в 21.
По аналогии с этим определением мы определим универсальность в классе автоматных моделей следующим образом:
Определение 5 Автоматная модель 21 универсальна в классе автоматных моделей, если для любой автоматной модели 03, такой что 21 = 03, существует элементарное вложение 03 в 21.
Основные результаты второй части второй главы, изложенные в теореме 11, и следствиях 7, 8 показывают, что проблема универсальности крайне сложна для распознавания.
Теорема 11. Мноокество Un = {п | 21п универсальна в классе автоматных моделей} — } -полно.
Следствие 7. Множество универсальных автоматных структур не менее чем }-полное.
Следствие 8. Множество универсальных вычислимых структур не менее чем }—полное.
Первая часть третьей главы посвящена изучению автоматного спектра теории,
Определение 6 Назовём автоматным спектром Spa(T) полной теории Т число попарно неизоморфных моделей теории Т, имеющих автоматное представление. Если у теории Т таких моделей нет, то спектр теории Spa(T) = 0. Если у теорииТ существует бесконечно таких моделей, то спектр теории Spa(T)=u.
Хорошо звестно, что для любого п > 3 существует теория Тп, имеющая п моделей с точностью до изоморфизма. В первой части третьей главы доказывается теорема, являющаяся аналогом этого результата для автоматного случая.
Теорема 12. Для любого п > 3 существует теория Тп, такая что выполнено равенство Spa(Tn) = п.
Легко строятся примеры теорий с автоматными спектрами равными 0,1,и, таким образом пока остаётся открытым вопрос, может ли автоматный спектр теории принимать значение в точности равное 2.
Вторая часть третьей главы посвящена рассмотрению групп автоматных автоморфизмов некоторых автоматных структур. А именно, рассматриваются группа автоматных перестановок счётного множества и группа автоматных автоморфизмов модели Q = ({0,1}*, гмех) ~ автоматного представления множества рациональных чисел с порядком. В работе [5] А.С. Морозов показал, что группа вычислимых перестановок счётного множества имеет неразрешимую теорию, более того элементарная теория этой группы вычислимо изоморфна множеству всех предложений истинных в арифметике. В теореме 13 и следствии 9 доказывается автоматный аналог этого результата.
Теорема 13. В Aut a ({0,1}*) определима с параметрами стандартная модель арифметики. При этом класс таких параметров такоісе является формульным.
Следствие 9. Элементарная теория группы Aut a({0,1}*) неразрешима. Более того, она вычислимо изоморфна множеству всех предложений, истинных в стандартной модели арифметики.
Заметим, что доказательство этого утверждения остается верным также и для любой группы Auta(L), где L — произвольный бесконечный регулярный язык. Также с точки зрения теории автоматных моделей интересно следующее следствие:
Следствие 10. Пусть L произвольный бесконечный регулярный язык. Тогда группа Auta(L) не имеет автоматного представления.
В совместной работе А.С. Морозова и Дж. К. Трасса [21] показывается, что группа вычислимых автоморфизмов рациональных чисел с порядком имеет неразрешимую теорию, более того элементарная теория этой группы вычислимо изоморфна множеству всех предложений истинных в арифметике. И опять же интересен вопрос есть ли автоматный аналог этого результата. В теореме 14 и следствии 11, доказывается более слабый результат, а именно, показывается, что теория структуры Aut а (Q) наследственно неразрешима. Теорема 14. В группе автоматных автоморфизмов Auta(Q) структуры Q определяется с параметрами арифметика.
Следствие 11. Теория структуры Auta(Q) наследственно неразрешима.
К сожалению, пока неизвестно верно ли, что элементарная теория группы Auta(Q) вычислимо изоморфна множеству всех предложений истинных в арифметике. Также интересно и следующее следствие.
Следствие 12. Структура hut а (О) не имеет автоматного представления.
Кроме того все эти результаты интересны со следующей точки зрения: в предложении 4 показывается что группа автоматных автоморфизмов любой автоматной модели вычислима. Возникает сразу же естественный вопрос, а верно ли, что группа автоматных автоморфизмов любой автоматной модели имеет разрешимую теорию или даже автоматна. Эти результаты дают отрицательный ответ на эти вопросы.
Автор выражает глубокую признательность А.С. Морозову за постановку задач, постоянное внимание к работе и всестороннюю поддержку.
Вычислимые алгебраические свойства
Действительно, пусть Т сходится в 0, значит, R, пройдя конечное множество конфигураций К, остановится в конфигурации из FIN, следовательно, в ориентированном графе Л(Т) множеством вершин, достижимых из X, будет К U Vp. Первые \К\ элементов В ставятся последовательно в соответствие элементам из К, далее элементу LA из Л(Т) ставится в соответствие элемент L.1 из 2-п 2-\К\+2-п
В. Полученное отображение является автоматным изоморфным вложением В в Л(Т).
Обратно, пусть Т расходится в 0. Предположим, что существует / — автоматное изоморфное вложение В в Л{Т). Оно отображает 11 в X, 1111 — в следующую за X конфигурацию, и т. д. По лемме 2 существует константа с такая, что Ух \\х\ — \f(x)\\ с. Но Т за один шаг может увеличить длину конфигурации максимум на 1, а в В длина каждой последующей вершины больше длины предыдущей на 2, следовательно, существует w такое, что \\w\ — /(ги) с; противоречие.
Теорема 5 Для произвольной МТ Т существует автоматная модель А(Т), строящаяся равномерно эффективно по номеру Т, с выделенными элементами X и Y, находящимися равномерно эффективно по номеру Т, такая, что существует автоматный автоморфизм, переводящий X в Y тогда и только тогда, когда Т сходится в точке 0. Доказательство. Пусть R — обратимая МТ, эквивалентная Т, полученная по теореме 2. В графе C(R) = (Уя, Ер) определим новые регулярные множества: VH = {x,l !,new,a;FIN}, ЕИ = {(х Л ІЛ) \ п Є ш,х Є FIN}, 2-п 2-(п-1) 2-п где FIN — множество, определенное в теореме 4. F = (Vp, Ер) — граф из теоремы 4, А(Т) (VRUVHUVF, ERUEnUEp). В качестве X возьмем конфигурацию из VR, соответствующую начальной конфигурации МТ Т с входом 0, а в качестве Y — элемент 11 из Vp.
Если Т сходится в 0, то существует конечная конфигурация, в которой Т остановится. Пусть ей соответствует конфигурация Р из VR и всего есть к конфигураций, принимаемых МТ Т на входе 0. Построим автоматный автоморфизм а структуры Л(Т) такой, что а(Х) = Y. Первым к элементам, достижимым из X, ставятся в соответствие первые к элементов, достижимых из Y. Далее, a (PL Л) = 1.Л , п Є ш. На остальных элементах а действует тожде ственно. Нетрудно проверить, что а — автоматный автоморфизм.
Пусть Т расходится в 0, предположим, что существует автоматный автоморфизм а, переводящий X в Y. По лемме 2 аналогично рассуждениям из доказательства теоремы 4 получаем противоречие. Следствие 3 Множество Autela = {(m,n,l) 3/—автоматный автоморфизм 2lm, такой 4mof(v) = vj"} — ТРх-полно.
Доказательство. Из теоремы 5 следует, что проблема остановки МТ сводится к этой проблеме, а из замечания 2 — что эта проблема лежит в классе Е. Следствие 4 Множество Isoa = {(т,п) 2lm =a 21п}Е-полко. Доказательство. Покажем, что эта проблема лежит в Е. Рассмотрим множество Isoi = {(n,m,z) I предикат Щ является изоморфизмом структур %п и 2lm}. Оно вычислимо по замечанию 2. Множество Isoa, очевидно, является проекцией множества Iso і и поэтому вычислимо перечислимо.
К проблеме Iso a сводится проблема из следствия 3. Действительно, (n,l,m) Є Aut & (f(n,l),f(n,m)) Є Isoa, где / — вычислимая функция, выдающая по номеру п автоматной структуры и номеру / элемента из этой структуры номер структуры, совпадающей с вышеуказанной, с внесенным в сигнатуру выделенным элементом /. Отсюда следует Ej-полнота проблемы Isoa.
Теперь получим оценку проблемы вычислимого изоморфизма и вложения для автоматных структур. Заметим, что для вычислимых структур оценки соответствующих проблем такие же. Пусть (v)new эффективная нумерация всех слов из языка 2lm.
Теорема 6 Mnooicecmeo Autc = {(m,n,l) 3/ — вычислимый автоморфизм 2lm, такой что /(г ) = v} — Е -полно.
Доказательство. Понятно, что это множество принадлежит Е. Докажем, что это точная оценка. Пусть множество S Є Е сведём его к Autc. Существует вычислимый предикат Ps, такой что п Є S 43 Bx3uyPs(n,x,y) (см. [8, 14.8]). Пусть п фиксировано. Определим новый вычислимый предикат P1s(x,y) = \/Ps(n,i,y) i x
Заметим, что если существует бесконечно много у, что Ps(n,x,y) истинен, то для любого Х\ х существует бесконечно у, что Р$(хх,у) истинен. А если не существует элемент х, такой что существует бесконечно у, что Ps(n,x,y) истинен, то и не существует элемент х, такой что существует бесконечно у, что Р$(х,у) истинен.
Пусть R обратимая МТ, вычисляющая предикат Р$(х, у), причём пусть если предикат Р (х,у) истинен, то на входе (гг, у)R зацикливается, иначе останавливается. Пусть C(R) — (V, Е) граф конфигураций R. Пусть in.it множество начальных конфигураций R. Пусть Н Є init соответствует входу (х, у). Тогда на второй проекции Н записана входная информация, т.е. слово .Ab L.A, на х у первой текущее состояние головки , т.е. начальное, третья проекция Н это Л. Определим бинарное отношение Projection (Я, гг): Projection (Я, х) Яе initkx Є Vk3yPr2{H) = хЬІ Л. у Это отношение регулярно. Пусть bo новый элемент. Определим отношение Ei (х, у) Є Ei i=f (х = b0ky Є 1 ) V (х Є Vky Є init &Projection (г/, х)) Теперь в модели (V U 1 U {bo}, E U i?i) к каждому элементу множества 1 присоединим по бесконечному числу цепей каждой конечной длины. Получилась модель Gr.
Общие алгебраические свойства
Теперь, используя конструкцию, приведенную в доказательстве Ej-полноты проблемы изоморфизма автоматных структур в [19], покажем Sj-полноту про блемы вложения автоматных структур. Заметим, что для вычислимых структур оценка проблемы вложения имеет такую же сложность. Это в очередной раз показывает нетривиалыюсть класса автоматных моделей.
Доказательство. Очевидно, что эта проблема имеет сложность не более, чем Е}. Получим нижнюю оценку. Рассмотрим граф N с множеством вершин = {0,1} 1U{A} и множеством ребер EN = {(х,у) х - р yk(-Bz)(x - р z - р у)}, где х - р у, если х является собственной приставкой у. У каждой вершины v графа N есть ровно ш последователей: г»1, г;01, г;001 и т. д.
Назовем Т С Vfj деревом, если А Т и для любого х Є Т предшественник х также принадлежит Т. Назовем дерево Т вычислимым деревом, если существует МТ М такая, что х 6 Т - на слове х она сходится и дает положительный ответ, х ф. Т 4-ї на слове х она сходится и дает отрицательный ответ. Сведем к проблеме вложения проблему существования бесконечной ветви в вычислимом дереве Т.
Пусть Т — вычислимое дерево, Р — обратимая МТ, его вычисляющая. Изменим ее так, чтобы она вместо положительного ответа зацикливалась. Сщт) — (Ущт),Ещт)) — граф конфигураций этой МТ. Определим автоматное множество Ет = {(v,w) v Є VN, W — начальная конфигурация R(T), соответствующая входу г;}.
Автоматный граф (Удг U Ущт),Е U Ет U Ещт)) представляет собой граф N с прикрепленными к каждой вершине цепочками конечной или бесконечной длины в объединении с некоторым числом цепочек конечной или бесконечной длины. При этом к вершине присоединена бесконечная цепочка тогда и только тогда, когда эта вершина принадлежит дереву Т. Соответственно к вершине присоединена конечная цепочка тогда и только тогда, когда эта вершина не принадлежит дереву Т. Пусть cycle ={(х,х)\хе VR{T)}. Определим автоматную структуру А(Т) = {VN U VR{T), ENUETU ER(T) U Cycle ) Возьмем (UA,SA) — автоматную копию натуральных чисел с функцией следования, init (х) — формула, выделяющая множество вершин без входящих ребер. Введем множество cycle = {(х, х) х Є и А & -anit (х)}.
Пусть структура Ры = (V, Е) — ш непересекающихся копий структуры (иA, SAU cycle); Pw — автоматный граф по предложению 1. Добавим к ребрам графа Рш множество {(Х, у) init (х) & init (у) & X а У & Vz((x а z) - (у а z))}, где а — порядок из теоремы 3. Получился автоматный граф В. Вычислимое дерево Г имеет бесконечную ветвь тогда и только тогда, когда В изоморфно вкладывается в Л(Т). Из вышеизложенного следует }-полнота проблемы вложения автоматных структур.
Ввиду нижеследующей теоремы, изложенной в [16], все вышеуказанные оценки сложности для класса автоматных структур верны и для класса автоматных графов.
Теорема 8 Для произвольной структуры Л существует граф С (Л), эффективно построенный по Л, со следующими свойствами: (1) А автоматна тогда и только тогда, когда С (Л) автоматен; (2) существует изоморфизм а между группой Aut(A) автоморфизмов Л и группой Aut(C(A)) автоморфизмов С(А); более того, / Є Aut(A) автоматен тогда и только тогда, когда a(f) автоматен; (3) структура (В) автоматно изоморфна структуре Л тогда и только тогда, когда (С (В)) автоматно изоморфна С (Л).
В данной главе оцениваются индексные множества классов однородных, автоматно однородных, универсальных автоматных структур. Будет показано, что по виду автоматной структуры распознать явлется ли она однородной или автоматно однородной не сильно сложно, а именно, что соответствующие индексные множества лежат достаточно низко в арифметической иерархии. Свойство универсальности, наоборот, оказывается крайне сложным для распознавания.
Универсальност
Перейдём к оценке свойства универсальности и покажем, что оно очень сложно для распознавания. В доказательстве следующей теоремы используется конструкция из доказательства }-полноты проблемы изоморфизма для автоматных структур, изложенная в [23].
Теорема 11 Мнооїсество Un = {п 21п универсальна в классе автоматных моделей] — Т\-полно. Доказательство. Понятно, что Un Є }. Докажем, что это точная оценка, сведением к Un множества С = {п \ Тп вычислимое дерево, имеющее бесконечную ветвь }. В статье [2] по номеру п вычислимого дерева Тп эффективно строится дерево Sn, такое что если в Тп есть бесконечный путь, то в Sn есть поддерево, изоморфное ш ш. А если в Тп нет бесконечного пути, то и в Sn нет бесконечного пути. Теперь по Sn, используя конструкцию из [23], эффективно построим автоматную модель Un Определим множества iV={0,l} lUA (х, у) Є EN ±= (х - р y)k-i(3z(x - р z - р у)), где х р у =? х является приставкой у. В графе (N, EN) К каждой вершине присоединим по бесконечному числу цепей каждой конечной длины. Затем к полученному графу добавим по бесконечному числу отдельных цепей каждой конечной длины и по бесконечному числу отдельных цепей бесконечной длины, устроенных по типу шипо типу целых чисел. Это делается по аналогии с теоремами 9,10, так чтобы полученный граф (D, ED) был автоматным. Можно считать, что Sn вычислимое поддерево (N,E )- Пусть Рп МТ работает на элементах из N, причём Рп на входе х зацикливается, если х Є Sn, иначе останавливается. Rn обратимая МТ, эквивалентная Рп, из теоремы 2. Пусть C(Rn) граф конфигураций Rn. Пусть Cu(Rn) — и копий C(Rn). Теперь возьмём граф (D, ED) объединим его с графом СШ(ЛП) и свяжем каждую вершину р Є N с соответствующими ей ш начальными конфигурациями. Получилась автоматная модель 05 = ( B,S). Определим новую модель 03ш 93ыМ?8х{0 иГ} Определим отношение - на множестве {0 U 1 } х " У = (х — 2/0) v (яі = У) Это отношение — предикат следования на множестве целых чисел. Теперь определим отношение (х,у) еЕ и х,уе \Ъи\к{{Рг2{х) = Рг2(у)к{Ргх(х),Рп(у)) Е )У V(Pn (x) = Pn (y) = A)&Pn (x) - Pn (y)) Модель 23w = (103( ,, -Б«в„) состоит из и копий моделей 93, причём все корни копий упрядочены по типу целых чисел.
Возьмём ш копий Q3W и добавим к ним модель 93. Получим модель Un. Будем рассматривать модель Un в расширенной сигнатуре v _ (о(2) p(i) root р(1) р(1) ч ь — \а tree init end- где отношение S это предикат следования, предикат Pree выделяет элементы дерева, константа root выделяет корень этого дерева, PJJ.: t выделяет все вершины, не имеющие предшественников, -find выделяет все вершины не имеющие последователей. Все эти отношения формульно записываются через предикат S 2\ кроме того Un в сигнатуре 5 2 автоматна, значит Un в сигнатуре автоматна. Утверждается, что п Є С =» Un Є Un.
Пусть п Є С, тогда в Sn вкладывается полное дерево, а, следовательно, и в Un вкладывается полное дерево, у которого каждая вершина есть начало бесконечного числа цепей каждой конечной длины и бесконечной длины. Рассмотрим теорию Т сигнатуры Е со следующей системой аксиом: 1. х = root =Ф Ptree (х) & -"(3yS(y,x)) 2. Предложение, утверждающее, что для любого элемента не являющегося константой root и не лежащего в PIJ-J4- существует ровно один предшественник. 3. {фп п Є ш}, где фп утверждает, что у элемента, лежащего в Pree есть п последователей также лежащих в Pree 4. {(р п Є ui,m Є w}, где p% утверждает, что из любого элемента, принадлежащего Ptree выходит m цепей длины п, которые состоят из элементов, не лежащих в Ptree 5. { I n Є u),m Є со}, где VC утверждает, что существует т отдельных цепей длины п, которые состоят из элементов, не лежащих в Ptree 6. ip утверждает, что каждый элемент, не лежащий в Ptree» и не лежащий в Реп х имеет ровно одного последователя,причём не лежащего в Ptree а лежащий в Pend не имеет ни одного последователя. 7. гр утверждает, что каждый элемент, не лежащий в Ptree и пе лежащий в Pinit имеет ровно одного предшественника, а лежащий в Pinit не имеет предшественников.
Любая модель, теории Т состоит из дерева с корнем, бесконечного числа цепей каждой конечной длины, какого-то числа отдельных цепей (возможно и нулевого и бесконечного), устроенных по типу w и по типу целых чисел, и некоторого количества (возможно и нулевого и бесконечного) деревьев следующего вида: к каждому элементу цепи, устроенной по типу целых чисел, присоединяется по w— ветвящемуся дереву.
Причём из каждой вершины, каждого дерева этой модели выходит по бесконечному числу цепей каждой конечной длины и некоторому (возможно и нулевому и бесконечному) числу цепей бесконечной длины. Понятно, что все такие модели вкладываются в Un. Кроме того ясно, что Un модель теории Т.
Пусть 21 модель теории Un. Считаем ввиду вышесказанного, что 21 С Un. Покажем, что 21 Un. Построим элементарное расширение 2li модели 21.
Добавим в сигнатуру счётное число новых попарно различных константных символов. Нетрудно записать множество Y предложений, утверждающих что 1. С каждым элементом модели 21, являющимся элементом дерева связано ш деревьев, составленных из константных символов. Причём каждое дерево представляет из себя копию полного ш—ветвящегося дерева с каждым элементом которого связано и цепей каждой конечной длины и бесконечной длины. 2. Добавленные константы образуют ш компонент связности следующего вида: в модели, представляющей из себя целые числа с предикатом следования, к каждому элементу присоединяется по и копий полного ш-ветвящегося дерева, причём с каждым элементом полученной модели, связано счётное число цепей каждой конечной длины и счётное число цепей бесконечной длины. 3. Некоторые константы образуют счётное число отдельных цепей каждой конечной длины, устроенных по типу ш, и по типу целых чисел. 4. С каждым элементом модели 21, являющимся вершиной дерева связано ш бесконечных цепей и и) цепей каждой конечной длины, составленных из константных символов.
Множество Y U (21), где (21) полная диаграмма модели 21, локально выполнимо. Действительно, модель 21 выполняет любое конечное подмножество Y. Значит существует счётная модель 2li элементарно расширяющая 21 и выполняющая Y. Аналогично построим счётное элементарное расширение И модели Un. Модель И изоморфна модели 01\. Более того изоморфизм (р можно построить таким образом, чтобы на элементах из 21 он действовал тождественно.
Построим частичный изоморфизм для компонент связности содержащих root. Элемент rootЯі перейдёт в элемент rootu. Заметим что если один элемент цепи, лежащей в Un, лежит в 21, то и вся цепь лежит в 21, в противном случае в модели 21 появился бы элемент, не имеющий последователя и не лежащий в .Pen(i, либо не имеющий предшественника и не лежащий в Pinit Это противоречит совпадению теорий моделей 21 и Un.
Группы автоматных автоморфизмов некоторых автоматных структур
Автоморфизм /ш раскладывается в счётное произведения положительных независимых бампов, носители которых расположены по типу ш и бамп с самым маленьким носителем есть /0. Заметим, что бамп /0 передвигает все элементы между словами А и 1, таким образом пустое слово А есть начало бампа /о, а 1, соответственно, конец. Кроме того п—ый бамп из этого произведения есть результат сопряжения бампа /0 перестановкой (fs)n Лемма 7 Свойство "х не содерокит отрицательных бампов" определимо с параметрами в Aut а (Q) формулой Pos (ж) ±4 Vt Comp {fix)
Доказательство. Пусть х не содержит отрицательных бампов, тогда и f$x не содержит отрицательных бампов, следовательно выполнена формула Comp (f x). Обратно, пусть в х есть отрицательные бампы. Возьмём такие элементы h и /, что I hx и їх I, поскольку в х есть отрицательные бампы такие элементы всегда можно взять. Пусть а — начало бампа fo, Ь — такой элемент, что b bf0 (такой элемент b существует поскольку /0 положительный бамп) и с — некоторый элемент, больший h и hx. Ввиду автоматной однородности системы Q существует автоматный автоморфизм t переводящий а b bfo в I hx с. Началом бампа /Q является элемент /, значит все элементы меньшие / бамп /о оставляет на месте, кроме того бамп Д переводит элемент hx в элемент с. Имеем, IXXJQ IX Jn IX IX hxfo = с h. Значит у автоморфизма Ж/Q есть как отрицательные так и положительные бампы. Следовательно, формула ViComp(/oa;) не выполнена.
Теорема 14 В группе автоматных автоморфизмов Auta(Q) структуры Q определяется с параметрами арифметика.
Доказательство. Автоморфизм fu раскладывается в счётное произведения положительных независимых бампов, упорядоченных по типу из. Каждый такой бамп, таким образом, кодирует элемент из из. Каждый из этих бампов сопряжён с /0. Т.е. получается, что данный автоморфизм элемент из, если он является частью fu и сопряжён с /о. Поэтому элементы, кодирующие натуральные числа, выделяются следующей формулой с параметрами: 3t(x = /о) к (3 у, z Apart (х, у) к Apart (у, z) к Apart (х, z) к fu — yxz).
Порядок на бампах также интерпретируется естественным образом, чем меньше носитель бампа (в смысле поэлементного сравнения), тем меньше и кодируемый им элемент. Если бамп можно получить из другого сопряжением положительным автоморфизмом, то первый бамп больше, т.е., порядок х у на бампах, интерпретирующих натуральные числа, задается формулой Bt (Pos ( ) к Xі = у) Функция следования определяется естественным образом через порядок. S(x) — у != х у к Уг (z х —» z у) Сложение и умножение определяются через естественные индуктивные схемы х + 0 = х и х + (у + 1) = (х + у) + 1 -0 = 0 х (у + 1) = (х у) + X, на элементах, кодирующих натуральные числа, следующим образом: х + у = z 3 [/0 = z & = г & V/i «$ y(S(hl) = (S(h)Y)]. x.y = z 3t[ti = f0kyt = zkVh y(ht + x = (S(h))t)]. D Напомним, что теория T называется наследственно неразрешимой, если любая подтеория теории Т той же сигнатуры неразрешима. Следствие 11 Теория структуры Aut а (О) наследственно неразрешима.
Доказательство. По теореме 14 стандартная модель арифметики относительно элементарно определяется в модели Auta(Q). Кроме того по предложению из [4, гл. 5, 1] стандартная модель арифметики имеет наследственно неразрешимую теорию. Следовательно, по теореме 2 из [4, гл. 5,1] группа Auta( Q ) имеет наследственно неразрешимую теорию. Следствие 12 Структура Auta(Q) не имеет автоматного представления.
Доказательство. Хорошо известно, что любая автоматная структура имеет разрешимую теорию. Но из 11 следует, что модель Auta(Q) имеет неразрешимую теорию. Значит Auta(Q) неавтоматна.
