「再帰」の説明の一例(プログラミング初心者向け)

Twitterから参照するためのメモです)
まずそもそも「関数」は「同じ形の計算を何度も書かないための仕組み」であることを十分に理解する(させる)。その上で、

sum(0) = 0
sum(1) = 0+1
sum(2) = 0+1+2
sum(3) = 0+1+2+3
sum(4) = 0+1+2+3+4
...

も「同じ計算を何度も書いている」から、

sum(0) = 0
sum(1) = sum(0)+1
sum(2) = sum(1)+2
sum(3) = sum(2)+3
sum(4) = sum(3)+4
...

と書き換える。これを一般化すると

sum(0) = 0
sum(n) = sum(n-1)+n (n>0の場合)

つまり

sum(n) = if n=0 then 0 else sum(n-1)+n

となる

追記:n<0の場合は気にするな。

帰納法と余帰納法の何がどう双対なのか(初等的に)

(高校で習うはずの)数学的帰納法をはじめとする帰納法(induction)と、(π計算など並行プロセス計算に出てくる)双模倣(bisimulation)をはじめとする帰納法(coinduction)は、双対(dual)であると言われます()。双対というのは、大雑把に言うと、論理式のド・モルガンの法則 ¬(A∨B) ⇔ ¬A∧¬B と ¬(A∧B) ⇔ ¬A∨¬B のように、何か一組のもの(ここでは∧と∨)をひっくり返しても同じ式が成り立つという関係です()。

しかし、自分は学部4年ぐらいのときに余帰納法(というか双模倣)を習って、「(数学的帰納法のような)帰納法と(双模倣のような)余帰納法が双対」と聞いても、何となく「余帰納法は結論を仮定する(?)から、仮定を仮定する(?)帰納法と反対なのかなあ」と思うぐらいで、恥ずかしながら何が双対なのかよくわかりませんでした。かといって、詳しい人に「何が双対なんですか」と下手に聞くと、高い確率で「始代数と終余代数が…」みたいなカテゴリー理論的(?)説明をされてしまい、それはそれで面白いし落ち着いて確かめれば形式的には(=字面上は)意外と簡単(?)なのですが、(当時の)自分にとっては「数学的帰納法と双模倣の何が双対なのか」という素朴な疑問に対してピンと来る答にはなりませんでした。

仕方がないので(当時の)自分なりに思案した説明が以下です。教科書的定義から繰り返すと長くなってしまうので、単調関数の最小不動点と最大不動点がどうとかいうは知っているとします(詳しく知りたい人はTAPLの21.1節がわかりやすいと思います。その章の元になった論文の2節も、短いですが証明以外の大まかな内容はほぼ同じです)。すると、例えば自然数の集合Nは

  • 0∈X
  • ∀n.n∈X⇒n+1∈X

(の両方)を満たす最小の集合X、すなわち

  • F(X) = {0}∪{n+1 | n∈X}

なるFの最小不動点と定義されます。高校で習う(はずの)いわゆる数学的帰納法(すなわち自然数に関する帰納法)は、自然数に関する命題(すなわち自然数の集合)Pが

  • 0∈P
  • ∀n.n∈P⇒n+1∈P

(の両方)を満たせば∀n∈N.n∈Pを満たす、という(自然数の集合Nの)性質を利用した証明法です。これは論理的に

  • 集合PがP⊇F(P)を満たせばN⊆Pを満たす … (1)

と言いかえられるので、「NはX⊇F(X)を満たす最小の集合X」という自然数(の集合)の定義にも合います。

これに対し、余帰納法は、単調関数Fの最大不動点S(すなわちX⊆F(X)なる最大のX)に対し、

  • 集合RがR⊆F(R)を満たせばS⊇Rを満たす … (2)

という性質を利用した証明法です。具体例としては、プロセスの組の集合(すなわちプロセス上の二項関係)Xに対し

  • F(X) = {(p,q) | ∀p'.p→p'⇒∃q'.q→q'∧(p',q')∈X}

