- 2005-12-13 (Tue) 17:10
- アカデミック？
オートマトンの話が出たときにふと思い出したので．問題の確認をば．これは1957年頃に Myhill によって提起された問題で，内容は以下のとおり．
とりあえず兵士が一列に並んでいて，端以外の兵士は全部同じである．右端の兵士を将軍として，将軍が時刻 t = 0 に隣の兵士に射撃命令を下す．各兵士は有限の状態（記憶）を持っており，時刻 t における両隣の兵士の状態によって自身の時刻 t+1 の状態を決定する．ただし，初めは待機状態にいるものとする．これらの条件の下で，全兵士がある時刻 T において一斉にある特定の状態（射撃状態）に移行するように，兵士たちの状態遷移関数を構成せよ．
この問題の解は，兵士の人数を n とすると最小時間である 2n-2 （伝令が往復する）の解が存在し，87年に Mazoyer が 6 状態の最小時間解を与えている: Mazoyer. A six-state minimal time solution to the firing squad synchronization problem: Theoretical Computer Science, Vol. 50, Issue 2, pp. 183-238, 1987.
並列プロセッサの同期とか生物細胞の成長同期とかの応用問題があるらしい．
- Newer: PPoPP は Practice を結構重んじる