キマイラ・サイトは http://www.chimaira.org/です。
トラックバック／コメントは日付を気にせずにどうぞ。
連絡は hiyama{at}chimaira{dot}org へ。
蒸し返し歓迎!
ところで、アーカイブってけっこう便利ですよ。タクソノミーも作成中。今は疲れるので作っていません。
2007-04-11 (水)
1+1ができない子と線形論理
雑記／備忘 | |
1+2と1+1
森毅さんが書いていたのだったかな？ 「1+2はできるが、1+1はできない子」の話を読んだことがあります。ちゃんとは憶えてないのですけど、だいたい次のようなことだったかと：
大人：まず1があるだろう。
子供：うん。
大人：そこに2を持ってきて。
子供：うん。
大人：一緒にしたらいくつだ？
子供：3
と、1+2=3はOK。
大人：まず1があるだろう。
子供：うん。
大人：そこにまた1を持ってきて。
子供：えっ、1はさっき持ってきちゃったから、もうないじゃん。
大人：別な1を持ってくる。
子供：別のだったら、1じゃないでしょ。
僕も似た感覚を持ったことがあるので、この子の発想は理解できます。計算結果を出す前に、計算式を組み立てるとして、そのとき、□+□ のようなテンプレートを考えましょう。また、このテンプレートとは別に、（一桁の数に限定して）1から9の数が書いてあるカードがそれぞれ1枚ずつ準備されているとします。
- テンプレート □+□ がある。
- カード[1]を持ってきて、最初の四角にはめ込んで 1+□。
- カード[2]を持ってきて、次の四角にはめ込んで 1+2。
この手順はOK。しかし、
- □+□ がある。
- カード[1]を持ってきて、最初の四角にはめ込んで 1+□。
- カード[1]を持ってきて、ってもう使っちゃってるから、できない。
カード[1]はすでに消費しちゃっているから、2回は使えないってわけです。
タプルの片一方を取り出す
今度はタプル（特にペアの場合ですけど）のテンプレート (□, □) を考えます。四角には、やはりカードをはめ込むとして、(1, 2)、(2, 1) などを作れます。各数値ごとのカードが1枚ずつだと (1, 1) は作れません。（同じ数のカードがイッパイあることにすれば、(1, 1)も作れます。）
さて、タプル（ペア）(1, 2)の一番目を取り外すと (□, 2)です。手元には数値のカード[1]があります。この操作は、タプルの第1成分を取り出す射影（projection）と呼ばれるものです。ここで問題は、残っている(□, 2)のほうです。これにはカード[2]が1枚はめ込まれたままになっていますが、どうしたものでしょう？ 普通は気にしない、つまり、残ったカードとテンプレートを捨ててしまいます。最終結果は手元のカード[1]だけです。
もし、「空っぽのテンプレートは捨ててもいいが、カードが1枚でも入っているテンプレートは捨ててはいけない」という規則があると、(1, 2)を[1]と(□, 2)に分けることはできても、[1]だけを単独で取り出すことはできません。
リソースに敏感になる
いま問題にしているのは、
- 数値のカードを素材にして、式1+2とかタプル(1, 2)を作ること
- 逆に、組み立てた式やタプルから素材を取り出すこと
です。通常は意識してないのですが、式やタプルを自由に組み立てるには素材のカードを複製（コピー、クローン）する必要があります。そうでないと、1+1も(1, 1)も作れません。それと、式やタプルの一部にだけ注目して取り出すには、取り出した部分以外を捨てる操作（破棄）も潜在的に行われています。
複製や破棄を明確に意識することは、数値や記号を物体のように扱うことです。物体の複製や破棄にはかならずコストが伴います。場合によっては、完全な複製を作ることや、迷惑をかけずに捨てる／破壊することは不可能かもしれません。
冒頭の「1+1ができない子」は、数値や記号を物体扱いするセンスを持っていたわけです。このようなセンスを、リソースに敏感（resource sensitive/aware）と呼びます。ここでリソースとは、数値や記号のような抽象的なモノを物体扱いした概念と思ってください。
コンピュータによる記憶や計算では、メモリ、ディスク、CPUなどの“リソース”が使用され、複製も破棄（ゴミ管理）もコストがかかるので、リソースに敏感な態度はコンピューティング・サイエンスでは自然ともいえます。
奇妙な論理と現象の世界
前節のタプル（ペア）の計算／処理では、次の図式で示される A → (A, A)、(A, B) → A という操作が（暗黙的である明示的であれ）使われていました。
A 素材 ----------------[重複タプルを作る] (A, A) タプル (A, B) タプル ----------------[第1成分を抜き出す] A 素材
論理の世界で似た操作は、次のものでしょう。ただし、AやBは数値や記号ではなくて、命題（論理式）です。
A 仮定 ---------- A∧A （AかつA） A∧B 仮定（AかつB） ----------- A
これは、「正しいことを（しつこくも）二度言っても正しい」、「2つとも正しいなら、そのうちの一方は正しい」ことなので、あきれるくらいに当たり前です。
にもかかわらず、リソースに敏感な態度をとると、命題（論理的な主張）もリソースと考えることになります。正しいことを言って、その影響が他に及んでしまうと二度目は言えないかもしれません。また、A∧B が正しいのは、あくまでも組み合わせとして正しくて、A, B単独で正しいことは保証されないかもしれません。
と、こう述べてみると、論理にリソースに敏感な態度を持ち込むのは異常なことに思えます。リソースに敏感な論理は線形論理（linear logic）と呼ぶので、この言葉を使えば、「線形論理は異常だ、奇妙だ、変態だ」というわけです。実際僕はそう思っていました。
しかし、先日の「ボブ・クックの『物理系実務者のための圏論入門』」で紹介した圏論的量子力学／量子情報学の基礎的前提を眺めていると、量子情報（量子的真偽値、量子的命題と言ってもいい）は完全に複製することも、破棄することも許されていません。これは、人為的な仮定ではなくて、物理的な法則がそうなっているようです。
となると、人間の論理（古典論理*1や直観論理）から見ていくら奇妙でも、自然現象の論理は線形論理になっていると認めざるをえないようです。
そして、計算現象の論理もどうも線形論理みたいなのです。その理由のひとつは、コンピュータによる計算が実際にリソースに敏感だとういうこと。また別な理由として、計算も結局は自然現象（物理現象）に支えられているという事実があるでしょう。手作業で行う計算でも、紙がなくなったり鉛筆が折れたら中断しちゃうし、やってる人間が疲労して間違ったりと、確かにリソースに敏感ですものね :-)
とまー、そんな事情で、線形論理を毛嫌いしているわけにもいかないのかなー、と思っているこの頃…
- http://d.hatena.ne.jp/m-hiyama/20070413
- http://d.hatena.ne.jp/lethevert/20070423
- http://d.hatena.ne.jp/m-hiyama/20070508
- http://d.hatena.ne.jp/propella/20070720
- 檜山正幸のキマイラ飼育記 - どこが面白いの？可逆計算 -- コンピュ...
- 檜山正幸のキマイラ飼育記 - カリー／ハワード（Curry-Howard）の対...
- 暗号、数学、時々プログラミング - というワケで、キマイラ飼育始め...
- 檜山正幸のキマイラ飼育記 - 圏のクリーネスター構成 もっと -- エ...
- 檜山正幸のキマイラ飼育記 - こんな簡単なトレース付きモノイド圏が...
- 檜山正幸のキマイラ飼育記 - こんな簡単なトレース付きモノイド圏が...
- Meta formalizer - 可逆計算やデータフローについての思考
- kencobaの日記 - #awodeytokyo 読書会記録6月
- miura1729の日記 - GC撲滅への道 - GC Advent Calendar
- 438 http://d.hatena.ne.jp/
- 235 http://ja.reddit.com/
- 180 http://b.hatena.ne.jp/entrylist?sort=hot
- 148 http://b.hatena.ne.jp/
- 148 http://reader.livedoor.com/reader/
- 114 http://d.hatena.ne.jp/miura1729/20121205/1354633325
- 97 http://b.hatena.ne.jp/entry/http://d.hatena.ne.jp/m-hiyama/20070411/1176255532
- 93 http://www.google.co.jp/search?q=線形論理&ie=utf-8&oe=utf-8&aq=t&rls=org.mozilla:en-US:official&client=firefox-a
- 74 https://www.google.co.jp/
- 56 http://www.google.com/reader/view/
...と、こう述べてみると、論理にリリースに
本質的でないことですみません。リリースが混じっているような気がするんですが。
＞ リリースが混じっているような気がするんですが。
ソフトウェアだと、リリースにも敏感になりますからね。
いやっ、実は単なる間違い。直します。ご指摘ありがとうございます。
> もし、「空っぽのテンプレートは捨ててもいいが、カードが1枚でも入っているテンプレートは捨ててはいけない」という規則があると、(1, 2)を[1]と(□, 2)に分けることはできても、[1]だけを単独で取り出すことはできません。
子供じみた意見となりますが、(1, 2)を[1]と(□, 2)に分けた時点で[1]を取り出せています。(□, 2)が問題なら、その後、[1]を複製し、元の[1]を(□, 2)に戻すか、または、残った(□, 2)から更に2を取り出し、空っぽとなったテンプレートを捨ててしまえば、(□, 2)が片付けられます。
簡単申込はこちらhttp://www.ganzis.jp/japanese/bl/pe_apply.php
また僕の所にコメントするなんて、ganzisはうまくいってないのですか？ 全然儲かってないのですか？ あまりに出来が悪くツマラナイので誰も見向きもしてくれなくて窮地に陥っているのですか？ そうですか、心配です。がんばってください。
＞子供：えっ、1はさっき持ってきちゃったから、もうないじゃん。
＞大人：別な1を持ってくる
思いっきりはずれますが。（「印象」コメントというもの？？）
最近読んでいた、熊野純彦の「西洋哲学史」（上、岩波新書）を思い出しました。
”１に１を加えると２になるが、２になったのは加えたほうの１なのか、別の１なのか”
と、かのプラトンさんは問うたそうです。（p.148）さらに１に１を加えることに不審の念を表しているとか。
子どもの言葉も後になると深い。（直面している学習にはジャマになるけど）
＞ ”１に１を加えると２になるが、２になったのは加えたほうの１なのか、別の１なのか”
これは現在でも意味のある問題提起ですね。「演算+が、対等な二項演算なのか、左からの作用なのか、右からの作用なのか？」という再解釈もできるでしょう。その解答の一部は、群やモノイドとその作用、等質空間、スカラー乗法なら左加群と右加群の区別とかで与えられるかもしれません。
＞ 子どもの言葉も後になると深い。
とんでもなく本質的だったり深遠なことを言うときがありますよ、実際。
あの質問に答えて説明をすると長くなりそうです。エントリーを起こすことにしました。
「リソースに敏感」というのは
「1+2=3」という文章に疑問をもつことみたいなもの、
と解釈してよろしいでしょうか？
小さい頃「1たす2は3（にひとしい）」
というのを知った時に
（なんでひだりがわはかんたんにしなきゃいけないんだろう？）
と思ってて
「1+2＝2+1＝1+1+1」
という遊びをしてました。
その上で
「1+2＝3」は「Q.1+2 A.3」
のことだと思ってました。
線形論理のことはわかりませんがそういうことと似てるような・・・
間違ってたらすいません。
まず「リソースに敏感」の意味ですが、計算や証明のような作業過程において、事前に与えられた数、記号、命題のようなモノも物質扱いすることです。逆に物質的でない扱いとは：
1. 作業過程で必要なら、いくらでも複製してよい。
2. 作業過程で使わなかったものは捨てて（あるいは無視して）よい。
複製／破棄を許さない、あるいはそれなりのコストを要求するのが「リソースに敏感」な態度です。
例えば、f(x, y, z) := x*x + y*y という関数定義で、記号としてのxを2回、yも2回使っています。しかしzは使ってません。記号の複製／破棄を許さないなら、この関数は定義できません。関数をハードウェア回路で実装するとして、x, y, zを入力信号線と考えると、x→x, x（出力線は2本）、y→y, y という信号複製器（duplicator）、z→放電 という放電器（discharger）が必要です。複製／放電は、電力を要求し発熱を伴うでしょう。エネルギー・環境問題の見地からタダじゃないんです！ g(x1, x2, y1, y2) := x1*x2 + y1*y2 なら複製／破棄なしの定義です。
＞ 「1+2＝3」は「Q.1+2 A.3」のことだと思ってました。
これは別な論点なんですが、重要な指摘です。記号「=」の意味は、等式命題としての宣言・記述以外に、左から右への書き換え／簡約／変形などを表すことがあります。前者の意味なら 3 = 1 + 2 もOKですが、後者の意味なら 1 + 2 = 3 はいいけど 3 = 1 + 2 はダメです。
僕の記憶やウチの子供の様子から、算数の「=」は、質問と回答の区切り、あるいは、作業のbefore/afterの区切りのようで、書き換えの意味が強いようです。
（記号 z は一応、定義内には存在しますが。。）
とすると、f(0, 0, 0)は全てを破棄することになりますか。
思いつきの質問ばかりですいませんが、気がむいたときご回答頂ければ十分です。
＞ x * x + y * y + z * 0 はzを破棄していることと同等ですか。
同等です。足し算／掛け算や定数を組み合わせれば、出力結果としては破棄と同じ効果を出せます。ですが、演算や定数の組み合わせは以前からコストとして意識されていたものです。リソースに敏感とは、以前はタダだと思われていたものにもコスト意識を持つことです。
＞ f(0, 0, 0)は全てを破棄することになりますか。
なりません。回路の例えだと、3本の入力線にたまたま同じ信号(0を表す）が入って、内部で演算器も動いて、たまたま0が出力されるだけのことです。入力をすべて捨てる関数は f(x, y, z) := c です（定数cは何でもいい）。このとき、x, y, zの放電（信号を安全に消滅させる）と定数cの発生にコストがかかります。
カードが1枚でも入っているテンプレートを破棄できない場合、以下の仕組みを作ることは可能だが、
([1],[2}) → [1], (□,[2])
([1],[2}) → [1], ([1],[2])
([1],[2}) → [1], [2]
しかし、単独で[1]を取り出す、
([1],[2}) → [1]
は不可能ということですね。きっと。
作業をテーブルの上で行うとして、「テーブルの上のモノは捨てない限りは残る」と考えてください。最後にテーブルの上に残ったモノが処理／演算の結果です。何も捨てずに (1, 2)→[1] は無理なんです。
> SKIコンビネーターのSが複製，Kが破棄を行っていますね。
比較的最近（2011-06-03）書いたエントリー http://d.hatena.ne.jp/m-hiyama/20110603/1307062942 でも釘と紐の絵を描いておいたのですが、「何もしない、複製する（複数回使う）、捨てる（1回も使わない）、入れ換える（役割の交換）」といった操作が、計算を支える根源的な操作のような気がします。
命題を物体のように扱ってリソースに敏感な態度をとると、
A∧(B∨C)と(A∧B)∨(A∧C)は異なる論理式として扱われる（分配律が不成立）のでしょうか。
応答が遅くなりました。ごめんなさい。
リソース敏感であっても、必ずしも分配法則を否定する必要はないと思います。A→A∧Aなどを認めないことと、分配律を両立させることもたぶん可能でしょう。
通常の分配律は採用せずに、弱分配律とか線形分配律とか呼ばれる法則を使う例はあります。