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

Систематизировать знания и впервые представить системный обзор на русском языке поможет грант Российского фонда фундаментальных исследований.
В теории алгоритмов автоматом называется абстрактная математическая модель устройства, которое, принимая, преобразуя и передавая входящие сигналы, переходит из одного состояния в другое. Мысль о том, что автоматы функционируют не сами по себе, а под воздействием окружающей их среды, и что результат взаимодействия зависит как от изначального внутреннего состояния автомата, так и от сигналов, которые он получает извне, была выдвинута еще в далеком 1936 году британским математиком Аланом Тьюрингом в ставшей знаменитой статье «О вычислимых числах, с приложением к проблеме разрешимости». Революционность подхода Тьюринга заключалась в переносе на математические системы свойства организмов — реагировать в зависимости от внутреннего состояния и качеств внешних воздействий.
Открытия гениального британца полностью изменили нашу жизнь — положили начало программированию, создали условия для появления компьютеров, торговых автоматов, мобильных телефонов и других гаджетов. Все это — реализации в физических устройствах математической концепции автомата: кофейный автомат, когда мы выбираем и оплачиваем сорт напитка, последовательно переходит от состояния ожидания к состоянию приготовления и выдачи порции кофе; компьютер выходит из состояния ожидания, когда мы вводим слова на клавиатуре или щелкаем мышкой, и так далее.
«Мы знаем, что автомат может находиться в разных состояниях, но нам далеко не всегда известно, в каком конкретно состоянии находится тот или иной автомат. Как уменьшить или устранить эту неопределенность? Задачу решает синхронизация автоматов. Синхронизируемые автоматы — это математические или технические системы, которые исходя из своего внутреннего, скрытого от нас состояния переходят в новое, заранее известное нам состояние под воздействием набора наших сигналов», — описывает Михаил Волков.
По словам Волкова, в 1950-60-х годах такая задача стояла перед разработчиками искусственных спутников Луны. На время, когда спутник заходил в невидимую зону, связь с ним и контроль над его состоянием утрачивались. При появлении спутника было необходимо привести его в заранее известное состояние, синхронизировать, что и делалось с помощью сигналов с Земли.
В наше время синхронизация играет большую роль при тестировании протоколов передачи данных, в разработке и отладке электронных устройств, таких как мобильные телефоны. На этом участке науки заметный вклад принадлежит российским ученым, в том числе Михаилу Волкову и его воспитанникам. Волков — всемирно признанный научный авторитет, соавтор фундаментальной справочной книги по теории автоматов.
«Теория автоматов — одно из тех направлений, в которых наш университет занимает ведущие позиции. По данной тематике моими учениками и научными „внуками“ защищено около десятка диссертаций, — рассказывает Михаил Владимирович. — Например, очевидно, что эффективность синхронизации зависит от скорости операций. Недавно мой ученик, кандидат физико-математических наук Михаил Берлинков решил важную научную проблему, нетривиально доказав, что в среднем типичный автомат синхронизируется достаточно быстро. Это крупное достижение всего последнего десятилетия».
В настоящее время Михаил Волков работает над созданием обширного исторического обзора исследований, открытий и изобретений в области синхронизации конечных автоматов.
Проект Волкова, по итогам конкурса более чем 3,3 тысяч заявок, поддержан грантом Российского фонда фундаментальных исследований.