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

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

Первый толчок к возникновению теории автоматов дала работа Э. Поста 1921 года [1]. В ней были получены фундаментальные результаты о строении решетки замкнутых классов булевых функций. В дальнейшем эти результаты были переработаны и упрощены в [8]. Сами автоматы и их алгебры начали исследоваться в тридцатые годы двадцатого века, но особенно активно в период с 50-х годов.

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

Последующие работы по изучению алгебр автоматов велись под большим влиянием известных статей А. В. Кузнецова [9, 10] и С. В. Яблонского [11] по теории функций &—значной логики. Возникшие для таких функций постановки задач о выразимости, полноте, базисах, решётке замкнутых классов, а также развитый аппарат сохранения предикатов оказались весьма действенными и для алгебр автоматных функций. При этом под выразимостью понимается возможность получения функций одного множества через функции другого с помощью заданных операций, а под полнотой — выразимость всех функций через заданные.

Основу результатов для функций /с-значной логики составляет подход A.B. Кузнецова, опирающийся на понятие предполного класса. Для конечно-порождённых систем таких функций семейство предполных классов образует критериальную систему: произвольное множество является полным тогда и только тогда, когда оно не является подмножеством ни одного предполного класса. Множество этих предполных классов оказалось конечным и из их характеризации вытекает алгоритмическая разрешимость задачи о полноте. На этом пути C.B. Яблонским путем явного описания всех предполных классов была решена задача о полноте для функций трехзначной логики, а вместе с А. В. Кузнецовым найдены отдельные семейства предполных классов для логики произвольной конечной значно-сти. Затем усилиями многих исследователей [13]-[16] последовательно были открыты другие семейства предполных классов. Заключительные построения провел И. Розенберг в 1970 году [17]. При этом все предполные классы были описаны как классы сохранения отношений или предикатов.

Одновременно с изучением функций Ахзначной логики были сделаны попытки применения аппарата предполных классов в задаче о полноте для автоматов. Сначала В. Б. Кудрявцев [18] эффективно решил задачу о полноте и её- модификациях для функций с задержками. После этого им был получен фундаментальный результат негативного характера: континуальность множества предполных классов автоматных функций [19]. В дальнейшем, М. И. Кратко [20] установил алгоритмическую неразрешимость задачи о полноте относительно операций суперпозиции и обратной связи для конечных систем автоматов.

Ситуация не улучшается, если вместо автоматных функций рассматривать дефинитные автоматы. Автору удалось показать, что в классе дефинитных автоматов континуум предполных классов [44]. В. А. Буевич показал, что в классе дефинитных автоматов задача о полноте относительно операции суперпозиции алгоритмически неразрешима [28].

В силу своего определения [12, 33] автоматные функции и дефинитные автоматы являются бесконечпозначными и даже континуумзпачными функциями. Тем самым полагается, что вычисляющие эти функции автоматы «работают» бесконечно долго. Однако совершенно ясно, что каждое реальное кибернетическое устройство по истечении некоторого конечного промежутка времени прекращает свою «работу», то есть либо становится ненужным, либо переходит в начальное состояние. В связи с этим возникает проблема т-полноты. Множество М дефинитных автоматов называется т-полным, если для любого дефинитного автомата / с помощью операций суперпозиции из функций множествам можно получить функцию /', совпадающую с / на всех наборах, составленных из слов длины т.

В работах [33, 24] показано, что для решения проблемы т-полиоты операция обратной связи является несущественной, так как в данном случае эта операция выразима через операцию суперпозиции. Отсюда следует, что проблема т-полноты для т = 1 по сути является проблемой полноты в ко-нечиозначных логиках. Вместе с тем при т > 2 существует принципиальное отличие между этими задачами. Множество всех детерминированных отображений на словах длины т порождает специальное замкнутое подмножество в конечнозначной логике, существенно зависящее от параметра т. Используя естественную аналогию между проблемой т-полноты и полноты в конечнопорождённых замкнутых классах конечнозначных логик, можно ввести понятие т-предполного класса. Так как для проблемы т-полноты операция обратной связи несущественна, то каждый т-предполный класс в классе автоматных функций порождает т-предполный класс в классе дефинитных автоматов. Для этого достаточно рассмотреть множество всех дефинитных автоматов, принадлежащих заданному г-предполному классу в классе автоматных функций. Других т-предполных классов в классе дефинитных автоматов нет.

Можно показать, что всякое множество дефинитных автоматов (автоматных функций) является т-полным тогда и только тогда, когда целиком не содержится ни в одном из т-предполных классовсовокупность т-предполных классов конечна, может быть описана эффективно и образует минимальную т-критериальную систему [24], при этом множество 1-предполных классов изоморфно множеству предполных классов в конеч-нозначных логиках. Таким образом, для любого т > 1 существуют алгоритмы распознавания т полноты как для конечных множеств автоматных функций, так и для конечных множеств дефинитных автоматов.

