Решение проблемы классификации автоматных базисов Поста по разрешимости свойств полноты и А-полноты тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

С5

Московский государственный университет им. М. В. Ломоносова Механико-математический факультет

На правах рукописи УДК 519.95

Бабин Дмитрий Николаевич

Решение проблемы классификации автоматных базисов Поста по разрешимости свойств полноты и А-полноты.

ДИССЕРТАЦИЯ

на соискание ученой степени доктора физико-математических наук 01.01.09 — Математическая Кибернетика.

Научный консультант

академик АТН РФ, профессор Кудрявцев Валерий Борисович.

Москва 1998 г.

Президиум ВАК России

(решениеот* 19 Г^г., Г* *^

1 присудил ученую степень

Оглавление.

Введение..........................3

1. Алгоритмическая разрешимость полноты и А-полноты конечных систем а.-функций, содержащих полную систему истинностных функций..........................36

1.1. Основные понятия и леммы..........................39

1.2. Доказательство лемм 1.1,1.2,1.3..........................48

1.3. Доказательство лемм 1.4,1.5..........................60

1.4. Доказательство теорем 1,2..........................86

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

2.1. Основные леммы..........................91

2.2. Доказательство вспомогательных утверждений. ... 103

2.3. Доказательство теорем 3,4..........................132

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

3.1. Основные леммы..........................137

3.2. Доказательство лемм 3.1 — 3.3..........................147

3.3. Доказательство лемм 3.4.-3.8........................168

3.4. Доказательство лемм 3.9.-3.13........................190

4. Алгоритмическая неразрешимость проблемы полноты и А-полноты конечных систем автоматов с истинностной частью типа О, Р, Р3..........................197

4.1. Основные леммы..........................200

4.2. Доказательство лемм..........................208

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

Введение.

Понятие автомата относится к числу важнейших в математике. Оно возникло на стыке разных ее разделов, а также в технике, биологии и других областях. Содержательно автомат представляет собой устройство с входными и выходными каналами. На его входы последовательно поступает информация, которая перерабатывается им с учетом строения этой последовательности и выдается через выходные каналы. Эти устройства могут допускать соединение их каналов между собой. Отображение входных последовательностей в выходные называют автоматной функцией, а возможность получения новых таких отображений за счет соединения автоматов приводит к алгебре автоматных функций.

Первый толчок к возникновению теории автоматов дала работа Поста Э. 1921 года [1]. В ней были получены фундаментальные результаты о строении решетки замкнутых классов булевых функций, которые были в дальнейшем методически переработаны и упрощены в книге Яблонского C.B., Кудрявцева В.Б., Гаврилова Г.П. "Функции алгебры логики и классы Поста" [2].

Сами автоматы и их алгебры начали исследоваться в тридцатые годы текущего столетия, но особенно активно в период с 50-х годов.

Основополагающую роль здесь сыграли работы Тьюринга, авторов знаменитого сборника "Автоматы" [3] Шеннона, Мура, Клини и других. Последующие работы по изучению алгебр автоматов велись под большим влиянием

известных статей A.B. Кузнецова [4,5] и C.B. Яблонского [6] по теории функций &-значной логики. Эти функции могут рассматриваться как автоматы без памяти, к которым применяются операции суперпозиции. Возникшие для таких функций постановки задач о выразимости, полноте, базисах, решетке замкнутых классов и другие, а также развитый аппарат сохранения предикатов как ключевой для решения этих задач, оказались весьма действенными и для алгебр автоматных функций. При этом под выразимостью понимается возможность получения функций одного множества через функции другого с помощью заданных операций, а под полнотой — выразимость всех функций через заданные.

Основу результатов для функций /с-значной логики составляет подход A.B. Кузнецова, опирающийся на понятие предполного класса. Для конечно-порожденных систем таких функций семейство предполных классов образует критериальную систему; другими словами, произвольное множество является полным точно тогда, когда не является подмножеством ни одного предполного класса. Множество этих предполных классов оказалось конечным и из их характеризации вытекает алгоритмическая разрешимость задачи о полноте. На этом пути C.B. Яблонским путем явного описания всех предполных классов была решена задача о полноте для функций трехзначной логики, а вместе с A.B. Кузнецовым найдены отдельные семейства предполных классов для логики произвольной конечной значности. Затем усилиями многих исследователей [7-11] последовательно были открыты новые такие семейства, а заключительные построения провел Розенберг [12].

Одновременно с изучением функций без памяти ( без учета времени ), были сделаны попытки применения аппарата предполных классов в задаче полноты для автоматов. Сначала для автоматов без обратных связей, называемых функциями с задержками, В.Б. Кудрявцев эффективно решил задачу о полноте и ее естественных модификациях [13]. После этого им было проведено рассмотрение общего случая и на этом пути был получен фундаментальный результат негативного характера, который показал континуальность множества предполных классов автоматных функций [14]. В дальнейшем, Кратко М.И. была показана алгоритмическая неразрешимость задачи о полноте для автоматных функций [15]. Нужны были новые методы исследования автоматных функций. Изменился характер задач в теории автоматов. Начался сбор положительных примеров и попытки различных вариаций этой задачи.

Как отмечается в работе [16] возникли четыре основных подхода к задаче о полноте.

Первый подход связан с расширением понятия равенства автоматов и их множеств. Возникли следующие понятия полноты:

— А-полнота (Буевич 1973 г. [17]). Для некоторого т автоматные функции / и д считаются т - равными, если они равны на словах длины т. Автоматная функция / А-выразима через множество автоматных функций М, если для каждого т найдется г - равная / а-функция д1 выразимая через М. Оказалась, что проблема А-полноты алгоритмически неразрешима.

— Клини - полнота ( Дассов Ю. 1978 г. [18] ). Автоматные функции считаются Клини - равными, если зада-

ваемые ими регулярные множества совпадают. Проблема Клини-полноты также алгоритмически неразрешима.

— еполнота ( Строгалов A.C. [19] 1986 г. ). Предполагается, что автоматные функции е - равны, если они отличаются на множестве меры меньшей е. Проблема е - полноты также алгоритмически неразрешима.

— Проблема полноты с учетом недостижимых состояний ( Хазбун И.В. 1992 г. [20] ) также алгоритмически неразрешима.

— iV-полнота ( автор 1994 г. [21] ) - это выразимость относительно суперпозиции автоматов с не более, чем N-состояниями. Здесь независимо от N удалось обнаружить двухместную универсальную функцию. Проблема N - полноты также алгоритмически неразрешима.

Второй подход связан с вариацией операций, применяемых к автоматам. В.Б. Кудрявцев [13] для функций с задержками относительно операции суперпозиции описал все предполные классы, число которых оказалось счетным и нашел, тем не менее, алгоритм распознавания полноты конечных систем. C.B. Алешин [22] установил в каких случаях, в зависимости от мощностей алфавитов входного, выходного и состояний, существуют базисы для автоматов с операцией суперпозиции. С.С. Марченков [23] для автоматов с бесконечным числом состояний и операцией суперпозиции показал, что полные системы ( естественно, бесконечные ) имеют в совокупности еще и бесконечную арность (аналог 13 проблемы Гильберта для д.-функций). Автор [24] для автоматов с конечным числом состояний и операцией суперпозиции показал, что существуют полные системы ( естественно, бесконечные ) арности два (аналог 13

проблемы Гильберта для о.д.-функций). Более того автору удалось показать, что система, состоящая из одноместных конечных автоматов и всех булевых функций, полна относительно суперпозиции. Общее построение, связанное с вариацией операций над автоматами, осуществлено В.Б. Кудрявцевым в книге "Функциональные системы" [25].

Третий подход связан с изучением полноты в подклассах автоматов. Часовских A.A. в 1985 г. [26] в классе линейных автоматов описал все предполные классы, число которых оказалось счетным и нашел, тем не менее, алгоритм распознавания полноты конечных систем. Тальхайм [27] установил свойства решетки замкнутых классов одноместных стабильных автоматов. Коляда К.В. в 1984 [28] рассматривал классы функций, определенных на регулярных множествах ( функции сопряженные к автоматным ) и обнаружил для одних классов алгоритмическую неразрешимость, а для других алгоритмическую разрешимость проблемы полноты. Автор в 1985 г. [29] показал неполноту относительно суперпозиции системы, состоящая из одноместных конечных автоматов и всех булевых функций в классе перестановочных автоматов.

Четвертый подход связан с ограничением на исследуемые системы автоматов. Еще в 1961 A.A. Летичевским [30] был получен алгоритм решения задачи о полноте для конечных систем автоматов, выдающих номер своего состояния ( автоматов Медведева ) при наличии всех булевых функций. А в 1986 В.А. Буевич [31] показал алгоритмическую разрешимость проблемы А-полноты для систем, содержащих все булевы функции. В 1992 г. автор [32] показал, что существует алгоритм распознавания полноты при

наличии в рассматриваемой системе всех булевых функций.

Очевидно, что для распознавания полноты существенна роль функций без памяти, присутствующих в базисе. Если присутствуют все функции без памяти, то алгоритм распознавания полноты [32] и А-полноты [31] существует. Если присутствует, фактически, лишь тождественная функция х, то не существует алгоритма распознавания как полноты [15], так и А-полноты [17].

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

Решение этой задачи предполагает расслоение систем конечных автоматов на иерархию классов, образующих типы. В один тип входят все системы, которые содержат заданный класс Поста автоматов без памяти. Такие системы автор называет автоматными базисами Поста. До начала решения задачи классификации автоматных базисов Поста в иерархии типов были известны лишь свойства двух точек. Тип систем, содержащих все Р2 был рассмотрен автором, здесь была доказана разрешимость. Тип систем, содержащих, фактически, лишь тождественную функцию х был рассмотрен М.И.Кратко и для него была доказана алгоритмическая неразрешимость.

Автором последовательно в статьях [32-38] эта задача была решена, были установлены свойства всех классов диаграммы Поста. В результате на диаграмме Поста (см.

рисунок 1) получилась явная граница, отделяющая алгоритмически разрешимые случаи от неразрешимых. Эта же граница оказывается верной и для случая А-полноты. Обозначения классов, взятые из [2], таковы:

Классы типа Ь — суть

¿1 = [х + У, 1], ¿2 = [ж + У + 1], Ьз = [х + у], Ь4 = [х + у + х], Ь5 = [х + у + г + 1], Классы типов М, С, И, Р2 -

Мг = [ху, хУу, 0,1], М2 = [ху, хУу, 1], М3 = [ху, хУу, 0], М4 = [ху, хУу];

С\ = [жУу],С2 = [жУу,х+у+1],С3 = [ху, х+у],СА = [хУу, ж(у+^+1)]; £>1 = [жу V V у^], = [жу У хх У ух], Из = [ху У хх У ух]-, = [ж V у^, хуУххУ у г], Р22 = [ж V у2, ху У хг У ух],

Р32 = [1, ху У хх У ух],¥\ = [ж V у, ху У хх У ух],

Р52 = [ж(у V хуУ ххУ ух], Р62 = [ж(у V хуУ ххУ ух],

Р2 = [0, ху У хх У ух], Р82 = [жу, ху У хх У ух],

Классы типов О, Б, Р, Р00, при /х > 2 — суть

01 = И, о2 = [1],Оз - [о], о4 = И, Об = [х, 1], Об = М],

07 = [0,1],08=М, 1],О9 = [ж,0], 5б = [ж V 2/, 0,= Му,0],53 = = [хУу],

Р6 = [ху, 0,1], Р§ = [ху,1],Р3 = [ху,0],Рг = [ху],

9

= И уг], = [я V уг],ЕГ = [1, я V = [хУу],

^ = [х(уЧг)],Р%° = [х(уУг)],Р?> = [0, х(уУ г)}, = [ху], ^ = [ж V уг, /г*(жь ..., = [/г* (хи

Н = [М*(жЬ . . .,^+1)],^ = [хУу,^*^!,...,^!)], Н = Му V ^(жх,..., аг^+х)}], ^ = [км(х1,.. .^х^+г)], = [0,^(^1,...,^+!)],^ = [ж^/гДа?!,...,^!)], где через

/г*(жь ..., ж^-ы) обозначена функция, двойственная к функции

/л+1

• • • ? ~ V Х1 ■ • • жг-1жг+1 . . . Хц+\.

г=1

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

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

автомата: циклах, двойных циклах, тройных циклах. Оказывается, что не сохранение отношений на циклах длины N является критериальным условием для выразимости счетчика по модулю отсутствие соотношений на двойных циклах — условием выразимости селекторных функций, отсутствие отношений на тройных циклах — условием выразимости универсальной булевой функции.

Для задачи А-полноты рассматривается сохранение отношений на путях, двойных путях, тройных путях. При этом не сохранение отношений на путях длины т является критериальным условием для г-выразимости счетчика по модулю т, отсутствие соотношений на двойных путях — условием А-выразимости селекторных функций, отсутствие отношений на тройных путях — условием выразимости универсальной булевой функции.

Возможность проверки циклов ( путей ) длины N при произвольном N обусловлена наличием рекуррентной зависимости предиката отношения на циклах ( путях ) длины меньшей I и на циклах ( путях ) длины /. В разрешимом случае удается за время такое что

\os\og\og\ogt < |д|22п+т,

где |<2| число состояний автоматной функции, п число входов, т число выходов, установить наличие или отсутствие соответствующих отношений на циклах длины N при всех натуральных N.

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

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

Для слабых классов Поста такую проверку провести не удается. Более того, удается свести проблему полноты и А-полноты к проблеме конечности числа продукций Поста, которая алгоритмически неразрешима.

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

Очевидно, что, если проблема полноты ( А -полноты) алгоритмически неразрешима для систем вида ^и^, то она неразрешима для систем вида ^ II у и Г[ {]ь>, где С

двойственный к ^ замкнутый класс. Поэтому для доказательства указанной классификации достаточно проверить ее на классах

£4,-^2, Рз4, 5б,Од.

Пусть Еч = {0,1}, - множество всех сверхслов

а(1)а(2)..., где а(]) £ Е2,з = 1,21...]Е1 - множество всех слов а(1)...а(т) длины т. Пусть

