No Such Blog or Diary

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

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

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

Leaf のゲームに XviD がリンクされており XviD がGPLなのでライセンスに違反しているらしい．誰が最初に見つけたのか知らんけど御苦労なことで．んで，GPL に従うならソース公開となるが， Leaf の回答 によるとその準備をしているらしい．準備だけで終わってしまう気もしないではないが，公開されるなら是非ほしいところ．それにしてもライセンス関係の問題って怖いなーと．自分でなんかソフト作る場合にはとにかく気をつけるとしよう．とはいえ仕事で作らない限りソースはオープンにするだろうけど．

シチューがおいしいかと思う今日この頃．あまり手間もかからないで楽だし．というわけでハウス食品の北海道シチューのルウで作りましたとさ．どのあたりが北海道なのかさっぱりわからなかったり．にんじんとたまねぎのみでジャガイモ入れなかったり．肉が面倒だからひき肉をトレイに入ってる形そのままで焼き固めてみたり．緑分が少ないなぁと思うけど面倒なので無視したり（ソラマメでも入れてみるか？）．どうでもいいけど，もう少し大きななべがほしい...

どうやら今日発売とのことだけど...　マイクロソフトのゲーム機ってすぐ止まりそうなイメージが．ついでに電力も最大時254Wで食いまくりだし．ACアダプタに冷却ファンが入ってるってのも微妙かと．この辺 PS3 も高性能で電力食うだろうけどその分省電力においても高性能であることを祈りたい...　それはさておき，店頭に並ぶ人の数も少ないのに７時から売り出す意味があったのだろうか？　なんとなく熱くない祭りだなぁと思ってみたり．

知らんかったのでメモ．

f(x) の antidifference g(x) は f(x) = g(x+1)-g(x) で定義される．この定義のもと f(x) の x = k, k+1, ..., k+n における和を考えると，ちょうど前後の g(x) が打ち消しあって始点と終点の g(x) の差になる．

f(k)+f(k+1)+f(k+2)+...+f(k+n) 
= g(k+1)-g(k)+g(k+2)-g(k+1)+g(k+3)-g(k+2)+...+g(k+n+1)-g(k+n) 
= g(k+n+1)-g(k)

まあ，g が f の積分と考えればそうだなと．んで，k の n 次多項式で， k^{n} = k * (k-1) * (k-2) * ... * (k-(n-1)) の形のものを factorial polynomial というらしく，この factorial polynomial k^{n} の antidifference は k^{n+1}/(n+1) になる．連続の場合の x^n の積分が x^{n+1}/(n+1) であることに対応すると．

で，これらの事実を使うと，適当な多項式 p(x) の和 S(n) = p(1) + ... + p(n) が簡単に求まると．これは，p(k) が m 次多項式であれば p(k) を k^{i} の線形和 p(k) = \sum_{i=0}^{m} a_i k^{i} であらわせて，その antidifference が P(k) = \sum_{i=0}^{m} a_i k^{i+1}/(i+1) となるので， あとは S(n) = p(1) + ... + p(n) = P(n+1) - P(1) で和が求められると．

大昔に i^2 の和が 1/6*(2n+1)*(n+1)*n だとか教えられた記憶が歩けど一般化した話は知らんかったので少々感動．

使い道のない知識だけど．