自己複製するプログラムがどのように自然発生するか（論文解説）

はじめに

今年の7月、GoogleのParadigms of Intelligence Teamという研究チームと、シカゴ大学の研究者によって、『Computational Life: How Well-formed, Self-replicating Programs Emerge from Simple Interaction』 というタイトルの論文がプレプリントサーバーのarXiv上に公開されました。

日本語に訳すと、『計算生命：単純な相互作用から自己複製するプログラムがどのように生まれるか』 という意味になります。

この論文のすごいところは、自己複製しないランダムなプログラムを適応度景観のない環境(ランダムな変動が進化の主な要因となる環境)に置くと自己複製を行うプログラムが生まれ、その後も自己複製を続けて複雑な行動を続けることを実験によって確かめたところです。

かつて、天文学者のフレッド・ホイルは、

生体高分子だけでなく、生物細胞の制御プログラムまでもがこの地球上の原始的有機物スープの中で偶然にもたらされたという考えは明らかに高次元のナンセンスである。

と述べました。
生命細胞の材料となる有機物が十分にある原始のスープの中から原始的な生命が生まれる確率はごくごく小さい為、生命が偶然に生まれることはあり得ないという意味です。

しかし、この論文はフレッド・ホイルの発言と対照的に、ランダムな状態から自然に生命のような複雑な自己複製装置が生まれる可能性は十分にあることを示しています。人類が現在も挑んでいる謎の一つである、生命の起源の解明に大きく貢献する可能性がある論文だと思います。

Brainfuck

本題に入る前の前提知識として軽くBrainfuckの説明を挟みます。

Brainfuckとは、Urban Müllerが開発したプログラミング言語で、><+-.,[]の8つのコマンドのみでチューリング完全を実現しています。

0で初期化された配列とそのポインタを下記の通りに操作することで動作します。

