ПОЛНОТЫ ПРОБЛЕМА в теории автоматов

— нахождение критериев полноты для множеств автоматов. При исследовании П. п. для задания автоматов обычно используют язык сетей логических. Множество автоматов наз. полным для данного класса автоматов и данного набора операций над автоматами, если любой автомат из ЗЛ может быть получен из автоматов множеств при помощи указанных операций. Если говорят о полном множестве, не указывая класса

автоматов и операций, то обычно подразумевают, что мн-во состоит из конечных автоматов и что любой автомат конечный может быть получен из автоматов мн-ва при помощи операций суперпозиции и обратной связи. Систему указанных автоматов и операций обозначим через Р.

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

В связи с поисками эффективных критериев полноты возникает задача об отыскании алгоритма, устанавливающего полноту или неполноту любой конечной системы автоматов. Эта проблема может быть обобщена: для данного автомата А и конечного множества автоматов требуется определить, может ли А быть получен из автоматов мн-ва при помощи заданного набора операций. Т. о. приходят к изучению предиката Р (X, Y) — «автомат X реализуется множеством У». Установлено, что проблема распознавания «реализуемости» алгоритмически неразрешима при любом фиксированном А, т. е. одноместный предикат имеет нерекурсивное мн-во истинности. С другой стороны, при некоторых значениях параметра Y предикат Р (X, Y) имеет как рекурсивные, так и нерекурсивные множества истинности.

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

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

Лит.: Яблонский С. В. Функциональные построения в -значной логике. «Труды Математического института им. В. А. Стеклова АН СССР», 1958, т. 51; Летичевский А. А. Условия полноты в классе автоматов Мура. В кн.: Теория автоматов. Семинар, в. 2. К., 1963; Кратко М. И. О существовании нерекурсивных базисов конечных автоматов. «Алгебра и логика», 1964, т. Кудрявцев В. Б. О мощностях множеств предполных множеств некоторых функциональных систем, связанных с автоматами. «Проблемы кибернетики», 1965, в 13. М. И. Кратко, В. Б. Кудрявцев.