読者です 読者をやめる 読者になる 読者になる

いきるちから

気が向いたときに適当なことを書きます

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

はじめに

クワインとは

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

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

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

クワインと計算理論

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

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

不動点としてのクワイン

Churchのテーゼ

計算について考えようと思うと、まずは「計算可能」とは何かを考えなくてはいけない。この「定義」*2を与えるのがChurchのテーゼである。

Churchのテーゼ

関数  \mathbb{N}^m \rightarrow \mathbb{N} が計算可能とは、再帰的なことである。

フィーリングでやるといいながら早速つらい言明。ごめんなさい。

ここで主張したいことは2つに分けられる。まず「計算」とか「プログラム」といった考えたい対象を、自然数 \mathbb{N} 上の関数*3として理想化している。そうでもしないと数学的に扱えなくて面倒だから仕方がない。これは計算機の状態(メモリーとかHDDとか、CPUの状態とか)を自然数エンコードできる*4と考えれば、それほど危険なことは言っていないと思えると思う。

もう一つは、自然数上の関数のうち、再帰的なものを計算可能と呼ぼうということである。再帰的関数の定義はここでは扱わない。ここでは、自然数上の関数の部分集合として計算可能関数というものがあること、計算可能関数とは何となくC言語とかで実装できる関数っぽいくらいに思っておいてくれればいい。詳しくは次のリンクか教科書を読んでほしい。
μ再帰関数 - Wikipedia

この先では計算可能な関数のことをプログラムと呼んでいく。プログラムは自然数から自然数の関数だが、上のような説明の下では自然数(計算機の状態)を受け取って自然数(これも計算機の状態)を返す関数と考えられる。副作用を持つようなものもちゃんと含んでいるわけである。

万能プログラム

プログラムは再帰的関数だったのだから、引数が与えられると、値を返す。ところで、僕らがプログラムをつくるとき、普通はソースコードコンパイルする。ソースコードはプログラムの情報を全て含んでいて、実質的にプログラムと等価である。しかし、プログラムは自然数上の関数だったのに対し、ソースコードはただのデータ(自然数)である。計算可能なものに限れば、関数という扱いにくいものがただの自然数として扱いやすくなる。この話をまとめると次の定理が成立する。

計算可能関数の枚挙定理

自然数 e に対しプログラム  \{e\}  を対応させる関数 \{\} : \mathbb{N} \rightarrow (\mathbb{N} \rightarrow \mathbb{N}) が存在する。
全てのプログラム  p  に対し、ある  e \in \mathbb{N} が存在して、 p = \{e\} となる。
このような e のうち一つを選んで、  \lceil p \rceil と書く。

前半部はコンパイラがやっていることである。自然数ソースコード)にプログラムを対応させるのは、まさしくコンパイラの役割である。後半部は全てのプログラムは、何らかのソースコードで書けていると主張している。これにより、プログラムを考える代わりにソースコードについて考えていればいいことが保障される。関数の代わりに自然数についてだけ考えていればいいのである。後半の主張はそれほど自明じゃないけど、ここでは扱わない。*5

さらに、コンパイラ自身もプログラムなのだから、関数  \{\} 自体もプログラムになるのではと考えるのは自然である。実際次の定理が成立する。

万能プログラム

ソースコード e と入力  \vec{x} を受け取り、出力結果  \{e\}(\vec{x})  を返す「万能プログラム」  U  が存在する。
つまり計算可能関数  U  が存在して  U(e, x) = \{e\}(\vec{x})*6が成立する。

万能プログラム  Uソースコードと入力を受け取って、コンパイルと実行を同時にしてくれるプログラムである。この定理が現代の「ソースコードを書いてコンパイルすればいい」という万能計算機の存在を保証していて、僕らはプログラムごとに別の機械を作らなくてよくなった。*7やったぜ。

多引数プログラムとパラメタ定理

我々が扱うプログラムは複数の引数を取るものもある。ここで複数の引数のうち、いくつかを固定してしまったものもまたプログラムである。例えば  \mathrm{add}(x,y) = x+y を考えてみよう。これは2引数のプログラムである。引数  y を固定した  \mathrm{add_3}(x) = \mathrm{add}(x,3) = x + 3 は新しい1引数のプログラムになっている。

このように引数の固定はプログラムから新しいプログラムをつくる写像になっている。上の例では y ごとに対して新しい関数 \mathrm{add}_y が定まる。Haskellとかだとこういうことやれるわけだし、気分的には計算可能になってほしい。実際そうなって、それを主張するのがパラメタ定理である。