С проблемой т-полноты тесно связана проблема А-полпоты. Множество М называется А-полным, если оно является т-полным для любого т. Из определения понятия А-полноты следует, что произвольный дефинитный автомат / можно «аппроксимировать» дефинитными автоматами, принадлежащими замыканию А-полного множества М. То есть можно выбрать последовательность дефинитных автоматов ъ /2, • • •, /г, • • • такую, что для любого т > 1 дефинитный автомат /г совпадает с / на всех наборах, составленных из слов длины т.

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

Проблема Аполноты исследовалась в работах В. А. Буевича [21]-[28]. Оказалось, что эта проблема алгоритмически неразрешима, как для автоматных функций [21], так и для дефинитных автоматов [28]. Тем не менее критерий полноты может быть сформулирован в терминах Апредполных классовчисло Апредполных классов счётно, множество Апредполных классов рекурсивно перечислимо и каждый предполный класс может быть описан эффективно [24]. Более того, каждый т-предполный класс является А-предполным и наоборот: для любого А-предполного класса существует т > 1, такое что этот А-предполный класс является в тоже время т-предполным.

Алгоритмически разрешимые случаи возникают при ограничении класса проверяемых систем. Так А. А. Часовских [29] описал в классе линейных автоматов все предполные классы, число которых оказалось счётным, и нашел, тем не менее, алгоритм распознавания полноты конечных систем. Для каждой конечной системы М автоматов он заключается в проверке непринадлежности М конечному числу предполных классов. То есть для произвольной конечной системы удаётся выделить конечную критериальную систему предполных классов. Тальхальм [30] установил свойства решетки замкнутых классов одноместных стабильных автоматов. К. В. Коляда в 1984 году [31] рассматривал классы функций, определённых на регулярных множествах (функции, сопряженные к автоматным) и обнаружил для одних классов алгоритмическую неразрешимость, а для других алгоритмическую разрешимость проблемы полноты.

Ещё- в 1961 г. А. А. Летичевским [32] был получен алгоритм решения задачи о полноте для конечных систем автоматов, выдающих номер своего состояния (автоматов Медведева) при наличии всех булевых функций. В 1986 году В. А. Буевич [23] показал алгоритмическую разрешимость проблемы Аполноты для систем автоматов, содержащих все булевы функции. В 1992 году Д. Н. Бабин [35] доказал, что существует алгоритм распознавания полноты системы автоматных функций при наличии в рассматриваемой системе всех булевых функций. Автору удалось получить аналогичные результаты для дефинитных автоматов, а именно показать, что для систем дефинитных автоматов вида Р2 и ь> существует алгоритм проверки на полноту и А-полноту таких систем дефинитных автоматов [41]. Для каждого конечного V он заключается в проверке непринадлежности и конечному числу предполных классов. Значит, для распознавания полноты и А-полноты существенна роль функций без памяти, присутствующих в базисе. Если присутствуют все функции без памяти, то проблемы Аполноты и полноты алгоритмически разрешимы как для автоматов [23, 35], так и для дефинитных автоматов [41]. Если присутствует, фактически, лишь тождественная функция х, то не существует алгоритма распознавания Аполноты и полноты ни для автоматных функций [20, 21], ни для дефинитных автоматов [21, 28].

Учитывая эти результаты, естественно исследовать на Аполпоту и полноту системы вида Р и и, где Р — некоторый класс Поста, а и — конечная система дефинитных автоматов (автоматных функций). Такие системы мы будем называть автоматными базисами Поста — также, как это делал Д. Н. Бабин в своих работах [36]-[40]. Возникает разделение классов Поста на сильные и слабые по их способности гарантировать разрешимость проблемы Аполноты и полноты. Для автоматных функций данную задачу исследовал Д. Н. Бабин. Ему удалось расслоить классы Поста на те, для которых проблемы полноты и Аполноты для систем автоматных функций вида разрешимы, и те, для которых эти проблемы неразрешимы. Оказалось, что проблемы полноты и Аполноты для систем вида Р и V разрешимы точно тогда, когда Р содержит либо функцию х + у + либо функцию хуМугУ хх [36]-[40].

Воспользуемся обозначениями из [1]. Для [л>2 ц+1.

1, ж2, • • ¦, хц+1) = / х1×2. .. • • • г=1 г,* — функция, двойственная к Нц. В частности.

1г2{хъ х2, жз) = Х1Х2 V х2хг V Х1Х3. Определим все классы Поста. Классы типа С :

Сг = [{х/у}], С2 = [{хУу, х + у + 1}],.

С3 = [{ху, х + у}], С4 = [{х V у, х{х + у + 1)}]. Классы типа М :

А = [{ху, х V г/, 0,1}], А2 = [{ху, XV у, 1}],.

0. ч д а.

С.

Ц ь / ж.

У i'5).

0,.

7,.

О,.

А3 = [{ал/, ж V у, 0}], А4 = [{ху, х V у}}.