コマンド	処理
>	ポインタをインクリメント
<	ポインタをデクリメント
+	ポインタが指す要素の値をインクリメント
-	ポインタが指す要素の値をデクリメント
.	ポインタが指す要素の値を出力
,	入力から1バイト読み込んで、ポインタが指す要素に代入
[	ポインタの指す要素の値が0なら、対応する]までジャンプ
]	ポインタの指す要素の値が0でなければ、対応する[の直後の要素までジャンプ

BrainfuckでHello Worldを書くと次のようなコードになります。こちらのコンパイラにコピペして試していただくと処理の流れがわかりやすいです。

+++++++++++[>++++++>++++++>+++>++++++++<<<<-]>+++>++++++.<.>++++..+++.>-.>-.<<.>>-----.<<---.<-.>>+.

拡張Brainfuck(BFF)

先述したBrainfuckを元にこの研究のために新しく考えられた、Brainfuckを拡張した言語です。
論文中では、BFFと略されるこの言語は元のBrainfuckの出力と入力を、配列のある要素からある要素へコピーする処理に置き換えたものです。

Brainfuck同様、0で初期化された配列とそのポインタを操作することで動作します。
Brainfuckとの違いは、読込元のポインタと書込先のポインタの二つのポインタ(論文中head0, head1のこと)を持つことで、下記のように動作します。

コマンド	処理
>	読込元ポインタをインクリメント
<	読込元ポインタをデクリメント
}	書込先ポインタをインクリメント
{	書込先ポインタをデクリメント
+	読込元ポインタが指す要素の値をインクリメント
-	読込元ポインタが指す要素の値をデクリメント
.	書込先ポインタが指す要素の値を読込元ポインタが指す要素にコピー
,	読込元ポインタが指す要素の値を書込先ポインタが指す要素にコピー
[	読込元ポインタの指す要素の値が0なら、対応する]までジャンプ
]	読込元ポインタの指す要素の値が0でなければ、対応する[の直後の要素までジャンプ

原始スープのシミュレーション

生命の起源として考えられている説は大きく二つあります。
生命は地球上の有機分子から生まれたとする 「地球説」 と、宇宙空間で生まれたアミノ酸が起源だと考える 「パンスペルミア説」 です。

原始スープとは地球説の中に登場する用語で、初期の地球で有機分子が海洋に蓄えられた状態をスープにたとえたものです。原始スープの中の有機物が、やがて最初の生命に至ったと考えられています。

この論文では、拡張Brainfuckの配列の各要素を一様分布からランダムに初期化して原始スープを再現し、相互作用とランダムな突然変異によってどのような変化が現れるかを観察しました。
結果、冒頭でも述べたように自己複製するプログラムが自然発生しました。

自己複製プログラムが単に偶然生まれたものではないことを確かめる

拡張Brainfuckによる原始スープから自己複製するプログラムが生まれることは分かりましたが、配列の各要素はランダムに初期化されており、また、一定の確率で相互作用以外のランダムな突然変異を行うシミュレーションのため、自己複製するプログラムは偶然生まれたものである可能性が残っています。

突然変異による発生では無いことは、突然変異率を0にしたシミュレーションでも自己複製するプログラムが発生することを確かめれば良いので、簡単に確かめられます。

一方、初期状態の時点で自己複製するプログラムを含まないことを確かめるのは非常に難しいです。自己複製プログラムは、単純に自己の文字列全体をコピーしている訳ではなく複雑な状態遷移を経て自己複製しているかも知れないからです。

そこで、研究チームは高次エントロピー(論文中ではhigh-order entropy)というメトリクスを使って自己複製プログラムの誕生が偶然ではないことを確かめています。

高次エントロピーとは

高次エントロピーは、この論文内の定義ではシャノンエントロピーとコルモゴロフ複雑度の差で表される複雑さの指標です。

シャノンエントロピー

シャノンエントロピーは次の式で表される量です。

H(X) = - \sum_{i} P(x_i) \log_2 P(x_i)

全ての事象が同じ確率で発生する一様分布の時最大になり、一つの事象が確実に発生する場合に最小値0をとるという性質があります。

コルモゴロフ複雑度

コルモゴロフ複雑度は、ある文字列を生成するために必要な最小限のプログラムの長さを数値化したものです。
例として、s1="aaaaaaaaaa"という文字列とs2="abckefkoks"という文字列のコルモゴロフ複雑度を比較してみます。s1の方は「'a'を10回出力する」という短いプログラムで書くことができますが、s2は規則性が無いのでs1より長いプログラムで書く必要があります。

そのためs1のコルモゴロフ複雑度は、s2のコルモゴロフ複雑度より小さいと言えます。

高次エントロピーの解釈

高次エントロピーはシャノンエントロピーからコルモゴロフ複雑度を引いた値なので、下記の表のように解釈できると考えられます。

シャノンエントロピー	コルモゴロフ複雑度	高次エントロピー	解釈
高い	高い	低い	分岐先が多い一様分布によって生成された文字列
高い	低い	高い	多くの種類のプログラムによって生成された文字列
低い	高い	低い	分岐先が少ないー様分布によって生成された文字列
低い	低い	低い	少ない種類のプログラムによって生成された文字列

結果

原始スープのシミュレーションの高次エントロピーを計算した結果、初期状態では0に近かった高次エントロピーが時間経過につれて増加する様子が確認できました。
（元論文 Figure1 を参照ください。）

つまり、自己複製プログラムがランダムな初期化やランダムな突然変異によって生まれた物ではないことが確かめられました。

手元で試してみる

研究チームが公開しているリポジトリを使って、手元で自己複製プログラムが生まれる様子を観察できます。

最初は一様分布から生成されたランダムな状態の様子

自己複製するプログラムが誕生し、拡大していく様子

多様性が生まれ、勢力が移り変わっていく様子

感想

論文を読んで、大学時代に読んだネット小説の中で一番面白かった、戸塚たくす先生の 『神の観察』 という作品を思い出しました。

無料で読める短編なので興味のある方はぜひリンクを辿って読んでみて欲しいですが、あらすじは

主人公は、暇つぶしの遊びとして、単純な生命に見立てて自己増殖を続けるプログラムを作る。
ただ自己増殖し続けるファイルに飽きてしまった主人公は、次のステップとして一定の確率で突然変異を起こすようにプログラムを修正する。
突然変異によって進化が可能になったプログラムの群は次第に性交や寄生、捕食など高度な生命のような挙動を初め、やがて知性のようなものも観察できるようになってきて…

というような感じです。

昔読んだSF小説が現実になりつつあり、とてもワクワクする研究分野だと思います。続報を待ちたいと思います。

参考文献