§ 4.4. Абстрактная агрегатизация автоматов и последовательностных машин

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

Процесс построения сетей с использованием лишь автоматов и преобразователей из заданного набора назовем агрегатизацией конечных автоматов и последовательностных машин.

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

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

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

Так, например, важный полный набор составляет: двоичный элемент задержки (т. е. элемент задержки с двумя состояниями), дополненный элементами, выполняющими операции дизъюнкции, конъюнкции и отрицания.

Действительно, любой автомат можно заместить логической абстрактной структурой, т. е. абстрактной структурой, у которой все и все . Но такую абстрактную структуру можно представить сетью, состоящей лишь из двоичных элементов задержки и логических преобразователей. Любая же логическая функция может быть представлена конъюнктивной формой дизъюнктивных групп, и значит, любой логический преобразователь может быть составлен из преобразователей, реализующих дизъюнкцию, конъюнкцию и отрицание (см. гл. I и II). Следовательно, описанный набор является полным.

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

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

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