Классы типа Ь: [{х + у, 1}], Ь2 = [{х + у + 1}], Ь3 = [{х + у}], ЬА = [{х + у + х}], Ьъ = [{х + у + г + 1}].

Классы типа И :

Бг = [{ху У хг У у г}], ?>2 = [{ху У уг У хг}], ?)3 = [{ху У хг У гу}]. Классы типа [{ж V У*-* хуУ хгУ у г}], Р22 = [{ж V у г, хуУхгУ у г}],.

Р32 = [{1, хуУхгУуг}], Г% = [{ж V у, ху У хг У у г}], ръ = [{х{уУг), хуУхгУуг}], Г% = [{х (у У г), ху У хг У у г}}, Р2 = [{0, хуУхгУ у г}}, Р2 = [{ху, хуУхгУ у г}]. Классы типа ^ при ¡-л > 2: = [{х У уг, КЦхъ хд+1)}], ^ = Щ (хъ ., К1' К^ • • •' ^+1)}]" = [{* V У> К^ • • ¦' ^+1)}]. рь = [ЫуУг),^^х,. ,^+1)}],^ =., хИ+1)}},.

К = [{О, К{хх,., ж^+О}], ?^ = [{ху, И^хг,., 2^+1)}]. Классы типа .Р00: [{х У = [{я V у*}], = [{1, я V уг}}, = [{х У у}], [{х (у У *)}], = [{*(г/ V *)}], = [{о, х (у У г)}], ВТ = [{ху}}. Классы типа 5: й = [{х У у}], = [{а: V у, 1}], ^ = [{х У У, 0}], 56 = [{х У у, 0,1}]. Классы типа Р :

Р = [{®-2/}], Рз = [{^, 0}], Р5 = [{*г/, 1}], Рв = [{^г/, 0,1}].

Классы типа О :

0 = [{я}], 02 = [{1}], 03 = [{0}], 04 = [{а?}], 05 = [{х, 1}],.

06 = [{х, 0}], О7 = [{0,1}], 08 = [{х, 0,1}], Оэ = [{х, х, 0,1}].

Автор исследовал на А-полноту и полноту системы вида Е и г/, где ^ — некоторый класс Поста, а ь> — конечная система дефинитных автоматов. Для проблемы А-полноты удалось отделить разрешимые случаи от неразрешимых. Оказалось, что проблема А-полноты для систем вида ^Ри^ разрешима точно тогда, когда Г содержит либо функцию х + у 4- г, либо функцию хуУугУ хх, либо функцию.

Х1Х2Х3 V Х1Х2Х4 V Х1Х3Х4 V Х2Х3Х4, либо функцию.

12:2 V V Х1Х4 V Ж2Ж3 V Х2Х4 V Ж3Ж4.

В результате на диаграмме Поста (см. рис.) появилась явная граница, отделяющая разрешимые случаи от неразрешимых.

Следует отметить, что хотя операция обратной связи для решения проблемы А-полноты оказывается несущественной, результаты, полученные для дефинитных автоматов отличаются от результатов, полученных для автоматных функций Д. Н. Бабиным. Так, для классов³, где г = 1, 2,., 8, проблема А-полноты для систем автоматных функций алгоритмически неразрешима, а проблема А-полноты для систем дефинитных автоматов алгоритмически разрешима. В то же время, можно показать, что если для класса Поста Р проблема А-полноты для систем автоматных функций вида Р и у разрешима, то она разрешима и для аналогичных систем дефинитных автоматов.

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

Как было сказано выше, автор доказал, что проблема Л-полноты для систем вида Р и V алгоритмически разрешима тогда и только тогда, когда ?>2 С Р, ЬА С Р, Р23 С Р, либо Р63 С Р.

Легко убедиться, что если Р' С Р и проблема Л-полноты алгоритмически неразрешима для систем вида Р и и, то она алгоритмически неразрешима и для систем вида Р' и V. Аналогично, если Р С Р' и проблема Л-полноты алгоритмически разрешима для систем видаРи^, то она алгоритмически разрешима и для систем вида Р' и V. Также, если Р* — класс, двойственный к Р относительно замены 0 на 1, то проблема Л-полноты для систем вида Р и г/, алгоритмически разрешима тогда и только тогда, когда алгоритмически разрешима проблема Л-полноты для систем вида Р* и р. А значит, для доказательства указанной классификации достаточно рассмотреть только граничные случаи и только левую половину диаграммы Поста. То есть, достаточно доказать неразрешимость для классов¹, Ре и Од, и разрешимость на классах -^4,.

Данная работа состоит из «Введения», «Основных понятий и результатов», а также трёх глав. В отличие от «Введения» в «Основных понятиях и результатах» все определения и утверждения даются формально и строго.

Первая глава посвящена разрешимым случаям проблемы Л-полноты. Как было указано выше, достаточно рассмотреть только граничные случаи, а именно Дз, Ь4,, • Для каждого из них строится несколько счётных семейств Л-предполных классов, которые образуют критериальную систему. Затем для каждой конечной системы дефинитных автоматов из каждого семейства выделяется конечное множество Л-предполных классов. Каждый Л-предполный класс описывается как класс сохранения отношения. Так как мы рассматриваем только системы, содержащие!^, ?4, или^, то нас интересуют не все А-предполные классы [24], а только те, которые содержат все функции из ?>2, или В работе встречаются унарные, бинарные отношения, а также отношения арности 4. Приведём некоторые примеры классов сохранения этих отношений. Для каждого р > 2 определяется множество автоматов, у которых выход в момент времени р не зависит от входа в момент времени р — 1. Для каждого р > 1 определяется множество всех автоматов, у которых выход в момент времени р самодвойственно зависит от входа в момент времени р множество всех автоматов, у которых выход в момент временир линейно зависит от входа в момент времени р множество всех автоматов, у которых выход в момент времени р монотонно зависит от входа в момент времени р. Любопытно, что самая большая сложность возникает с унарными отношениями. Более того, именно унарные отношения строятся для доказательства неразрешимости во второй и третьей главе.

Ранее упоминалось, что разрешимость проблемы А-полноты для систем ?>2 и ъ> и ?4 и р можно вывести как следствие из результатов Д. Н. Бабина [40], полученных для автоматных функций. Но автор приводит своё- доказательство этих фактов в работе, так как в процессе доказательства демонстрируется общий подход к решению такого рода задач. А имеино, показывается, как наличие соответствующих функций без памяти ограничивает множество унарных отношений, которые необходимо рассматривать. Такое ограничение позволяет для каждой конечной системы дефинитных автоматов из счётного множества А-предполных классов выделять конечное множество. Именно такой подход позволяет решать задачу об А-полноте для классов где г = 1, 2,., 8, хотя для автоматных функций данная задача алгоритмически неразрешима. Более того, по мнению автора описание А-предполных классов и их ограничений, необходимых для решения задачи об А-полноте при наличии классов или Ь4, имеет самостоятельную ценность.

Во второй главе рассматриваются простейшие неразрешимые случаи, а именно б’о, Рв и О9. Как было сказано выше неразрешимость сводится к проблеме конечности последовательности продукций Поста. Тройка в = (И, /9, и), где П = {?1, (?2} ¦ ¦ • 5 с^}, -О* — множество слов в алфавите .О, р И —ь ?)*, уо (^) =⁵ ^ — натуральное число, называется системой однородных продукций Поста. Если I > си, то скажем, что 0 применима к слову? = с? ггб?г2. и слово =. назовём результатом применения в к слову Последовательность ?2, £з> • • •, такую что, а г-+х = назовём последовательностью продукций Поста слова Последовательность продукций конечна, если последнее слово имеет длину меньшую ш. Известно [34], что существует система однородных продукций Поста, для которой не существует алгоритма, по слову? решающего вопрос о конечности последовательности продукций слова Зафиксируем эту систему продукций Поста После этого продукции Поста специальным образом кодируются словами в алфавите {0,1}. Для каждого слова? строятся параметрические системы дефинитных автоматов:

Ех = {ж V р, 0,1, ИЪ, Ть Т2,., П, ТУ.

Е2 = {ж, О, Со, Т1- Т2,., Тк,.

Автомат Т^ выдает на выходе закодированное слово, а автоматы Т2, ., Т^ позволяют из одного элемента последовательности продукций строить следующий элемент последовательности. При этом доказывается, что каждая из систем А-полна точно тогда, когда последовательность продукций слова? бесконечна.

Следует заметить, что доказательство существенно отличается от доказательства аналогичных утверждений для конечных автоматов [36, 39, 40]. В отличие от конечных автоматов не существует дефинитных автоматов, не зависящих от входа, которые бы выдавали периодическую последовательность на выходе. А значит мы пе можем в каждый момент времени находить начала частей, которые получились при кодировании продукций. Для корректного «чтения» и «преобразования» продукций метод кодирования продукций существенно усложняется. Есть ещё- одно существенное отличие доказательств для конечных автоматов и дефинитных автоматов. При некорректном использовании конечного автомата, он запоминает «ошибку» и во все последующие моменты уже не работает корректно. Дефинитный автомат забывает любую информацию через определённое число шагов. А значит даже после некорректного использования дефинитный автомат начнёт работать как и раньше. Это тоже значительно усложняет конструкцию, так как приходится следить, чтобы «ошибка», возникшая в какой-то момент времени, не могла исчезнуть.

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

В третьей главе рассматривается самый сложный неразрешимый случай, а именно рассматриваются классы и^. Техника доказательства неразрешимости сильно отличается от техники доказательства во второй главе. И хотя задача опять решается сведением к проблеме конечности последовательности продукций Поста, отличие настолько существенно, что доказательство выделено в отдельную главу. В отличие от доказательства во второй главе, где используются специальные дефинитные автоматы, с помощью которых можно из одного элемента последовательности продукций построить следующий элемент последовательности, в данном случае вся последовательность продукций сначала кодируется специальным образом с помощью нулей и единиц, а потом только проверяется, что последовательность записана корректно. Ещё- больше усложняется конструкция, позволяющая выделять части, которые получились при кодировании продукций. Суть этой конструкции заложена в определении унарного отношения, которое сохраняется в случае, если последовательность продукций конечна. Одно из принципиальных отличий доказательства в этой главе от доказательства во второй главе заключается в следующем. Во второй главе автоматы строились таким образом, что «ошибка», возникшая в какой-то момент времени, не могла исчезнуть, а оставалась записанной в сверхслове. Наличие же функций Нц для ¡-л > 4 делает это невозможным. Специальным образом подобрав слова, всегда можно избавиться от «ошибки», записанной на сверхслове. Для этого достаточно проследить, чтобы «ошибки» в разных сверхсловах были в далёкие друг от друга моменты времени. Для решения данной проблемы был придуман новый подход, в котором такого понятия, как «ошибка» уже нет. В процессе доказательства мы сразу строим автоматы так, чтобы они сохраняли сложное унарное отношение.

Основные результаты работы опубликованы в статьях [42] — [45].

Помимо этого результаты диссертации неоднократно докладывались на семинарах механико-математического факультета МГУ им. М. В. Ломоносова «Теория автоматов» (2005;2010 гг.) и «Кибернетика и информатика» (2005;2010 гг.) под руководством академика В. Б. Кудрявцева.

Также результаты докладывались на следующих конференциях:

• международные научные конференции студентов, аспирантов и молодых ученых «Ломоносов» (Москва, МГУ им. М. В. Ломоносова, 2007, 2008, 2009 и 2010 гг.);

• IX международный семинар «Дискретная математика и её- приложения», посвященный 75-летию со дня рождения академика О. Б. Лупанова;

• научные конференции «Ломоносовские чтения» (Москва, МГУ им. М. В. Ломоносова, 2007, 2008 и 2009 гг.);

• международная конференция «Интеллектуальные системы и компьютерные науки» (Москва, МГУ им. М. В. Ломоносова, 2006 г.);

• третья научная конференция студентов и аспирантов кафедры МаТИС механико-математического факультета МГУ (Москва, МГУ им. М. В. Ломоносова, 2007 г.).

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

Пусть N = {1,2,3,.} — множество всех натуральных чисел, N0 = 1^и{0}, Е2 — {0,1}, Е2 — множество всех слов длины I в алфавите Е — множество всех бесконечных последовательностей нулей и единиц. Далее такие последовательности называем сверхсловами. МножествоЕп состоит из всех наборов (о,!, а^, • • •, <хп), где а^? Е. Если а, Ь е Е2, то, а — отрицание а, а V Ь — дизъюнкция, а и 6, а&-&- — конъюнкция, а и 6, а + Ь — сложение по модулю 2. Множество всех булевых функций будем обозначать Р2.

Пусть, а — слово или сверхслово. Для п е N через а (п) обозначим п-ый элемент а. Обозначим через |си| длину слова адля сверхслова, а будем полагать, что, а — со. Для слова а, такого что |а| > к, определим го- = а (|о:| — к + 1). а (|а| — 1) а-(|а|).

Для слова или сверхслова а, такого что, а > к > I положим ка = а (1)а (2). а (к), [¡-]ка = а (к — I + 1) а (к -1 + 2). а{к).

Для произвольного слова, а определим слово о^ = (у.а «. а, и сверхслово ск°° = ааа.

Пусть п, к € N. Функция Т: Еп —> Е называется дефинитным автоматом с п входами высоты /г, если существуют функции: (Е23)П Е2 {у = 1, 2,3,. ., /г), такие что для любых х, Х2,., хп? Е выполняется: т (хг, х2:.. • = Л (]1Ж1,]1Ж2, • • •, Ь хп).

Т (х 1, Ж2, • • •, хп)(2) = ь (]2хъ]2×2, • ¦ • ,]2хп).

