Задача синхронизации стрелков — задача из области информатики и клеточных автоматов, впервые предложенная Джоном Майхиллом в 1957 году и опубликованная (с решением) в 1962 году Эдвардом Муром^[1]. Формулируется следующим образом:

Рассмотрим конечное, но произвольное число конечных автоматов (стрелков), выстроенных в ряд. В момент времени t = 0 каждый солдат находится в исходном состоянии, за исключением самого левого солдата (командира). Состояние каждого солдата в момент времени t > 0 зависит от состояния его самого и двух его соседей в момент времени t − 1 (за исключением самых крайних солдат, у которых только один сосед). Если солдат и его соседи находятся в исходном состоянии, то в этом же состоянии они и остаются в следующие моменты времени. Задача заключается в том, чтобы найти конечный набор состояний и правил перехода между ними, которые допускали бы одновременный переход всех солдат в требуемое состояние (огонь).

История

Первое решение этой задачи было найдено Джоном Маккарти и Марвином Мински и было опубликовано в Sequential Machines Эдвардом Муром. Лучшее из известных решений, использующее шесть состояний, было найдено Жаком Мазойером в 1987 году^[2]. Ранее Роберт Бальцер доказал, что решений с четырьмя состояниями не существует^[3]. (Питер Сандерс позднее выяснил, что поисковая процедура Бальцера была неполной, однако исправив процедуру, получил тот же результат.) До сих пор неизвестно, существует ли решение с пятью состояниями.

Решение, требующее минимальное время, было найдено профессором Е. Гото из МТИ^[4]. Оно использует несколько тысяч состояний и требует ровно 2n − 2 единиц времени для n солдат. Доказано, что более эффективных по времени решений не существует.

Общее решение

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

Решение, требующее минимального времени

Оптимальное по времени решение впервые было описано в статье Waksman, 1966^[5]. Командир посылает крайнему солдату сигналы S₁, S₂, S₃, …, S_i с частотами 1, 1/3, 1/7, …, 1/(2 ⁱ⁻¹ − 1). Сигнал S₁ отражается от правого края ряда и встречает сигнал S_i (для i ≥ 2) в ячейке n/2 ⁱ⁻¹. Когда S₁ отражается, он также создает нового командира на правом конце.

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

Обобщения

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

Примечания