Задача о полноте автоматного базиса

Набор структурных автоматов называется полным (или автоматным базисом), если из них можно построить любой наперед заданный структурный автомат.

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

Теорема. Система автоматов , содержащая полный набор ФЭ и - триггер (или -триггер) является полной.

Доказательство. Рассмотрим произвольный автомат , заданный соотношениями (2), и опишем его схему из указанных автоматов, называемую канонической структурой (рис. 6).

Схема состоит из двух частей.

…

…

…

Рис. 6.

Левая половина называется запоминающей частью. Она состоит из триггеров, набор состояний которых образует состояние автомата: если в момент времени

, …, ,

то это означает, что автомат находится в состоянии .

Правая половина называется комбинационной частью и представляет СФЭ. Входы этой схемы:

1) двоичное слово – входной сигнал автомата ;

2) двоичное слово – текущее внутреннее состояние автомата .

Выходы:

1) двоичное слово – выходной сигнал автомата , который реализуется по формулам (3);

2) двоичное слово , которое поступает на входы триггеров в запоминающей части и управляет памятью автомата.

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

В каждый момент времени сигналы управления памятью должны переводить автомат из состояния в состояние . Для этого надо изменить состояние каждого триггера

, .

Используемые в канонической схеме -триггеры или -триггеры обладают следующим свойством: для любой пары состояний существует входной сигнал, переводящий автомат из состояния в состояние . Обозначим этот сигнал через . Для -триггера , так как состояние, в которое устанавливается -триггер, равно входному сигналу. Для -триггера : при на вход надо подать 0, чтобы состояние не изменилось; при – 1, чтобы триггер «перевернулся».

Итак, , или в векторной форме

.

Выразим из закона функционирования автомата (2). Тогда

.

Теорема доказана.