задача синхронизации стрелков

Зада́ча синхрониза́ции стрелко́в — задача из области информатики и теории клеточных автоматов. Впервые предложенная Джоном Майхиллом в 1957 году и опубликованная (с решением) в 1962 году Эдвардом Муром. Название связано с поведением солдат при расстреле или ружейном салюте — все солдаты стреляют одновременно по сигналу. Формулируется следующим образом: можно ли так запрограммировать одномерный клеточный автомат конечной длины, чтобы из стартового состояния G●●…●●● все клетки одновременно перешли в состояние FFF…FFF, независимо от длины цепочки, если обязательно правило перехода ●●●→● и его аналоги для концов цепочки ⌀●●→●, ●●⌀→●? Простым языком: * роботов (конечных автоматов) с ружьями стоят шеренгой. У автоматов как минимум три состояния ●, G и F — «исходное», «командир» и «выстрел». Помимо этих трёх, можно добавить сколько угодно промежуточных состояний. * Роботы действуют независимо по одной программе и общаются только по цепочке: по сигналам барабана (синхронизатора) в зависимости от своего состояния в момент и состояния двух соседей переходят в новое состояние. Исключение — крайние роботы, у которых только один сосед; у них собственные программы. * Все три программы, если робот и его соседи в исходном состоянии, ничего не должны делать. * Все роботы стоят в исходном состоянии и ничего не делают. В момент крайнего левого переводят в состояние «командир». * Существуют ли такие три программы (набор состояний и три комплекта правил перехода — для командира, замыкающего и остальных роботов), чтобы при любом они одновременно (на одном ударе барабана) перешли в состояние «выстрел»? Поскольку сигнал распространяется по шеренге со скоростью 1 позиция за такт (в теории клеточных автоматов это называется «скорость света»), очевидно, время синхронизации будет возрастать с возрастанием .