АВТОМАТОВ ПОЛНЫЕ СИСТЕМЫ это:

АВТОМАТОВ ПОЛНЫЕ СИСТЕМЫ

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

Лит.:[1] Яблонский С. В., "Тр. матем. ин-та АН СССР", 1958, т. 51, с. 5-142; [2] Кудрявцев В. В., "Проблемы кибернетики", 1962, в. 8, с. 91-115; [3] его же, там же, 1965, вып. 13, с. 45-74; [4] Кратко М. И., "Алгебра и логика. Тр. семинара", 1964, т. 3, № 2, с. 33-44; [51 Л е-тичевский А. А., Условия полноты в классе автоматов Мура, К., 1963; [6] Буевич В. А., "Проблемы кибернетики", 1970, в. 22, с. 75-83. В. Б. Кудрявцев.


Математическая энциклопедия. — М.: Советская энциклопедия. . 1977—1985.

Смотреть что такое "АВТОМАТОВ ПОЛНЫЕ СИСТЕМЫ" в других словарях:

  • АВТОМАТОВ ТЕОРИЯ — раздел теории управляющих систем, изучающий математич. модели преобразователей дискретной информации, называемые автоматами. С определенной точки зрения такими преобразователями являются как реальные устройства (вычислительные машины, автоматы,… …   Математическая энциклопедия

  • АВТОМАТОВ МИНИМИЗАЦИЯ — минимизация значений параметров автоматов, приводящая к эквивалентным и в определенном смысле оптимальным автоматам. Задача А. м. возникает при синтезе автоматов, и ее специфика зависит от подхода к их изучению. При макроподходе минимизируют, как …   Математическая энциклопедия

  • ЭКВИВАЛЕНТНЫЕ ПРЕОБРАЗОВАНИЯ — управ ляющих систем преобразования, сохраняющие отношение эквивалентности (о. э.) управляющих систем (у. с.). Используются в задачах оптимизации, контроля, а также как средство характеризации (напр., аксиоматизации) определенных классов у. с.;… …   Математическая энциклопедия

  • Булева функция — В данной статье или разделе имеется список источников или внешних ссылок, но источники отдельных утверждений остаются неясными из за отсутствия сносок …   Википедия

  • Карацуба — Карацуба, Анатолий Алексеевич Карацуба Анатолий Алексеевич Дата рождения: 31 января 1937(1937 01 31) …   Википедия

  • Карацуба, Анатолий Алексеевич — Карацуба Анатолий Алексеевич Дата рождения: 31 января 1937 …   Википедия

  • Украинская Советская Социалистическая Республика —         УССР (Украïнська Радянська Социалicтична Республika), Украина (Украïна).          I. Общие сведения          УССР образована 25 декабря 1917. С созданием Союза ССР 30 декабря 1922 вошла в его состав как союзная республика. Расположена на… …   Большая советская энциклопедия

  • Nintendo — Об альбоме одноимённого музыкального проекта см. Nintendo (альбом). Nintendo Company, Limited …   Википедия

  • Pump It Up — Разработчики Andamiro/F2/Freevolt/Nexcade Издатель …   Википедия

  • Нинтендо — Nintendo Company, Limited Год основания 1889 Ключевые фигуры Сатору Ивата (президент и генеральный директор) Тип Публичная компания Девиз компании Различные …   Википедия


Поделиться ссылкой на выделенное

Прямая ссылка:
Нажмите правой клавишей мыши и выберите «Копировать ссылку»