/ : (ЕГГ - (Е?)т

-автоматная функция ( а.-функция), т.е она задается ре-куррентно соотношениями, где q £ = {дх, ...,дг}.

' 9(1) = Чи

< д(г + 1) = ■••> а„(0),

. = ФзШ), ««00), .7 = 1,

Параметр д называется состоянием а.- функции /, - ее начальным состоянием, вектор - буквы а = (а,1,...,ап) и Ь = (Ъ1? ...,6т) называются входной и выходной буквами, а сверхслова а(1)а(2)... и 6(1)6(2)... - входным и выходным сверхсловами соответственно. Класс всех а.-функций обозначим через Ра. В этом классе введем операции суперпозиции и обратной связи. Для суперпозиции будем использовать модификации операций из [40]:

(7//)(жЬ ..., хп) = /(ж2, ж3, ..., Хх), (е/)(жь = f(x2,xl,xs, ...,ж„),

< (0/)(жь ...,ж„_1 = /(жьжьж2, ...,хп_х),

, Жз, ..., Жп+1),

. (/ * ж2, •••, ж/+п-1) = $(д(х 1,..., ж/), ж/+1,..., ж/+п_1).

Операция обратной связи (o.e.), примененная к г-ой входной и j-ой выходной переменным а.-функции f(x 1,..., хп) = (уь ..., уго), задает а.-функцию

д(хъ..., жг-_ь ...,хп) = (у 1,..., yi+b ..., уте),

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