Зарегистрироваться

Автоматов полные системы

Категории Математическая кибернетика | Под редакцией сообщества: Математика

Автоматов полные системы – специальные подмножества заданного класса M автоматов, на котором определено некоторое множество Ω  операций со значениями в M. Эти подмножества обладают следующим основным свойством (свойством полноты): множество всех автоматов, которые получаются путем конечного числа применений операций из Ω к автоматам из заданного подмножества , совпадает с M. Задача о том, обладает ли множество свойством полноты или нет, называемой проблемой полноты (п. п.) для автоматов. Эта проблема изучена для различных моделей автоматов и операций. В порядке нарастания сложности объекта исследования сюда могут быть отнесены истинностные автоматы, автоматы, реализующие функции с задержками (т. е. функции k-значной логики с некоторым временным сдвигом), конечные автоматы и др.

П. п. для истинностных автоматов с обычно рассматриваемыми операциями суперпозиции по существу совпадает с п. п. для функций k-значной логики (см. Многозначная логика) и достаточно хорошо изучена. Под синхронной суперпозицией понимается такая суперпозиция автоматов, когда ко всем входам присоединяются автоматы, реализующие функции с одной и той же задержкой. Из найденных в этих случаях критериев полноты вытекает, в частности, существование алгоритма, устанавливающего для любой конечной системы автоматов ее полноту или неполноту. Основные критерии полноты даются в терминах так называемых предполных классов (т. е. таких подмножеств класса M, которые замкнуты относительно операций из Ω и каждый из которых вместе с любым автоматом, ему не принадлежащим, образует полную систему). Показано, что множество A является полным тогда и только тогда, когда оно не является подмножеством ни одного предполного класса, которые, в свою очередь, полностью описаны. Этот подход успешно осуществлен в целом ряде других случаев. Принципиально он возможен и при рассмотрении конечных автоматов, когда в качестве Ω выбираются операции суперпозиции автоматов и операция обратной связи (см. Автоматов композиции). Здесь также справедлив указанный выше критерий, однако в этом случае установлено, что семейство предполных классов является континуальным, что исключает возможность получения эффективных критериев полноты в указанных терминах. Заметим, что во всех описанных случаях существуют конечные полные системы, и потому п. п. для произвольных систем автоматов сводится к п. п. для конечных систем автоматов. С последним обстоятельством, как и выше, связана задача об алгоритмической разрешимости п. п. для конечных систем конечных автоматов. Эта проблема может быть обобщена: для данного автомата a  и множества B требуется определить, может ли a быть получен из автоматов множества B при помощи заданного набора операций. Таким образом приходят к изучению предиката  P(x,y) - "автомат x реализуется набором y". Установлено, что проблема распознавания реализуемости алгоритмически неразрешима при любом фиксированном a, т. е. одноместный предикат P(a,y) нерекурсивен. С другой стороны, при различных значениях B параметра  y предикат p(x,B) может быть как рекурсивным, так и нерекурсивным. В связи с алгоритмической неразрешимостью п. п. для автоматов возникает задача об отыскании классов множеств, для которых указанная проблема имеет эффективное решение. В частности, существует алгоритм для распознавания полноты систем, состоящих только из автоматов Мура и всех истинностных автоматов. С п. п. связана задача нахождения конкретных полных множеств автоматов с заданными свойствами. Установлено, что для любого натурального n существует полная система автоматов, никакая собственная подсистема которой не является полной, и таких систем при заданном n бесконечно много. Существует также в некотором смысле простейший автомат с двумя состояниями, двумя входными и одним выходным каналами, который образует полную систему. П. п. рассматривается также для различных обобщений конечных автоматов и операций над ними; другое направление обобщений связано с введением различных отношений эквивалентности в рассматриваемом классе автоматов.

Рекомендуемая литература

Яблонский С.В., <<Тр. матем. ин-та АН СССР>>, 1958, т. 51, с. 5-142;

Кудрявцев В.Б., <<Проблемы кибернетики>>, 1962, в. 8, с. 91-115;

его же, там же, 1965, вып. 13, с. 45-74; [4] Кратко М.И., << Алгебра и логика. Тр. семинара>>, 1964, т. 3, №2, с. 33-44;

Летичевский А.А., Условия полноты в классе автоматов Мура, К., 1963;

Буевич В.А., <<Проблемы кибернетики>>, 1970, в. 22, с. 75-83.

Эта статья еще не написана, но вы можете сделать это.