💸 Как сделать бизнес проще, а карман толще?

Тот, кто работает в сфере услуг, знает — без ведения записи клиентов никуда. Мало того, что нужно видеть свое раписание, но и напоминать клиентам о визитах тоже. Проблема в том, что средняя цена по рынку за такой сервис — 800 руб/мес или почти 15 000 руб за год. И это минимальный функционал. Нашли самый бюджетный и оптимальный вариант: сервис VisitTime.
⚡️ Для новых пользователей первый месяц бесплатно. А далее 290 руб/мес, это в 3 раза дешевле аналогов. За эту цену доступен весь функционал: напоминание о визитах, чаевые, предоплаты, общение с клиентами, переносы записей и так далее.
✅ Уйма гибких настроек, которые помогут вам зарабатывать больше и забыть про чувство «что-то мне нужно было сделать».
Сомневаетесь? нажмите на текст, запустите чат-бота и убедитесь во всем сами!

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

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

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

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

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

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

…

…

…

Рис. 6.

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

, …, ,

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

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

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

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

Выходы:

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

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

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

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

, .

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

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

.

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

.

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