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

Зада́ча синхрониза́ции стрелко́в — задача из области информатики и теории клеточных автоматов.

Впервые предложена Джоном Майхиллом в 1957 году и опубликована (с решением) в 1962 году Эдвардом Муром. Название связано с поведением солдат при расстреле или ружейном салюте — все солдаты стреляют одновременно по сигналу.

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

Поскольку сигнал распространяется по шеренге со скоростью 1 позиция за такт (в теории клеточных автоматов это называется «скорость света»), очевидно, время синхронизации будет возрастать с возрастанием .

История 

Первое решение этой задачи было найдено Джоном Маккарти и Марвином Мински и было опубликовано в Sequential Machines Эдвардом Муром.

Решение, требующее минимальное время, было найдено в 1962 профессором Эйити Гото из МТИ. Оно использует несколько тысяч состояний и требует ровно  единиц времени для  роботов. Легко доказывается (см. ниже), что более эффективных по времени решений не существует.

Оптимальное решение, использующее всего шесть состояний (включая конечное «выстрел»), было найдено Жаком Мазойером в 1987 году. Ранее Роберт Бальцер компьютерным перебором доказал, что решений с четырьмя состояниями клеток не существует. Питер Сандерс позднее выяснил, что поисковая процедура Бальцера была неполной, однако исправив процедуру, получил тот же результат. В 2010-е эволюционным перебором получены сотни разных решений с шестью состояниями. До сих пор неизвестно, существует ли решение с пятью состояниями клеток.

Также пытаются побить рекорд по количеству задействованных правил перехода (включая требуемое, но неиспользуемое правило для командира ⌀●●→●. В решении Мазойера 119 правил. Существует неоптимальное по времени решение с шестью состояниями и 78-ю правилами, и оптимальное — с 80-ю.

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

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

Решение, требующее минимального времени 
Здесь описано достаточно простое решение из 16 состояний, описанное Абрахамом Ваксманом в 1966 году. Командир посылает соседнему роботу сигналы  с частотами  Сигнал  отражается от правого края ряда и встречает сигнал  (для ) в ячейке  Когда  отражается, он также создает нового командира на правом конце.

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

Доказательство минимального времени 

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

Любой сигнал проходит от робота к роботу не быстрее, чем с так называемой «скоростью света» — 1 позиция за шаг времени. Действия первого робота в момент  зависят от первых двух роботов на момент , от первых трёх на момент , …, от всех  роботов на момент . В этот момент последний робот всё ещё в исходном состоянии (сигнал к нему приходит к моменту ).

А значит, если добавить к правому концу ещё -х роботов, в момент  состояние первых  роботов будет таким же, для первого робота ничего не изменится, и он выстрелит на том же шаге . Последний -й на шаге  останется в исходном состоянии — до него сигнал не успеет дойти. Так что данная тройка программ — не решение. Противоречие.

Точно так же доказывается и другая нижняя грань,  шагов, но число  не меньше.

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

Обобщения 
Было предложено и изучено несколько более общих формулировок задачи, включая ряды с произвольным расположением командира, замкнутые кольца, квадраты, кубы, графы Кэли и графы общего вида.

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

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

Примечания

Литература

Ссылки 
 «Firing Squad Problem»
 «On Formulations of Firing Squad Synchronization Problems»
 «Firing squad synchronization»

Клеточные автоматы