2005年12月13日

オートマトンの話が出たときにふと思い出したので．問題の確認をば．これは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.

並列プロセッサの同期とか生物細胞の成長同期とかの応用問題があるらしい．

研究室の電気ポットは内容器の汚れがひどく，ポンプの吸出しもいまひとつ．でもだーれも掃除しないので朝一で出かけてクエン酸洗浄を試みた．とはいえ，やったことはクエン酸溶かして沸騰させ数時間ほっといただけだけど．ただしその効果は思いのほか大きく，底面にこびりついていた汚れがきれいさっぱり．ついでにポンプの調子も良くなり，おまけにカスがお湯に混じってよく出るように...　あと数回沸騰出水を繰り返せば良くなるだろうけど．もう少しこまめに洗浄しましょう．それにしてもカテゴリよくわからん．黄色本の続きを読むか．