Проблема синхронизации расстрельной команды — это проблема в информатике и клеточных автоматах , в которой цель состоит в том, чтобы спроектировать клеточный автомат , который, начиная с одной активной клетки, в конечном итоге достигает состояния, в котором все клетки одновременно активны. Впервые она была предложена Джоном Майхиллом в 1957 году и опубликована (с решением Джона Маккарти и Марвина Мински ) в 1962 году Эдвардом Ф. Муром .
Название задачи происходит от аналогии с реальными расстрельными командами : цель состоит в том, чтобы разработать систему правил, в соответствии с которыми офицер может отдать приказ расстрельной команде стрелять так, чтобы ее члены выстрелили из своих винтовок одновременно.
Более формально, проблема касается клеточных автоматов , массивов конечных автоматов, называемых «ячейками», расположенных в линию, так что на каждом временном шаге каждая машина переходит в новое состояние как функцию своего предыдущего состояния и состояний двух своих соседей в линии. Для задачи расстрельной команды линия состоит из конечного числа ячеек, и правило, согласно которому каждая машина переходит в следующее состояние, должно быть одинаковым для всех ячеек внутри линии, но функции перехода двух конечных точек линии могут различаться, поскольку у каждой из этих двух ячеек отсутствует сосед с одной из двух сторон.
Состояния каждой клетки включают три различных состояния: «активный», «покоящийся» и «активный», а функция перехода должна быть такой, чтобы клетка, которая находится в состоянии покоя и соседи которой находятся в состоянии покоя, оставались в состоянии покоя. Первоначально, в момент времени t = 0 , все состояния находятся в состоянии покоя, за исключением клетки в крайней левой точке (генеральной), которая активна. Цель состоит в том, чтобы разработать набор состояний и функцию перехода таким образом, чтобы независимо от длины линии клеток существовало время t , при котором каждая клетка переходит в состояние активации в момент времени t , и при этом ни одна клетка не находилась в состоянии активации до момента времени t .
Первое решение FSSP было найдено Джоном Маккарти и Марвином Мински и опубликовано в Sequential Machines by Moore . Их решение заключается в распространении двух волн вдоль линии солдат: быстрой волны и медленной волны, движущейся в три раза медленнее. Быстрая волна отражается от другого конца линии и встречается с медленной волной в центре. Затем две волны разделяются на четыре волны, быстрая и медленная волны движутся в обоих направлениях от центра, эффективно разделяя линию на две равные части. Этот процесс продолжается, подразделяя линию до тех пор, пока каждое деление не станет длиной 1. В этот момент каждый солдат стреляет. Это решение требует 3 n единиц времени для n солдат.
Решение, использующее минимальное количество времени (которое составляет 2 n − 2 единиц времени для n солдат), было впервые найдено Эйити Гото (1962), но его решение использовало тысячи состояний. Ваксман (1966) улучшил его до 16 состояний, а Бальцер (1967) дополнительно улучшил его до восьми состояний, заявив, что доказал, что не существует решения с четырьмя состояниями. Питер Сандерс позже обнаружил, что процедура поиска Бальцера была неполной, но сумел подтвердить результат несуществования с четырьмя состояниями с помощью исправленной процедуры поиска. Лучшее известное на данный момент решение, использующее шесть состояний, было предложено Жаком Мазойе (1987). До сих пор неизвестно, существует ли решение с пятью состояниями.
В решениях с минимальным временем генерал посылает направо сигналы S 1 , S 2 , S 3 , ..., S i со скоростями 1, 1/3, 1/7, ..., 1/(2 i −1 − 1) . Сигнал S 1 отражается на правом конце линии и встречается с сигналом S i (для i ≥ 2 ) в ячейке n /2 i −1 . Когда S 1 отражается, он также создает нового генерала на правом конце. Сигналы S i строятся с использованием вспомогательных сигналов, которые распространяются налево. Каждый второй раз, когда сигнал перемещается (направо), он посылает вспомогательный сигнал налево. S 1 перемещается сам по себе со скоростью 1, в то время как каждый из более медленных сигналов перемещается только тогда, когда получает вспомогательный сигнал.
Проблема синхронизации расстрельной команды была обобщена на многие другие типы клеточных автоматов, включая многомерные массивы клеток (Shinahr 1974). Также были рассмотрены варианты проблемы с различными начальными условиями (Kobayashi & Goldstein 2005).
Решения проблемы расстрельной команды также могут быть адаптированы к другим проблемам. Например, Патрик Фишер (1965) разработал алгоритм клеточного автомата для генерации простых чисел на основе более раннего решения проблемы синхронизации расстрельной команды.