Т (х1,х2, Хп){К) = ЛО/гГЕь ]/1Х21 ]}гХп) Т (х 1, Ж2,. • •, + 1) = Ь ([нк+1Х1, Ы/г+1², — - •, Ы/г+1^г).

Т (хъх2, ¦ ¦ ., хп)(Н + г) = Д ([л]л+"Ж1, [л]л+"Ж2,., [л]л+гЖ").

Таким образом, согласно нашему определению автомат высоты Н является также автоматом высоты /г +1. Элемент Т (жх, х2,., хп)(у) будем называть элементом на выходе автомата Т в момент времени, а ??0) — элементом, подаваемым на ¿—ый вход в момент времени ]. Для ^ — 1,., /г — 1 функция определяет элемент на выходе автомата Т в момент времени, а функция Д определяет элемент на выходе автомата, начиная с момента времени /г.

Пусть Т — автомат высоты ¡-г. Для р Е N определим функцию Тр: (Е2Р)п —Е2. Если р < /г, то положим.

Тр (аи а2,., ап) = /р (аь а2,., ап).

Для р > Н положим.

Тр (аь а2,., ап) = //г ([/гаь [Ла2,. -, [лап).

Таким образом, для любого р функция Тр определяет элемент на выходе автомата Т в момент времени р. Функции Тр, где р = 1,. будем называть порождающими. Нетрудно убедиться, что для задания дефинитного автомата необходимо задать высоту автомата и порождающие функции. Доопределим естественным образом каждый автомат на словах длины р. Будем полагать, что для любых с*1- а2,., ап € Е2Р выполняется Т{аъ а2, • ¦ •, ап) = /3, где ?3 е Е2Р и /?($) = Т5(]Ааь ]3а2,]ва") для любого 5 < р.

