檜山正幸のキマイラ飼育記 このページをアンテナに追加 RSSフィード Twitter

キマイラ・サイトは http://www.chimaira.org/です。
トラックバック/コメントは日付を気にせずにどうぞ。
連絡は hiyama{at}chimaira{dot}org へ。
蒸し返し歓迎!
このブログの更新は、Twitterアカウント @m_hiyama で通知されます。
Follow @m_hiyama
ところで、アーカイブってけっこう便利ですよ。

2012-03-23 (金)

スノーグローブ現象 再び

| 18:02 | スノーグローブ現象 再びを含むブックマーク

僕は「スノーグローブ」という言葉を気に入ってましてよく使ってますが、もともとはジョン・バエズ(John Baez)が説明のために持ちだした比喩です。次の絵もバエズから拝借。

見ればわかるように、ガラス玉のなかに箱庭の世界が閉じ込められています。圏論の言葉ではデカルト閉構造(より一般にはモノイド閉構造)のことで、世界全体がある対象の内部に反映される現象です。

このブログで「スノーグローブ」という言葉を最初に出したのは2007年夏ですね。

このテの現象を僕が偏愛していることは、次の記事とそこからのリンクを。

コンピュータとかプログラミング言語の文脈だと再帰構造とかメタ巡回(メタ循環;meta-circlular)構造とか言います。自己言及の構造ともいえますが、なんか哲学っぽくなるのでちょとイヤ。やっぱり「スノーグローブ」って言葉がいいな。

で、最近またスノーグローブ現象をマジメに取り上げたい動機があるので、その仕掛けを以下にざっと説明します。

メタ巡回構造

Cデカルト閉だとしましょう。完全な閉構造を持たなくてもいいのですが(部分閉構造でOK)デカルト閉圏のほうが話が簡単なのでそう仮定します。XとYの指数は YX と書くのが多数派ですが、面倒だから [X->Y] とします。[X, Y] という書き方もよく見ますが、タプル/リストと見間違えるのと、非対称モノイド圏のときに左右の区別がしにくいので、[X->Y] または [Y<-X] を使います。

デカルト閉圏Cの対象Dがメタ巡回構造を持つとは、Dから見て高階な(メタな)存在物Hが、H⊆D とみなせることです。とはいっても、「高階な存在物」の意味がハッキリしないし、圏のなかで包含「⊆」は(通常は)無意味です。もう少し明確にします。

高階な存在物の典型として [D->D] を取ります。これは指数なので、デカルト閉なCのなかで意味を持ちます。[D->D]⊆D の意味は、[D->D] からDへの埋め込み(embedding)があることです。埋め込みとはモノ射のことだと思っていいですが、ときにEPペア(embedding-projection pair)も使います。EPペアとは、モノ射 e:[D->D]→D とエピ射 p:D→[D->D] の組で、e;p = id[D->D] となるものです。

[D->D]⊆D となるモデルの嚆矢<こうし>は、スコットのPωモデル(自然数のベキ集合モデル)で、DがPωで、[Pω->Pω]はPω上の計算可能な部分関数の集合です。自明な例でもいいなら、集合圏Setのなかで単元集合Dは、[D->D]=D となる対象です。

Ω = {true, false} を古典論理の真偽値の集合とすると、たいていの場合はΩをデータ領域Dに埋め込めます。Ω⊆D と考えると、[D->Ω]⊆[D->D] となります。もちろん、必要があれば「⊆」は圏論的に解釈してください。[D->Ω] はデータ領域D上で定義された真偽値を取る関数(または部分関数)です。部分集合とその特性関数(characteristic function)との対応から、[D->Ω] = Pow(D) = (Dのベキ集合)とみなしてかまいません。つまり、[D->D]⊆D ならば Pow(D)⊆D も言えます。