とすると、Fの最大不動点Sはプロセスの模倣性(similarity)関係になります(ただし、→はプロセスの遷移を表す二項関係で、ここでは詳しく定義しません)。これを用いて、例えばあるプロセスp1が別のプロセスq1を模倣(simulate)することを示したかったら、(p1,q1)∈RかつR⊆F(R)なるRを一つ「発見」する(ないし「構成」する)ことができれば、(2)よりS⊇Rなので、めでたく(p1,q1)∈Sが言えます。

(1)と(2)は見た目から明らかに「双対っぽい」ですし、教科書的説明に出てくる式ですが、それらの「使い方」も

  • 帰納法は「集合Pに対し、Fの最小不動点Nに属する任意の要素nが、Pに属する」ことを示したいときに使う … (1')
  • 帰納法は「集合Rに対し、Rに属する任意の要素(p,q)が、Fの最大不動点Sに属する」ことを示したいときに使う … (2')

と言えば「双対っぽい」感じになります(もちろん、(p,q)とかはあくまで例で、一般に組である必要はありません)。

細かい用語や記法は「いいかげん」ですし、すぐにわかる人には当たり前すぎる話かもしれませんが、(昔の)自分はすぐにわからなかったので、ひょっとしたら他人の参考になるかもしれないと思い恥を忍んで(?)久しぶりにエントリを書いてみました。最近の老化により記憶(と認知)が怪しい(笑)ので、何か大ボケ(ないし小ボケ)があったら是非ともご指摘ください。(_ _)

FLOPS 2010参加登録受付開始

遅くなりましたがFLOPS 2010の参加登録受付を開始しました。皆様よろしくお願いします。
http://www.kb.ecei.tohoku.ac.jp/flops2010/
ご質問や誤植などがありましたらコメント、Twitter、メールのいずれでも結構ですので是非ともお気軽にご連絡ください。

追記:FLOPS 2010は皆様(特にIFIP WG2.8関係者各位)のご厚意で、アイスランド火山噴火の影響によるプログラム変更はありますが開催できそうです。ヨーロッパからの招待講演者はむしろ増える(!)予定です。準備ができ次第、上述Webサイトと参加登録者各位へのBccメールでアナウンスします。

医療保険

契約している医療保険が値下げ(!)されて更新(解約&再契約)が必要になったので、この機会に考察してみました。プロや詳しい方のツッコミをお待ちしております。
まず、そもそも保険の目的は、(正確な比喩ではないかもしれませんが)「大数の法則」のように、多くの人が集まることにより、確率的事象の影響を予測しやすくすることです。例えば「百万分の一の確率で、一年後に十億円が必要になります。払えなかったら破産です」と言われたら、(普通の)個人では対処のしようがなく、「百万分の一の確率で一年後に破産する」しかありません。そこで、「今のうちに1,100円を払ってくれれば、一年後に十億円が必要になっても肩代わりします」という仕組みがあると助かります。それが保険です。(期待値との差の100円は手数料です。加入者が100万人だったら、一人100円×100万人=1億円が保険会社の収入になります。)
では、「入院1日目から、最大60日目まで、一日5千円を支払います」という保険と、「入院61日目から、最大1,000日目まで、一日1万円を支払います」という保険はどちらが得でしょうか。無論、前者は比較的高確率、後者は低確率の事象ですが、当然ながら保険料も確率に応じて(かなり正確に)決まっているので、「確率の高い出来事だから保険に入る」というのはナンセンスです。例えば、もし確率100%の事象だったら、明らかに自分で貯金したほうが(保険会社の手数料分だけ)得です。同様に、よほどのお金持ちか貯金不足で限り、「入院1日目から60日目まで」などという保険に意味は無く、むしろ確率は低いけれども損害が大きい「入院61日目から1,000日目まで」のような保険のほうが有用です。残念ながら現在のところ、日本の保険会社で後者のような医療保険は存在しない(?)ようですが…

追記:もちろん、高額療養費制度は存在しますが、現在の公的医療保険制度がいつまで存続するかわかりませんし、(現役の場合は)長期入院により収入が減少するリスクのほうが問題です。所得補償保険もありますが、逆選別のため(?)か、一般に割高のようです。最も悩ましいのは「入院」ではなく「療養」により収入がなくなるリスクで、良い案があったら教えてください。(自分の場合、「療養」できる状態ならば、無理すれば「就業」も可能かもしれませんが…)

「税金の無駄」について我々国民が肝に銘じておくべきこと

私は政治や財政の専門家でも何でもありませんが、最近の(特に一部のマスメディアやネット上の)議論では、あまりにも当然のことが無視されているように思うので、(こんなところで私が言っても意味がないことは承知で)陽に述べさせていただきたいと思います。

  • 大前提1:日本は国民主権の民主主義国家ですから、政治の最終責任はすべて国民にあります。「政治家」や、ましてや「官僚」のせいにすることは許されません。政治家は国民が選出した代表、官僚は国民が雇用している従業員に過ぎません。(「俺が儲からないのは従業員のせいだから従業員をクビにする。残ったやつはもっと働け。ただし給料は減らす。」なんて経営者は最悪ですよね?)
  • 大前提2:「税金」は「私たちがみんなで議論・合意して、お互いのために出し合うお金」です。

以上を踏まえ、常に意識すべきこと:

  • 私(あなた)はいくら税金を払っているか。普通のサラリーマンであれば、国の直接税(所得税)は、給与明細や源泉徴収票にはっきりと書いてあります。国の間接税(消費税)は、普通は4%です(1%は地方消費税)。(法人税なども何らかの意味で間接的には払っているはずですが、計算が難しそうです。良い計算方法があったら教えてください>詳しい方)
  • 私(あなた)はいくら税金を使っているか。これはさらに計算が難しいと思いますが(良い計算方法があったら教えてください)、意識することが重要です。例えば外を歩くだけでも道路や信号を使っているはずですし、息をするだけでも空気を浄化するために使用された税金を使っていることになります。ちなみに信号機は一基あたり数百万円〜一千万円ぐらいだそうです(もちろん機種や仕様によると思いますが)。
  • これらを考えた上で、「税金の無駄」があるとしたら、具体的にどれが無駄で、具体的にどうしたら削減できるのか(あるいはそもそも本当に無駄なのか)。大前提1・2で述べた通り、それを考えるのは我々国民であって、「政治家」や「官僚」に責任転嫁することは許されません。

繰り返しになりますが、私は専門家ではないので、専門家の方のご意見・ご指摘がありましたら是非とも宜しくお願い致します。(_ _)

追記:未成年者には選挙権がない、外国人は日本の総人口にカウントされているが日本国民ではない等々、多少の不正確さはご容赦ください。(指摘は歓迎します)

Microsoft Academic Search

またTwitterから転載します。(「はてな」と統一できればよいのですが、文字数制限が一番のネックです…)

  • Microsoft Academic Search ( http://academic.research.microsoft.com/ ) という、Google ScholarCiteseerのMS版があることを知った。
  • MS Academic Search、ちょっとデータが古い&論文のunificationが甘い? > http://academic.research.microsoft.com/Author/822441.aspx
  • 学会や論文誌についての統計(引用数など)は参考になる。> http://bit.ly/2VS5Z8
  • …というか研究「者」個人まで陽にランキングされてるのかー。これはきつい…(笑) > http://bit.ly/30GiSK
  • ふーむ、大学ランキング同様、多少の疑問はあるかもしれないが(全体を100として±5ぐらいの誤差?)、学会ランキングも人間ランキングもほぼ実感を反映している
  • 若輩としては、citations / publications ではなく citations / (publications * years) で計算してほしかったですが:-)
  • ちなみに人名からcitations / publicationsとかcit / (pub * years)とかcit / (pub * yrs * authors)とかを計算してくれるソフトウェアもあります。 > http://www.harzing.com/pop.htm
  • 多少の誤差はあっても大体は一致しているわけですから、人事(採用)では研究分野の好き嫌いとか知り合いとかではなく、こういう客観的指標をきちんと使用していただきたいものです。最近はやや減っているようですが、いまだに明らかに逆転しているケースが…
  • 文字数制限のせいで書き忘れましたが、MS Academic Searchの件は松岡さん(などと私がお呼びするのも失礼ですが)経由で知りました。> http://twilog.org/ProfMatsuoka#091102