帰納法と余帰納法の何がどう双対なのか（初等的に） - sumiiのブログ
（高校で習うはずの）数学的帰納法をはじめとする帰納法(induction)と、（π計算など並行プロセス計算に出てくる）双模倣(bisimulation)をはじめとする余帰納法(coinduction)は、双対(dual)であると言われます（例）。双対というのは、大雑把に言うと、論理式のド・モルガンの法則 ¬（A∨B） ⇔ ¬A∧¬B と ¬（A∧B） ⇔ ¬A∨¬B のように、何か一組のもの（ここでは∧と∨）をひっくり返しても同じ式が成り立つという関係です（例）。 しかし、自分は学部4年ぐらいのときに余帰納法（というか双模倣）を習って、「（数学的帰納法のような）帰納法と（双模倣のような）余帰納法が双対」と聞いても、何となく「余帰納法は結論を仮定する(?)から、仮定を仮定する(?)帰納法と反対なのかなあ」と思うぐらいで、恥ずかしながら何が双対なのかよくわかりませんでした。かといって、詳しい人
量子計算とプログラムの不動点意味論 - sumiiのブログ
http://alohakun.blog7.fc2.com/blog-entry-321.html 関数の情報がどんどん増えていって，その単調増加列 (近似) の極限 (という用語を使ってよいのか ? ですが) で，目的の関数 (最小不動点) に収束する，という概念が面白かった． せっかくなので反応しておくと、Keye Martinさんという人が2004年1月頃にPennへ来たときに 古典計算機では計算の反復ないし再帰の回数xは自然数で、xが増加すれば情報量も増加する。量子計算機では、xが実数や複素数になって「√ｎ回の反復」「ｉ回の再帰」などが実現でき、xと情報量との関係は放物線などになる。 みたいな不動点意味論の話をしていてビビリました。この↑説明はスーパー劣化コピーですが、talkのアナウンスから引用すると `Entropy' is to quantum state as `lengt
callccによる排中律の証明 - sumiiのブログ
Wadlerのパクリ。というか劣化コピー。 悪魔：「あなたが私と契約してくれたら、(A)『私があなたに一億円をあげる』、(B)『あなたが私に一億円をくれたら、どんな願いでもかなえてあげる』のどちらかをして差し上げます。(A)と(B)のどちらにするかは、私が決めます。」 人間：「どちらにせよ害はなさそうなので、じゃあ契約します。」 悪魔：「はい、では私は(B)を選びます。」 人間：「やっぱりそう来るか。でも一億円なんて持ってないし、まあいいや。」 （十年後） 人間：「気になってしょうがないので、悪いことをして一億円を集めました。だから願いをかなえてください。」 悪魔：「そりゃどうも（と一億円を受け取る）。では私は(A)を選びます。はいどうぞ（と一億円を返す）。」 ICFP 2003の会場ではWadlerとShiversが壇上で寸劇をやりました（本当）。λ式で書くと callcc(λk:¬(T
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