デカルト閉圏CのなかでDがメタ巡回構造を持つなら、ベキ集合Pow(D)を自分のなかに包含することができるわけですね。A∈Pow(D) ⇔ A⊆D ですから、Pow(D)⊆D と組み合わせると A∈D となり、A⊆D ⇒ A∈D が言えます。なんか変な感じでしょう。変な感じがする理由は2つあって:

  1. 記号を乱用しているから。
  2. そもそもメタ巡回構造というものは不思議な感じがする。

e:Pow(D)→D をメタ巡回構造を構成する埋め込みとしましょう。記号の乱用を少しつつしんで、「A⊆D ⇒ A∈D」を埋め込みeを明示的に使って書きなおせば「A⊆D ⇒ e(A)∈D」となります。Pow(D)の要素は、Dの部分集合なので、Sets-as-Typesの立場では「型」ということになります。つまり、eにより、型がデータ領域のインスタンスとして表現されていることになります。

さらに、[D->D]⊆D を実現する埋め込みを使えば、DからDへの関数がデータ領域Dのインスタンスとなるので、「プログラムはデータなり」というノイマン型コンピュータの原理を表していることになります。ここらへんのことは何度も書いたことがあるので、これくらいにします。

万能対象とスノーグローブ現象

[D->D]⊆D となるようなDとしては、先に例に出した集合圏の単元集合のような小さなものもあります。Dがあまりに小さいと、世界全体(外の圏C)を映し出す(あるいは閉じ込める)ことはできません。

Cの対象Uが万能(または普遍的)とは、Cの任意の対象Xに対して、X→U という埋め込みがあることです。埋め込みの定義は、先に言ったようにモノ射でいいときもあればEPペアにすべきときもあります。Cの部分圏として埋め込みの圏を指定することもありますね。

対象Xごとに、埋め込み X→U の選び方は色々あるでしょうが、話を簡単にするために、Xごとに埋め込み eX:X→U を割り当ててしまってもいいでしょう。割り当てる手段があるのか? と聞かれると困りますが、Cがあまり大きくないなら具体的な割り当てを構成できるかもしれません。計算科学で出てくる圏はあまり大きくないから出来るかも? そもそも、圏Cが大きすぎると万能対象Uは存在できません。

さて、Uが万能対象であり、しかもメタ巡回構造を持っているとします。Uが万能ということは、世界(圏C)の任意の対象がUのなかに入ることを意味します。X, Y∈C に対して、ホムセットC(X, Y) は指数対象 [X->Y] で表現できます。もし [U->U]⊆U であれば、[X->Y]⊆U と出来て、Cの対象もホムセットもU内に埋め込めて、圏の構成要素である域/余域/結合などもU内で再現できます。

デカルト閉圏を扱った教科書のタグイには、このストーリーをちゃんと実行する手順が書かれています。僕の曖昧な記憶だと、一番面倒くさいのは、Xの埋め込みとYの埋め込みから X×Y(直積)の埋め込みを構成するところで、一回はやったことがありますが二度と出来ない気がします。ゴチャゴチャした計算を遂行するよりは、実用上は「X⊆U かつ Y⊆U ならば、X×Y⊆U」を仮定してしまっていいと思います。

そしてそれから

実は、スノーグローブの説明をするのが目的ではなくて、構文領域と意味領域の関係について整理したかったのです。エルブラン、リンデンバウム、タルスキー、それとコゥゼンあたりは、構文領域から意味領域を搾り出して標準モデルを作る方法を議論しています。構文領域でもあり意味領域でもあるような領域を取り扱うわけです。

こういう状況だと、記述や表現がそのままデータとなるので、メタ巡回構造/スノーグローブ現象が絡んできます。であるなら、スノーグローブ現象が起きる一般的機構もまとめておくほうがいいかな、と。書いてみたら(それが今回の記事)息切れした、と。

スノーグローブ現象が起きると、インスタンスレベルとメタレベルが混じり合うわけですが、エルブラン風のモデルの作り方をすると、さらに構文領域と意味領域も混じってきて、なんだか混沌としたスープ状の奇妙な構造物を相手にすることになります。奇妙と感じるのは我々に先入観があるからで、計算モデルの世界はそんなもんなのかも知れません。