Множество всех дефинитных автоматов обозначим Va• Для Т? Va через h (T) обозначим наименьшую высоту автомата Т. Ясно, что каждой булевой функции из Р2 соответствует дефинитный автомат высоты 1. Будем использовать стандартные обозначения для автоматов высоты 1, а именно: х, xSzy — ху, х V у, х + у — дефинитные автоматы 7, Т2, Т3 и Т4 высоты ' 1, такие что выполняется Tl (a) = а, Т^а,/?) = aSz/3, Т^(а,/3) = а V /3,.

ТЦа,/3) = с* + /3.

Пусть 5С — автомат высоты 2 с одним входом, для которого S](а) = с, = а (1), Автомат 5С будем называть задержкой с начальным состоянием с.

Пусть М С Va. Фиксируем некоторое счётное множество.

U = {ui, U2, U3i • • •}, элементы которого будем называть переменными. Индуктивно определим понятие терма над множеством М :

1) Если и? U, то и — терм над М.

2) Если F — автомат с п? N входами, F? М, т, ., тп — термы над М, то выражение F (ri, Т2,., тп) — терм над М.

Термы, отличные от переменных, назовём собственными. Пусть т — произвольный терм, (xi, x2, ¦ ¦ ¦, ocm) — набор попарно различных переменных, содержащий все переменные, использованные при построении терма т. Тогда через т (хг, х2, ¦ ¦ ¦, xm) обозначим функцию г: Еш —> Е, определяемую индуктивно:

1) Если т — хс — переменная, 7 = (71, j2,., 7m)? Em, то определим т (хъх2,., жт)(7) = 7е.

2) Если г = F (rb г2,. ., гп), 7 = (71,72,., 7m) G то определим т{хъх2,., жт)(7) = F (ri (a-i, iC2, — • •, жто)(7),. ., тп (хъх2,., жш)(7)).

О функции Т, такой что Т = т (х 1, Ж2, •., хт) для некоторого собственного терма т над множеством М, будем говорить, что она получена термальными операциями из дефинитных автоматов множества М. Нетрудно проверить, что функция Т также будет дефинитным автоматом, поэтому мы можем ввести на множестве Та оператор замыкания [ ] относительно термальных операций — такое отображение, которое каждому множеству М С Та сопоставляет множество [М] всех автоматов, которые можно получить термальными операциями из автоматов множествам. Определённый выше оператор замыкания также известен как оператор замыкания относительно операции суперпозиции [33].

Множество М называется замкнутым, если [М] = Ммножество М называется полным, если [М] = ТаПусть т 6 М, скажем, что автоматы Т и Т9 с п входами т-равны, если для любого г < г выполняется Т[ = XОбозначим через [М)т множество всех дефинитных автоматов, т-равных получающимся из М с помощью термальных операций. Множество М называоо ется А-полным, если [М]т = Та для любого т. Определим [М]д = р| [М]т. т=1.

Проблема А-полноты для Та состоит в описании всех А-полных множеств М. Множество М называется Л-замкнутым, если [М]д = ММ называется А-предполным, если [М]а ^ Та и для любой / е Та М выполняется [М и {/}]Л = Та.

Нетрудно заметить, что дефинитные автоматы — это все автоматы, которые можно получить с помощью термальных операций из автоматов из Р2 и задержки. Другими словами [.Р2 и {<5с}] = Та, где 8С — задержка с начальным состоянием с. Отсюда, в частности, следует, что [{х/у, «Б'с}] = Та.

Постом полностью описаны все замкнутые относительно операции суперпозиции «классы булевых функций [1, 8]. Все они конечнопорожденные и образуют счётную решетку по включению.

Пусть Р — замкнутый класс булевых функций. Определим проблему А-ПОЛНОТА (-Р): дана конечная система V дефинитных автоматов, заданных своими порождающими функциямитребуется установить, А-полна ли система Р и V.

Нетрудно убедиться, что если ^ С и проблема А-ПОЛНОТА (^) алгоритмически разрешима, то А-ПОЛНОТА (-Р') также алгоритмически разрешима. Аналогично, если Р' С. Р и проблема А-ПОЛНОТА (^) алгоритмически неразрешима, то А-ПОЛНОТА^') также алгоритмически неразрешима. Также, если Р* — класс, двойственный к Р относительно замены 0 на 1, то проблема А-ПОЛНОТА (^*) алгоритмически разрешима точно тогда, когда алгоритмически разрешима проблема А-ПОЛНОТА (^). Воспользуемся обозначениями из [1]. Для ?1 > 2.

М+1×2, ¦ ¦ •, хц+х) = / хгх2 ¦.. х¹×1+1. .. х/1+1, г=1 г* — функция, двойственная к К^. В частности.

12(^1, х2, хз) = х±х2 V х2×3 V х1×3. [{ВД], ^ = [{Л3}], П2 = [{/г2}], и = [{Я + 2/ + *}], ЯГ — К*^}], = [{ж&у}], 56 = [{х V у, 0,1}], Р6 = [{ж&т/, 0,1}], Од = [{ж, 0}], ^ =.

Были доказаны следующие три теоремы.

Теорема 1. [43] Проблема А-ПОЛНОТА (Р) алгоритмически разрешима для каэюдого Р Е? > -^2? ?4}.

Теорема 2. Проблема А-ПОЛПОТА (Р) алгоритмически неразрешима для каждого Р Е {¿->б, Ре, Од}.

Теорема 3. [45] Проблема А-ПОЛНОТА (Р) алгоритмически неразрешима для каэ! сдого Р Е {^4, ^в}.

Эти три теоремы позволяют все классы Поста разделить на сильные и слабые по их способности гарантировать разрешимость проблемы А-полноты для дефинитных автоматов. Таким образом, может быть сформулирована.

Теорема 4. Проблема А-ПОЛНОТА (Р) алгоритмически разрешима тогда и только тогда, когда для какой-то f Е {/?2,^ + У + ^3} выполняется / Е i71¦

1. Post Е. Two-Valued 1. erative Systems of Mathematical Logic. Princeton Univ. Press, Princeton, 1941.

2. Automata Studies, ed. by C.E. Shannon and J. Mc Carthy. Princeton, 1956 (русский перевод: Сборник статей под редакцией Маккарти и Шеннона. ИЛ, Москва, 1956.).

3. Kleene S. С. Representation of events in nerve nets and finite automata. Automata Studies, ed. by C.E.Shannon and J. Mc Carthy, Princeton, 1956, 3−41.

4. M. Perles, M.O. Rabin, E.Shamir. Theory of definite automata. IEEE Trans, on Electronic Computers, EC-12 (1963), 233−243.

5. G. Ginzburg. About some properties of definite, reverse definite and related automata. IEEE Trans, on Electronic Computers, EC-15 (1966), 809−810.

6. B. Imreh. On finite definite automata. Acta Cybernetica, 7 (1984), 61−65.

7. M. Steinby. On definite automata and related systems. Ann. Acad. Sci. Fenn., Ser. A 1,444 (1969).

8. Яблонский С. В., Гаврилов Г. П., Кудрявцев В. Б. Функции алгебры логики и классы Поста. Наука, Москва, 1966.

9. Кузнецов А. В. О проблемах тождества и функциональной полноты для алгебраических систем. Труды третьего всесоюзного математического съезда. Т. 2. Москва. Изд. АН СССР, 1956, с.145−146.

10. Кузнецов А. В. Структуры с замыканием и критерии функциональной полноты. Успехи математических наук. Т. 16, № 2, 1961, с.201−202.

11. Яблонский С. В. Функциональные построения в fc-значной логике. Труды математического института им. В. А. Стеклова. АН СССР, 1958, Т. 51, с.5−142.

12. Яблонский С. В.

Введение

в дискретную математику. Наука, Москва, 1986. с.5−142.

13. Ло Чжу-Кай, Лю Сюй Хуа. Предполные классы, определяемые бинарными отношениями в многозначной логике. Acta Sei. Natur. Univ. Jilinensis, 1963, № 4.

14. Захарова Б. Ю. Критерий полноты для системы функций из Р^. Проблемы кибернетики. 1967, № 18, с.5−10.

15. Мартынюк В. В. Исследование некоторых классов функций в многозначных логиках. Проблемы кибернетики. 1960, № 3, с.49−60.

16. Пап Юн-Цзе. Один разрешающий метод для отыскания всех предпол-ных классов в многозначной логике. Acta Sei. Natur. Univ. Jilinensis, 1963, № 3.

17. Rosenberg J. La structure des fonctions de plusiers variables sur un ensemble fini. Comptes Rendus Acad. Sei. Paris, 1965 № 260, c.3817−3819.

18. Кудрявцев B.B. Теорема полноты для одного класс автоматов без обратных связей. Проблемы кибернетики. 1962, № 8, с. 91−115. // ДАН СССР. 1963. Т. 151. m 3. С. 493−496.

19. Кудрявцев В. Б. О мощностях множеств предполных классов некоторых функциональных систем, связанных с автоматами // ДАН СССР. 1963. Т. 151. № 3. С. 493−496.

20. Кратко М. И. Алгоритмическая неразрешимость проблемы распознавания полноты для конечных автоматов. Москва, ДАН СССР, 1964, т. 155.

21. Буевич В. А. Об алгоритмической неразрешимости распознавания А-полноты для о.д.-функций // Математический заметки. Т. 12, № 6. 1972. С. 687−697.

22. Буевич В. А. О т-полноте в классе автоматных отображений. Москва, ДАН СССР, т. 252. № 5. 1980.

23. Буевич В. А. Условия Аполноты для автоматов. М.: Изд-во МГУ, 1986. // Математический заметки. Т. 12, № 6. 1972. С. 687−697.

24. Буевич В. А. Условия А-полноты для конечных автоматов, ч.1, ч.2. Издательство МГУ, 1986, 1987 г. г.

25. Буевич В. А. О т-полноте в классе детерминированных функций. Доклады РАН, т. 326. № 3. 1992.

26. Буевич В. А. О т-полноте систем, содержащих все одноместные ограниченно-детерминированные функции. Математические вопросы кибернетики. Вып. 8. 1999.

27. Буевич В. А. О существовании алгоритма для распознавания А-полноты систем, содержащих все одноместные ограниченно-детерминированные функции. Математические вопросы кибернетики. Вып. 8. 1999.

28. Буевич В. А., Клиндухова Т. Э. Об алгоритмической неразрешимости задач об А-полноте и полноте для дефинитных ограниченно-детерминированных функций. Москва, Математические вопросы кибернетики. Вып. 10. 2001.

29. Часовских А. А. О полноте в классе линейных автоматов. Математические вопросы кибернетики. Вып. 3. 1995, с. 140−166.

30. Тальхайм Б. О. О решетке замкнутых классов стабильных автоматов. Методы и системы диагностики. Вып. 1, Саратов, 1979.

31. Коляда К. В. О полноте регулярных отображений. Проблемы кибернетики. Вып. 41. М. Наука, 1980., с.41−49.

32. Летичевский A.A. Условия полноты для конечных автоматов. Вычислительная математика и математическая физика, № 4, 1961, с.702−710.

33. Кудрявцев В. Б., Алешин C.B., Подколзин A.C.

Введение

в теорию автоматов. Наука, Москва, 1985.

34. Мальцев А. И. Алгоритмы и рекурсивные функции. Наука, Москва, 1986.

35. Бабин Д. Н. Разрешимый случай задачи о полноте автоматных функций. Москва, Дискретная математика, 1992. Т. 4, вып. 4. с. 41−56.

36. Бабин Д. Н. Неразрешимость проблемы полноты и А-полпоты некоторых систем автоматных функций. Москва, Дискретная математика, 1995. Т. 7, вып. 2. с. 52−65.

37. Бабин Д. Н. О разрешимости проблемы полноты для специальных систем автоматных функций. Москва, Дискретная математика, 1996. Т. 8, вып. 4. с. 79−91.

38. Бабин Д. Н. Алгоритмическая разрешимость свойств полноты и А-полноты конечных систем автоматных функций с линейной истинностной частью. Москва, Интеллектуальные системы, т. 3, 1998, с. 51−69.

39. Бабин Д. Н. Конечность множества автоматных базисов Поста с разрешимой проблемой полноты. Москва, Дискретная математика, 1998. Т. 10, вып. 3. с. 57−64.

40. Бабин Д. Н. О классификации автоматных базисов Поста по разрешимости свойств полноты и А-полноты // Доклады Академии наук. № 4. Т. 367. 1999. С. 439−441.

41. Жук Д. Н., Присмотров Ю. Н. О проблеме полноты в классе автоматов без обратной.связи. Москва, Интеллектуальные системы, т. 11, 2007, с. 439−472.

42. Жук Д. Н. О неразрешимости проблемы полноты для дефинитных автоматов. Москва, Интеллектуальные системы, т. 12, 2008, с. 211−228.

43. Жук Д. Н. Разрешимые случаи задачи об А-полноте для дефинитных автоматов. Москва, Интеллектуальные системы, т. 13, 2009, с. 273−312.

44. Жук Д. Н. Континуальность множества предиолных классов в классе дефинитных автоматов. Москва, Интеллектуальные системы, т. 13, 2009, с. 41−48.

45. Жук Д. Н. О классификации автоматных базисов Поста по разрешимости свойств А-полноты для дефинитных автоматов. Москва, Дискретная математика, 2010. Вып. 2. с. 41−56.