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

• Автор: Винокуров, Никита Сергеевич
• Шифр специальности: 01.01.06
• Научная степень: Кандидатская
• Год защиты: 2006
• Место защиты: Новосибирск
• Количество страниц: 63 с. : ил.

1 Введение
1.1 Основные определения и предварительные сведения
2 Индексные множества алгебраических свойств автоматных структур
2.1 Автоматные алгебраические свойства
2.2 Вычислимые алгебраические свойства
2.3 Общие алгебраические свойства
3 Индексные множества теоретико-модельных
свойств автоматных структур
3.1 Однородность
3.2 Универсальность
4 Теоретико-модельные свойства автоматных
структур
4.1 Автоматный спектр теорий
4.2 Группы автоматных автоморфизмов некоторых автоматных структур
Список литературы

1 Введение
На сегодняшний момент получила широкое распространение теория конструктивных моделей (см. книги С.С. Гончарова, Ю.Л. Ершова [1], Ю.Л. Ершова [4]), появившаяся на стыке теории моделей (см. книгу Г. Кейслера, Ч.Ч. Чэна [6], Дж.Е. Сакса [9]) и теории вычислимости (см. монографию X. Роджерса [8]), изучающая свойства объектов, вычисляемых произвольными алгоритмами (машинами Тьюринга). В связи с резким развитием вычислительной техники появилась потребность в изучении не каких-то абстрактных вычислимых объектов, а вполне конкретных, вычисляемых за определённое время, т.е. надо было каким то образом сделать ограничение на вычисляющий алгоритм (вы-числяющеую машину), чтобы вычисляемый объект обладал достачно хорошими свойствами.
Появился ряд различных определений: структуры, вычислимые за полиномиальное время, вычислимые на машинах Тьюринга с ограниченной лентой и т.д. В частности в 1995 году в работе Б. Хусайнова и А. Нероуда [14] появилось понятие автоматной структуры, т.е. структуры, вычислимой с помощью конечного автомата. Напомним это определение.
Пусть Л обозначает пустое слово. Пусть Е — некоторый конечный алфавит. Тогда Е* будет обзначать множество всех слов над этим алфавитом, а Е+ будет обозначать Е* {А}.
Определение 1 Пусть Е — некоторый конечный алфавит. Обозначим через Еф алфавит Еи{<>}, где 0 ^ Е. Тогда копволюцией кортеэ/са (од, ...,ш„) € (X*)" назовём кортеж (од, ...,шп)^ € (Е^)п, полученный добавлением наименьшего числа символов 0 к правым концам ш,, 1 < г < п, так, чтобы все получившиеся слова имели одинаковую длину. Конволюцией отношения Я С (Е*)п назовём отношение П.^ С (Х£,)п, сформированного как множество копволюций всех кортежей в Я.
Определение 2 Будем говорить, что отношение И С (£*)" распознаваемо конечным автоматом, если его конволюция Б? распознаваема конечным автоматом над алфавитом (££,)”.
Определение 3 Будем говорить, что структура
Д= (Л,Я?,.с*)
автоматна над Е, если её носитель А С Е*, и все отношения ІЇ-1 С (£*)"* распознаваемы конечными автоматами. Будем говорить, что структура автоматна, если она автоматна над некоторым алфавитом. Если существует изоморфизм между некоторой структурой В и автоматной структурой А, тогда В называется автоматно представимой (над Е), и структура А называется автоматной копией структуры В, а изоморфизм называется автоматным представлением структуры В.
Эти объекты сразу же привлекли внимание исследователей, т.к. с ними было довольно просто работать, кроме того автоматные модели, как было показано в работе Е.Грёделя и А.Блумензаца[12] , обладали разрешимой теорией, а именно была доказана следующая теорема:
Теорема 1 ([12]) Для любой автоматной структуры А, множество всех БО(3го)-предложений, истинных в структуре А, разрешимо, где Б0{З00) язык первого порядка, обогащенный квантором 3°° (существует бесконечно много).
Из доказательства этой теоремы следует, что соответствующий разрешающий алгоритм строится равномерно по автоматному представлению модели. Из доказательства теоремы также легко получается следующее важное замечание:
Замечание 1 Любые формульные отношения языка ЕО(3°°) на автоматной структуре являются автоматными.
где =4ієх — это лексикографический порядок. Пусть т — наименьший элемент относительно порядка =4цех в Ь \ пусть 5(.г) — автоматная функция взятия следующего элемента относительно этого порядка. Тогда отображение
9ІХ)
X, если X € {й2г г Е uj}
(1-21+1, если X — d2t+ з т, если х = ai 5(х), если isi
будет автоматным. При этом ао € st (д), но а0 £ h(st ( Далее аналогично тому, как это сделано в [5], в модели
(Aut а({0,1}*),ш, •, ар)
определяется формулами первого порядка модель
(Aut а({0,1}*),ш, F, •, ар, g) ,
где F — множество всех конечных подмножеств (и и отношение 6 — естественное отношение принадлежности на и х F. При этом, в качестве интерпретаций конечных множеств берутся такие автоматные перестановки /, у которых стабилизатор st (/) конечен. По лемме 3, они выделяются формулой первого порядка в языке модели (Aut а({0,1}*),а;, •,ар).
Далее, как и в [5], строится формула Norm(x, у) языка первого порядка, выделяющая в модели Auta({0,1}*) пары перестановок (/o,/i), действующих, как
/о = n;ew(a2i,a2t+l)) /1 = n,ea,(a2i+l, Й21+2),
где все а; попарно различны и {а* | г < ш} — {0,1}’. Легко заметить, что в любом бесконечном регулярном языке существуют автоматные перестановки,