パラメタ定理
任意の m,n \in \mathbb{N} に対して、パラメタ化を行う  (1 + m)-引数プログラム  S^m_n \in \mathbb{N}が存在する。
つまり、任意のソースコード  e \in \mathbb{N} に対して  \{S^m_n(e, \vec{y})\}(\vec{x}) = \{e\}(\vec{y}, \vec{x}) が成立する。
ここで \vec{y}, \vec{x} はそれぞれ m, n 個の変数の組である。
対角化演算子不動点

「対角線には魔物が住む」というのは記号論理学での某教員の言だったが、クワインの話でも対角化の話が出てくる。対角化とは大雑把に言えば2変数関数の引数に同じものをぶちこむことである。例えば  f(x,y) f(a,a) と同じ引数  a を入れることだ。対角化は計算理論とか基礎論っぽい話でよく出てくる重要なテクニックである。

前置きが長くなったが、計算理論での対角化を考える。万能プログラムは、1引数プログラムに制限すれば2引数関数なので、これを対角化することができる。すると、自分自身のソースコードを入力としてプログラムが実行されることになる。フォーマルに書くと次のようになる。

対角化演算子

プログラム  D が存在して、1引数プログラムのソースコード e \in \mathbb{N}に対し、
 D(e) = \{e\}(e) が成立する。

