クワインと対角化定理 ～計算理論入門～

はじめに

クワインとは

この前プログラミングの教科書を読んでいたら面白い問題があった。大雑把には次のような感じ。*1

自分自身のソースコードを出力するプログラムを書け。

調べてみたところクワインというらしい。細かい話をすると入力を受け取るのもダメだそうなので上の問題文よりは厳しい。詳しい話はWikipediaにある。
クワイン (プログラミング) - Wikipedia
結構難しいし、SchemeとかHaskellはまだしもCのやつとか何やってるのか初見じゃ意味不明。頭がこんがらがるのが味わえるのでぜひ考えてみて欲しい。

クワインと計算理論

ところで、計算理論をかじったことある人は「これ対角化して不動点つくればいいんじゃね？」と気がつくと思う。実際その方針でこの問題は解けるし、Cとかのわけ分からん例もこのことを理解してるとすんなり分かる。もろに理屈っぽい計算理論が割と身近に思えるクワインに応用できるのが面白い。

というわけでこの記事では計算理論を紹介しつつ、それを軸にクワインをどう作ったらいいか考えていく。計算理論は本当は厳密に理論展開されてるけれど、この記事ではフィーリングでやっていく。チューリングとか黎明期の人たちにとっては計算機は理論的な存在で、扱うのは大変だったんだろうと思うし、真面目にこの分野を研究とか勉強するならフィーリングで済ませるべきではないとは思う。だけど僕らは幸い生まれながらに計算機に親しんできた世代なので直感が使えるし、ちょっと計算理論をかじってみる分には十分だと思う。計算理論の楽しさとかクワインの作り方がわかってもらえれば幸いである。

*1:手元に本がないのでわからない

直積空間での境界作用素

A Concise Course in Algebraic Topologyのゼミ発表の準備をしてたら沼にはまった。13.4節のお話。

やりたいこと

を示す。

基本戦略

]
とするとは境界作用素と可換になる。はの次元。これより上の同型が従う。

やったこと

可換性を示すとき直積空間上での境界作用素を具体的に計算しなくちゃいけない。つらい。死んだ。初見だと2つの図式をどう使うのかすら分からなかった。

クソつらいけどtopological boundary mapの方の定義に従って座標入れて計算するだけ。答えがどうなって欲しいかは勘で分かるのでまだマシっぽい。もしかしたら座標入れないうまい方法があるかも知れない。写像度の計算の途中でホモトピー論のFreudenthal suspension theoremとか出て来て、この先ホモロジーとホモトピーの話の絡みがでてきそうだなあと感じてわくわくした。

おわりに

とてもつらかった。ホモロジーの定義ってめっちゃ綺麗だったわり計算しようと思うと牙を向くなあ...topological boundary mapは初め訳わからんと思ってたがこの計算する中で分かり合えた気がする。