Решение проблемы отделимости алгоритмически разрешимых случаев А-полноты для базисов поста дефинитных автоматов

• Автор: Жук, Дмитрий Николаевич
• Шифр специальности: 01.01.09
• Научная степень: Кандидатская
• Год защиты: 2009
• Место защиты: Москва
• Количество страниц: 91 с. : ил.

Оглавление
Введение
Основные понятия и результаты
1 Разрешимые случаи проблемы Л-полноты
1.1 Основные утверждения
1.2 Доказательство утверждений
2 Неразрешимость проблемы Л-полноты для классов 56, Р6)

2.1 Основные утверждения
2.2 Доказательство утверждений .д
3 Неразрешимость проблемы Л-полноты для классов
3.1 Основные утверждения
3.2 Доказательство утверждений
Литература

Введение
Понятие автомата относится к числу важнейших в математике. Оно возникло на стыке разных её разделов, а также в технике, биологии и других областях. Содержательно автомат представляет собой устройство с входными и выходными каналами. На его входы последовательно поступает информация, которая перерабатывается им с учётом строения этой последовательности и выдается через выходные каналы. Эти устройства могут допускать соединение их каналов между собой. Отображение входных последовательностей в выходные называют автоматной функцией, а возможность получения новых таких отображений за счёт соединения автоматов приводит к алгебре автоматных функций.
Первый толчок к возникновению теории автоматов дала работа Э. Поста 1921 года [1]. В ней были получены фундаментальные результаты о строении решетки замкнутых классов булевых функций. В дальнейшем эти результаты были переработаны и упрощены в [8]. Сами автоматы и их алгебры начали исследоваться в тридцатые годы двадцатого века, но особенно активно в период с 50-х годов.
Основополагающую роль здесь сыграли работы Тьюринга, Мура, Кли-ни, а также многочисленные статьи, опубликованные в знаменитом сборнике «Автоматы» [2] под редакцией Шеннона и Маккарти. В одной из работ данного сборника впервые встречается понятие дефинитного события и дефинитного автомата [3]. Дефинитные автоматы — это все автоматные функции, которые можно получить из задержек и булевых функций с помощью операции суперпозиции. Впервые дефинитные автоматы были систематически исследованы в [4]. Некоторые свойства дефинитных авто-

матов изучались в [5, 6, 7].
Последующие работы по изучению алгебр автоматов велись под большим влиянием известных статей А. В. Кузнецова [9, 10] и С. В. Яблонского [11] по теории функций fc-значной логики. Возникшие для таких функций постановки задач о выразимости, полноте, базисах, решётке замкнутых классов, а также развитый аппарат сохранения предикатов оказались весьма действенными и для алгебр автоматных функций. При этом под выразимостью понимается возможность получения функций одного множества через функции другого с помощью заданных операций, а под полнотой — выразимость всех функций через заданные.
Основу результатов для функций &-значной логики составляет подход A.B. Кузнецова, опирающийся на понятие предполного класса. Для конечно-порождённых систем таких функций семейство предполных классов образует критериальную систему: произвольное множество является полным тогда и только тогда, когда оно не является подмножеством ни одного предполного класса. Множество этих предполных классов оказалось конечным и из их характеризации вытекает алгоритмическая разрешимость задачи о полноте. На этом пути С.В. Яблонским путем явного описания всех предполных классов была решена задача о полноте для функций трехзначной логики, а вместе с А. В. Кузнецовым найдены отдельные семейства предполных классов для логики произвольной конечной значно-сти. Затем усилиями многих исследователей [13]-[16] последовательно были открыты другие семейства предполных классов. Заключительные построения провел И. Розенберг в 1970 году [17]. При этом все предполные классы были описаны как классы сохранения отношений или предикатов.
Одновременно с изучением функций &-значной логики были сделаны попытки применения аппарата предполных классов в задаче о полноте для автоматов. Сначала В. Б. Кудрявцев [18] эффективно решил задачу о полноте и её модификациях для функций с задержками. После этого им был получен фундаментальный результат негативного характера: континуальность множества предполных классов автоматных функций [19]. В дальнейшем, М. PI. Кратко [20] установил алгоритмическую неразрешимость за-

константой 1. Поэтому далее будем полагать, что
^1 (0Ц> ®2> • • ■ 1 Оур— 1] Ь, Ь2у . . . , Ьр— = 1.
Рассмотрим автомат В,(х1,х2) = В,(хъ х2 + Z(]p-ll(x‘2) + г0р{х2)) + Л(жьж2) + г№{х-[) Е [М]

1(а1уа2,... ,ар,Ь1,Ь2, ...,Ьр) = Кр(а,1а2 ... ар, Ъф2 ... Ър).
Получим, что
1(а1, а2, ■ ■ ■ ,ар,Ь 1,Ь2,..., Ър) — ар + 12(аг. а2,..., ар_1, Ь, Ь2,..., Ьр^),
причём автомат Я (р — 1)-равен константе 0.
Пусть До = В,(х 1,Хх) + х + Zov(xl) Е [М. Легко проверить, что для 5 < р— 1 выполняется До (а) = а(з), а выход автомата До в момент времени р не зависит от входа в момент времени р.
Определим автомат ]¥о с одним входом высоты р — 1. Иф” (а) = 0, если 1 < з < р — 2; И/о>“1(а) = а(р — 1). По предположению индукции существует автомат У/ Е [М], (р — 1)-равиый автомату Иф. Тогда автомат У2(х) = Во(1У1(х)) Е [.М] обладает следующим свойством: если в < р — 2, то И^2(а) = 0; 1 (о-) = а(р — 1); (ага2... ар) = г(ар-1), где г —
некоторая функция из Р2. То есть выход автомата ¥2 в момент времени р зависит только от входа в момент времени р — 1. Если г(0) = 1, то вместо У/2 рассмотрим автомат ¥2(х) + Z0p-ll(x) + Z0p(x). Поэтому будем считать, что г(0) = 0.
В случае, если функция г константа 0, положим И'з(ж) — ]¥2(х). Рассмотрим случай, когда функция г не константа. В этом случае г(ар-1) = ар-1. Пусть
С = {(Т(0Р),Т(0Р“211))|Т е [М],п(Т) = 1}.
Из леммы 1.10 следует, что М сохраняет С. Покажем, что Кр С С. Рассмотрим произвольное (а, /3) £ Кр. Если а = /3, то очевидно
(^а(0р),^(0р-211)) = (а,а)бС'.