さて、これを使うと不動点を構成することができる。以下の話は直接クワインには使わないので、読み飛ばしてもよい。1引数プログラム p不動点とは、入力 a p(a) = a が成立するものの事である。 D(p(\lceil D \rceil))不動点っぽくなっている。 D の定義から、 D(p(\lceil D \rceil)) =\{p(\lceil D \rceil)\}(p(\lceil D \rceil) となる。形は似ていて、 \{p(\lceil D \rceil) \}(x) = p(D(x))となってくれるなら、 \{p(\lceil D \rceil)\}(p(\lceil D \rceil) = p(D(p(\lceil D \rceil))) となり不動点になる。*8実際はそんなうまく行かない。悲しい。

ぼやいていてもしょうがないのでもうちょっとがんばる。 \{p(\lceil D \rceil ) \}(x) = p(D(x))が成り立たなくて困っているので、 \{H(\lceil p \rceil)\}(x) = p(D(x))と なるプログラム  H を作ってやろう。すると、 D(H(\lceil p \rceil))不動点になる。
 D(H(\lceil p \rceil)) = \{ H(\lceil p \rceil) \}(H(\lceil p \rceil)) = p\left(\{H \left(\lceil p \rceil \right)\}\left(H \left(\lceil p \rceil\right)\right)\right)=p(D(H(\lceil p \rceil)))
となるからである。

というわけでがんばって  Hを作ればよい。プログラム f f(e,y) = \{e\}(D(y)) を満たすものとする。これは万能プログラム  U を使って作ることができる。これにパラメタ定理を使い、  H(e) = S^1_1(\lceil f \rceil,e) とする。これが求めるものになっている。実際、  \{H(\lceil p \rceil)\}(x) = f(\lceil p \rceil, x) = p(D(x))となっている。

以上をまとめると次のようになる。

不動点定理*9

あるプログラム  D(H(x))が存在して、任意の1引数プログラムのソースコード  e に対して、
 D(H(e)) \{e\}不動点になる。
そしてクワイン

前節で不動点定理を証明したが、実はこれはクワインをつくるのには直接使えない。前節の不動点定理はプログラムについての不動点であったが、クワインソースコードについての不動点定理だからである。しかし、対角化演算子を使うという基本方針は同じである。

 \mathbb{write}(x) x を出力する関数とする。副作用を含むので真面目に考えるとめんどくさそうだけど、多分対角化とかはそのまま成り立つからこのまま突っ走ろう。 まず対角化演算子ソースコード版を作る。 \overline{D}(e) = S^1_0(\lceil D \rceil, e) とする。すると  \{\overline{D}(e)\} = D(e) = \{e\}(e) が成立する。  \mathrm{d\_write}(x) = \mathrm{write}( \overline{D}(x) ) と定義すると、 \overline{D}(\lceil \mathrm{d\_write} \rceil)クワインである。なぜなら、  \{ \overline{D}(\lceil \mathrm{d\_write} \rceil) \} = \mathrm{d\_write}(\lceil \mathrm{d\_write} \rceil) = \mathrm{write}(\overline{D}(\lceil \mathrm{d\_write} \rceil))となり、自分自身のソースコードを出力するからである。

この話を一般化すると次の定理が成り立つ。

一般化クワイン

1引数プログラム  p に対し、 \mathrm{d\_p} = p(\overline{D}(x))とする。
このとき、ソースコード  \overline{D}(\lceil \mathrm{d\_p} \rceil)コンパイルし実行すると、 
p に自身のソースコードを入力としてあたえた結果を返す。

クワインの実装

作戦会議

以下なんとなくC++を念頭に置きつつ、どうクワインを実装したらいいかを見ていく。

前節の結果から  \overline{D} が作れればクワインが実装できることが分かった。さて、  \overline{D} とはいったい何なのだろうか。まず、  \overline{D}ソースコード  e を与えるとソースコード  \overline{D}(e) を返す関数*10である。 \overline{D}(e) は対角化を行うため、ソースコード  e の情報はすべて保持しておきたい。どう保持しておくかに正解はないけど、とりあえずstring型の変数で保管しておくことにしよう。愚直だけど実装楽だし情報落ちがないし。

次に \overline{D}(e) はどういう機能のプログラムか考えてみよう。 定義に振り替えると、 \{\overline{D}(e) \} = \{e\}(e) となる。これは、コンパイルして実行すると、  eコンパイルして、引数に  eを与えたものを実行することを意味する。

f:id:dolicas:20160502205524p:plain

よって、 \overline{D} は大雑把には上の図のようなプログラムになる。プログラムの途中でstring型の変数eにソースコード e を格納する。これは単に文字列として代入している。ちゃんとソースコード e ごとに1つソースコードが対応している。そのあとの部分で eコンパイルして、引数を e としたものを実行する、という機能を書く。

クワインを書くためだけにコンパイラを書くとかマジかよ」と思われるかも知れないが、実はそこまで大変ではない。今回は「全ての」プログラムに対して対角化して一般化クワインを作る必要はなく、  \mathbb{write}(x) についてだけ、 \overline{D}の定義式が成立すればいい。前節のクワインであることを示した式変形中では、これしか使っていないからである。よって、文字列の出力機能だけを持った言語のコンパイラを書いてやればいいのである。

 \mathrm{d\_write}(x)の実装

 \overline{D}の実装は、対角化する  \mathrm{d\_write}(x) によって変わりうる。とりあえずおいて \mathrm{d\_write}(x)を実装しよう。

 \mathrm{d\_write}(x) x を入力として受け取って、  \overline{D}(x)を出力するプログラムだった。 \overline{D}ソースコード(黄色い部分)を青い部分で包む関数だった。なので  \overline{D} の実装が決まっていればこれは簡単に実装できる。たとえば次のようにすればいい。

#include<iostream>

using namespace std;

int main(){
	//input
	string x;
	cin >> x;
	//output
	string D_s = (Dの黄色以前の青色部分) + x + (Dの黄色以降の青色部分);
	cout << D_s << endl; 
}

ソースコード中で  \overline{D}って書く方法が分からなかった。悲しい。最後の改行は気を付けないと微妙にずれると思う。

ここでのポイントは、入力  x \overline{D} を合成するのを、 \mathrm{d\_write}(x)ソースコード内でやったことである。 \mathrm{d\_write}(x) 自体は、黄色い部分に埋め込まれるため、青い部分に影響しない。なので、このソースコード中の「(Dの黄色以前の青色部分)」という部分に影響しない。クワインを作るとき愚直にやると話が循環してしまって困るのだが、この例ではうまく回避できている。

\overline{D} の実装

\overline{D} の実装に戻ろう。前に述べたように、 \overline{D} はすべてのソースコードコンパイルできる必要はなく、上の \mathrm{d\_write}(x)だけ扱えればいい。定義  \{\overline{D}(e) \} = \{e\}(e) から、どう実装したらいいかを考えていく。

まず前半部について考える。

	//input
	string x;
	cin >> x

本来は「標準入力から文字列を受け取って、xに渡す」という部分だが、 [\overline{D}] の定義より入力は  e である。よって個々の部分は「xにeを代入した」と解釈される(あるいはコンパイルされる)べきである。

つぎに後半部を扱う。

	//output
	string D_s = (Dの黄色以前の青色部分) + x + (Dの黄色以降の青色部分);
	cout << D_s << endl; 

D_sはxの前後に文字列を足している。さっきの議論より、xにはeが代入されているから、D_sはeの前後に文字列を足したものである。最後にcout << でこれを出力している。

以上より、 \overline{D}(e) がやるべきことは次のようにまとめられる。

  • ソースコード  e を読んでいく。これはstring型変数eを頭から読んでいけばいい。
  • 「string x; cin >> x」という組があったらxはeが代入されていると解釈する。連想配列か何かで保存しておく。
  • 「string D_s = hoge + x + fuga;」があったらD_xに右辺の文字列が代入されてるとしてひとつ前と同じよう処理する。"funi"みたいに与えられた文字列を処理できる必要がある。
  • 「cout << val << endl;」があったらvalを出力する。
  • ここで定義されてない変なことがあったらエラーを吐いて落ちる

まあ頑張れば実装できるよね。

実装の簡略化

上の  \overline{D} は明らかに無駄が多い。実際、変数の値を保持しておいて、計算して、という過程をやる必要はない。どうせ  \mathrm{d\_write}(x) の機能自体は変わらず、そこまで一般性を持たせる必要はないからである。

 \overline{D}(\lceil \mathrm{d\_write} \rceil)の機能を要約すると、以下のようになっている。

  • なんか入力xというのがあるらしい。(Dの黄色以前の青色部分) + x + (Dの黄色以降の青色部分)という形にして出力する。

この動作を行うために必要なのは、(Dの黄色以前の青色部分)と(Dの黄色以降の青色部分)、および挿入箇所xという情報を持っておくことだけである。情報の大部分を占める前半は文字列なので、「これをeの代わりの文字列として持っておけばいいんじゃない?」と思えるしその方針でよい。挿入箇所は特殊な記号(たとえば@)で表せばよい。

こうすると  \overline{D} がやるべきことは相当減る。

  • 文字列eを順番に出力する。
  • @があったらそこでeを挿入してから前の作業を再開する。""をつけるのに気を付けよう。*11
  • ただし言語の仕様でエスケープシーケンス(\nとか)があるので気を付けて処理する。

これで  \overline{D} の青い部分に何を書くべきかは決まった。すると文字列eに何を持たせるべきかも決まる。これで全部の実装が定まった。めでたしめでたし。

考察

不動点定理の補足

全てのプログラムに対する不動点を作ろうとおもうと、対角化演算子をつくらなければならない。これはコンパイラを作るのに相当して結構骨が折れる。一方、クワインのように特定の関数の不動点が欲しいだけだったらフルスペックの対角化は必要ない。その関数についてだけ対角化できればいいのである。理論的に便利なのと実用上便利なのは違うわけですね。まあ当たり前といえば当たり前の話ですが。

WikipediaでのCでのクワイン実装

冒頭でこれわけわからないって言ってたけど、この話を踏まえたうえで読むとよくわかる。大体どのクワインもeval関数(プログラムの「値」を「評価」する)みたいなのを作って頑張るのは同じっぽいし、一回種明かしされると不思議じゃなくなる。

言い訳

エスケープシーケンスの処理とか微妙な改行(最後とか)考えるのが面倒で実装しなかった。そのうちやるかも。ごめんなさい。

参考文献

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

*2:実際にはこれは定義というよりは観察結果を帰納したものである。人間が今まで考えてきた「まっとうな」計算モデルで、チューリングマシンより強力なものはない。逆に十分に強力な計算モデルはチューリングマシンと等価だった。だからチューリングマシンができることを計算可能と定義してしまおうという話である。

*3:本当は無限ループとかで値が返ってこない場合がある。このような「関数」を部分関数という

*4:自然数の有限列全体と自然数の間には全単射が存在する。メモリーとかは所詮0,1の有限列だから自然数エンコードできるわけである。

*5:基本的なアイディアとしては、計算機上で計算機をエミュレートするプログラムを書けばいい。プログラムが実行されていく様をエミュレートできるので結果は同じになる。

*6:無限ループ等で結果が返ってこないときは、両辺ともに値が返ってこないという意味で一致する。

*7:量子コンピュータとかだと万能計算機じゃなくて特定の問題だけ解くようなのを作ってるらしい。計算効率に関してはこの定理は何も言ってないし、その点では万能計算機が「万能」なわけじゃない。

*8:λ計算とかだとだいたいこんな感じで行けて楽

*9:この話は多引数のときに一般化可能である

*10:これは数学的な意味での関数であって、プログラミングの意味ではない。

*11: (Dの黄色以前の青色部分)とかに持たせるスタンスでもOK