사격부 동기화 문제

총살단 동기화 문제는 컴퓨터 과학과 세포 자동화에 있어서 하나의 활성 세포에서 시작하여 결국 모든 세포가 동시에 활동하는 상태에 도달하는 세포 자동화를 설계하는 것이 목표인 문제다.1957년 존 마이힐에 의해 처음 제안되었고, 1962년 에드워드 무어에 의해 (존 매카시와 마빈 민스키의 해결책으로) 출판되었다.

문제명세서

문제의 명칭은 실제 총살단과 유사하게 만들어졌는데, 그 목표는 장교가 처형 세부사항을 명령하여 총기를 동시에 발사할 수 있는 규칙 체계를 설계하는 것이다.

좀 더 공식적으로, 문제는 셀 오토마타, 즉 "셀"이라고 불리는 유한 상태 기계들의 배열과 관련된 것으로서, 각 기계들이 그 줄에 있는 이전의 상태와 그것의 두 이웃의 상태의 함수로서 새로운 상태로 전환된다.사격대 문제의 경우, 선은 한정된 수의 셀로 구성되며, 각 기계가 다음 상태로 전환되는 규칙은 선 내부의 모든 셀에 대해 동일해야 하지만, 이 두 개의 셀이 각각 이웃을 놓치고 있기 때문에 선의 두 끝점의 전환 기능은 다를 수 있다.그들 쌍방의 한 쪽

각 셀의 상태는 "활성", "쿼터스", "발화"의 세 가지 구별되는 상태를 포함하며, 전환 기능은 대기 중이고 이웃이 대기 중인 셀이 대기 상태를 유지하도록 해야 한다.초기에는 t = 0으로, 활성 상태인 맨 왼쪽(일반)의 셀을 제외한 모든 상태가 대기 상태가 된다.목표는 셀의 줄이 아무리 길어도 모든 셀이 시간 t의 발화 상태로 전환되는 시간 t가 존재하고 시간 t 이전의 발화 상태에 속하지 않는 시간 t가 존재하도록 상태 집합과 전환 기능을 설계하는 것이다.

해결 방법

금감원에 대한 첫 번째 해결책은 존 매카시와 마빈 민스키에 의해 발견되었고 무어에 의해 순차 기계로 출판되었다.그들의 해결책은 빠른 파도와 느린 파도의 세 배 느리게 움직이는 두 개의 파도를 병사들에게 전파하는 것을 포함한다.빠른 파도는 줄의 반대쪽 끝에서 튕겨져 나와 중앙에서 느린 파도와 만난다.그 후 두 파도는 네 파도로 갈라졌는데, 이 파장은 중심에서 어느 방향으로든 빠르고 느린 파도로 이동하며, 사실상 선을 두 개의 동등한 부분으로 나누었다.이 과정은 계속되며 각 구획이 길이 1이 될 때까지 선을 세분화한다.이 순간, 모든 군인들이 발포한다.이 해결책은 n명의 병사들에게 3n 단위의 시간이 필요하다.

최소한의 시간(n 병사의 2n - 2단위)을 사용하는 해법은 고토 에이이치(1962)에 의해 처음 발견되었지만, 그의 해법은 수천 개의 주를 사용했다.벅스만(1966)은 이를 16개 주로 개선했고, 발저(1967)는 이를 8개 주로 추가 개선하면서 4개 국가 해법이 존재하지 않는다는 것을 증명한다고 주장했다.피터 샌더스는 이후 발저의 검색 절차가 불완전하다는 것을 알게 되었지만, 수정된 검색 절차를 통해 간신히 4개 주의 비존재 결과를 재확인했다.현재 6개 주를 사용하는 가장 잘 알려진 해결책은 자크 마조이어(1987년)에 의해 소개되었다.5대 국가 해법이 존재하는지 여부는 아직 알 수 없다.

최소 시간 솔루션에서, 일반은 속도 1, 1/3, 1/7, ..., 1/2 ⁱ⁻¹(2 - 1)에서 올바른 신호 S₁, S₃, ..., S로_2i 송신한다.신호 S는₁ 선의 오른쪽 끝에서 반사되며, n/2 ⁱ⁻¹ 셀에서 신호_i S (i ≥ 2)를 충족한다.S가₁ 반성을 하면 오른쪽 끝에 새로운 장군을 만들어 내기도 한다.신호 S는_i 왼쪽으로 전파되는 보조 신호를 사용하여 구성된다.신호가 오른쪽으로 움직일 때마다 보조 신호를 왼쪽으로 보낸다.S는₁ 속도 1에서 스스로 움직이는 반면 각각의 느린 신호는 보조 신호를 받아야만 움직인다.

일반화

총살단 동기화 문제는 고차원적인 세포배열을 포함한 많은 다른 유형의 세포 자동화로 일반화되었다(Sinahr 1974).초기 조건이 다른 문제의 변형도 고려되었다(코바야시 & 골드스타인 2005).

총살 문제에 대한 해결책도 다른 문제들에 적응될 수 있다.예를 들어, 패트릭 피셔(1965)는 사격부 동기화 문제에 대한 초기 해결책에 기초하여 프라임 숫자를 생성하기 위해 세포 자동 알고리즘을 설계했다.

참조

• Balzer, Robert (1967), "An 8-state minimal time solution to the firing squad synchronization problem", Information and Control, 10 (1): 22–42, doi:10.1016/S0019-9958(67)90032-0.
• Fischer, Patrick C. (1965), "Generation of primes by a one-dimensional real-time iterative array", Journal of the ACM, 12 (3): 388–394, doi:10.1145/321281.321290.
• Goto, Eiichi (1962), A minimal time solution of the firing squad problem, Dittoed course notes for Applied Mathematics 298, Cambridge, MA: Harvard University, pp. 52–59. Waksman(1966년)이 인용한 바와 같다.
• Kobayashi, Kojiro; Goldstein, Darin (2005), "On formulations of firing squad synchronization problems", Unconventional Computation (PDF), Lecture Notes in Computer Science, vol. 3699, Springer-Verlag, pp. 157–168, doi:10.1007/11560319_15.
• Mazoyer, Jacques (1987), "A six-state minimal time solution to the firing squad synchronization problem", Theoretical Computer Science, 50 (2): 183–238, doi:10.1016/0304-3975(87)90124-1.
• Moore, F. R.; Langdon, G. G. (1968), "A generalized firing squad problem", Information and Control, 12 (3): 212–220, doi:10.1016/S0019-9958(68)90309-4.
• Shinahr, Ilka (1974), "Two- and three-dimensional firing-squad synchronization problem", Information and Control, 24 (2): 163–180, doi:10.1016/S0019-9958(74)80055-0.
• Waksman, Abraham (1966), "An optimum solution to the firing squad synchronization problem", Information and Control, 9 (1): 66–78, doi:10.1016/S0019-9958(66)90110-0.

외부 링크

• Weisstein, Eric W. "Firing Squad Problem". MathWorld.
• 솔루션 중 하나에 대한 시각화 및 설명.