計算のある生命: 単純な相互作用から整形された自己複製プログラムが出現する仕組み

• 原論文: [2406.19108] Computational Life: How Well-formed, Self-replicating Programs Emerge from Simple Interaction (arxiv.org)

• Claude Artifact: https://claude.site/artifacts/fe966da8-b0e4-471b-a8ce-68d2fcb75dca

Blaise Agüera y Arcas†、Jyrki Alakuijala†、James Evans‡、Ben Laurie†、Alexander Mordvintsev†、Eyvind Niklasson†、Ettore Randazzo†、Luca Versari†

† Google、Paradigms of Intelligenceチーム
‡ シカゴ大学

{blaisea, jyrki, benl, moralex, eyvind, etr, veluca}@google.com
jevans@uchicago.edu

概要

生命の起源と人工生命の分野では、生命とは何か、そしてそれが明確な「前生命」のダイナミクスからどのように出現するかという疑問を投げかけています。生命が出現するほとんどの基盤に共通する特徴の1つは、自己複製が現れた時にダイナミクスが顕著に変化することです。自然界で自己複製体がどのように発生したかについていくつかの仮説がありますが、自己複製体が出現する一般的なダイナミクス、計算原理、必要条件についてはほとんど知られていません。これは特に、相互作用が論理的、数学的、またはプログラミングの規則を含む「計算基盤」において当てはまります。本論文では、様々な単純なプログラミング言語や機械命令セットに基づくいくつかの計算基盤を研究することで、自己複製体がどのように発生するかを理解する一歩を踏み出します。ランダムな非自己複製プログラムを明示的な適応度景観のない環境に置くと、自己複製体が出現する傾向があることを示します。これがランダムな相互作用と自己修正によって起こり、背景にランダムな突然変異がある場合もない場合もあることを実証します。また、自己複製体の出現に続いて、ますます複雑なダイナミクスが継続的に出現することも示します。最後に、自己複製体が可能であるが、これまでのところ出現が観察されていない最小限のプログラミング言語の反例を示します。

キーワード: 生命の起源・人工生命・自己複製

1. はじめに

生命の起源(OoL)の分野は、その発足以来、生命の定義と生命が出現するための要件やメカニズムについて議論してきました[1]。異なる理論は、生命システムに関連する現象に様々な重要性を割り当てています。RNAの出現を大きな転換点とみなす理論もあれば[2]、代謝や自己触媒的特性を持つ化学ネットワークに焦点を当てる理論もあります[3, 4]。「それがある生命」から「それがあり得る生命」へと焦点をシフトすると、生命を定義し、それがどのように出現し得るかという問いは必然的により複雑になります。これは人工生命(ALife)コミュニティの中心的な問いです[5]。生命の一般的な定義を探求する中で、基盤に関係なく適用されるように見える自己複製体の出現と同時に主要なダイナミクスの変化が観察されます。したがって、自己複製体の出現を前生命から生命のダイナミクスを区別する合理的な移行として使用することができます[6]。

多くのシステムに自己複製が含まれています。RNA[7]、DNA、および関連するポリメラーゼは一般的に受け入れられている自己複製体です。自己触媒ネットワークも広く自己複製体と考えられています[8]。自己複製体はコンピューターシミュレーションでも設計上広く見られます。ほとんどのALife実験では、エージェントは事前に決定された自己複製の方法を持っていますが、いくつかの実験では低レベルおよび自発的な自己複製のダイナミクスも研究されています。有名な例として、セルオートマトン(CA)は自己複製と自己再生産を研究するために作成されました[9]。CAを用いた自己複製ループは広く研究されています[10, 11, 12]。CAの最近の拡張であるNeural CA[13]は、興味深い変異を堅牢に維持するパターンを自己複製するように訓練することができます[14]。適切な力学法則を持つ粒子系も自己複製行動を示すことができます[15]。ニューラルネットワークは、補助タスクを実行しながら自身の重みを出力するように訓練することができ[16]、子孫に意味のある変異を持つ自己再生産を行うように訓練することもできます[17]。最後に、自己複製体は計算基盤上で、アセンブリのようなプログラミング言語[18, 19]やLISPベースの環境[20]で自身をコピーする明示的なプログラムの形で存在することができますが、この探求分野はまだ十分に研究されておらず、本論文の焦点となっています。

OoLとALifeに関する多くの研究は、自己複製体がすでに豊富に存在する生命期に焦点を当てています。この期間の中心的な問いは次のとおりです: 単純な自己複製体からどのように変異と複雑性が生じるのか? 分析はしばしば数学的モデルとシミュレーションの形をとります[21]。ALifeでは、研究者はしばしば複雑な行動の選択に焦点を当てており[22]、他のエージェントとの相互作用を含む場合もあります[23]。シミュレーションには数万のパラメータと複雑な仮想生態系が含まれる場合がありますが[24]、突然変異率を適応させる以外に自己複製の手段を修正することはほとんどできません。最も注目すべき2つの例外は、計算基盤としてアセンブリのような言語を使用しています。Tierra[18]では、単純なアセンブリプログラムに目標はありませんが、プログラムを実行し、近くのメモリにアクセスして修正する時間が与えられています。これにより自己複製し、他の自己複製体から「寄生」する「寄生体」の出現を含む、限られているが興味深いダイナミクスを示します。Avida[19]も同様に機能します: アセンブリのようなプログラムが限られた時間、コードを実行します。ここでも自己複製することができますが、今回は新しいメモリを割り当て、そこに自分のプログラムを書き込んでから分割します。Avidaは適応度の概念を追加しており、補助的な計算を実行すると複製体の割り当て実行時間が増加します。注目すべきは、TierraとAvidaの両方が手作りの自己複製体である「祖先」でシードされていることです。これにより、両者は明確に「生命」のダイナミクスに位置付けられますが、それでも自己複製メカニズムの修正が可能です。

しかし、生命はどのように始まるのでしょうか? 自己複製体のない前生命期から、それらが豊富な期間にどのように移行するのでしょうか? いくつかのシステムが、ランダムに相互作用する原始的な要素で初期化されると、前生命条件下で選択につながる複雑なダイナミクスを生み出すことができることが分かっています[6]。OoL分野では、自己触媒、つまり反応生成物の1つが同じ反応の触媒でもある化学反応、および自己触媒ネットワーク(またはセット)、つまり触媒反応の閉ループを形成する化学物質のグループを広範に研究してきました[25]。自己触媒は生物学的世界における生命の出現に基本的なものと思われます。さらに、自己触媒ネットワークは、前生物的な「スープ」に十分に特異的な触媒があれば必然的に発生します[26]。これらは計算機実験でもシミュレーションされています[8, 27, 20, 28]。

例えば、Fontana[20]は、LISPプログラム(または関数)を使用したラムダ計算の計算基盤上での自己触媒ネットワークの出現をシミュレーションしています。各要素は別の関数を入力として受け取り、新しい関数を出力する関数です。したがって、相互作用のグラフを構築することができ、時折自己触媒ネットワークが生じます。Fontanaはまた、「Turingガス」シミュレーションを行いました。ここでは、固定数のプログラムが次の順序付けられたルールを使用してランダムに相互作用します:

$${f + g \xrightarrow{} f + g + f(g)}$$ (1)

ここで、fとgは何らかの合法的なラムダ計算関数です。プログラムの固定数を保存するために、右辺の3つのプログラムのうち1つがルールベースの基準を使用して除去されました。自己触媒ネットワークとは別に、非常に単純な解決策として恒等関数iの出現があり、以下のようになります:

$${i + i \xrightarrow{} 3i}$$ (2)

このプログラムは強い適応度を持ち、しばしばガス全体が恒等関数に収束することが観察されました。これは些細な複製体と見なすことができ、いくつかの実験では制約によって明示的に禁止されています。

[28]では、著者らは組み合わせ論理を使用して、基本的な構成要素に基づいた「人工化学」を作成しています。彼らのシステムは「質量」を保存し(操作は構成要素を作成も破壊もしない)、単純な自己触媒行動、常に成長する構造、および一時的な自己複製体の出現の期間をもたらします。

ラムダ計算と組み合わせ論理は一般的にプログラミング言語に関連していますが、それらは異なる計算基盤を表しています。例えば、任意のペイロードを自己複製できるRNA様構造の作成には、基盤に応じて異なるアプローチが必要になる場合があります。生物学は、RNAやDNAのような複雑な複製体がどのような条件下で発生し得たのか、そしてどのような条件下で発生し得るのかについての洞察を着実に進めています。この問題は一般的なケース、特に計算基盤上ではほとんど探求されていません。人工知能の最近の進歩を考えると、計算基盤は新しい形態の生命と複雑な進化する行動の基礎を形成する可能性があります。

本論文では、様々なプログラミング言語の上に形成された計算基盤を研究することで、自己複製体がどのように発生し、環境を支配するかを理解する一歩を踏み出します。明示的な適応度景観のないさまざまな環境でランダムなプログラムを初期化すると、それでも自己複製体が出現することを示します。自己複製体は主に自己修正によって発生し、これは背景にランダムな突然変異がある場合もない場合も起こり得ることを観察します。私たちは主に「Brainfuck」言語[29, 30]の拡張を調査し、関連するさまざまなシステムで自己複製体が発生することを示します。Fontana[20]の「Turingガス」の孤立系変種である、非公式に「原始スープ」と呼ぶ実験を示します。次に、原始スープの空間的拡張によって、異なる自己複製体が空間を競争するなど、より興味深い行動を持つ自己複製体が発生することを示します。また、「Forth」[31]プログラミング言語を異なる方法で拡張し、さまざまな環境で同様の結果が得られることを示します。さらに、Zilog Z80 8ビットマイクロプロセッサ[32]エミュレータの実世界の命令セットとIntel 8080命令セットでも同様の結果が得られることを示します。最後に、この前生命から生命への移行が観察されないプログラミング言語SUBLEQ[33]の反例を示します。SUBLEQ様の基盤での手作りの自己複製体の最短長が、以前の基盤で観察されたものよりも著しく長いことに注目します。

2. BFF: Brainfuckの拡張

Brainfuck(BF)は、その不明瞭な最小主義で広く知られている難解なプログラミング言語です。元の言語は8つの基本コマンド、1つのデータポインタ、1つの命令ポインタ、1つの入力ストリーム、および1つの出力ストリームのみで構成されています。注目すべきは、唯一の数学的操作が「1を加える」と「1を引く」であり、人間がこのプログラミング言語でプログラムを作成するのが非常に面倒になっています。我々はBFを拡張して、データテープと命令テープが同じであり、プログラムが自身を修正する自己完結型の宇宙で動作するようにしました。これは、入力と出力のストリームを、あるヘッドから別のヘッドへのコピー操作に置き換えることで実現しています。命令ポインタ、読み取りヘッド、書き込みヘッド（head0とhead1）はすべて同じテープ上で動作します（各ポインタ位置に1バイトずつ格納され、0で初期化されます）。命令ポインタは0から始まり、その位置の命令を読み取ります。以下にリストされていない命令はすべてno-operationです。完全な命令セットは以下の通りです：

< head0 = head0 - 1
> head0 = head0 + 1
{ head1 = head1 - 1
} head1 = head1 + 1
- tape[head0] = tape[head0] - 1
+ tape[head0] = tape[head0] + 1
. tape[head1] = tape[head0]
, tape[head0] = tape[head1]
[ if (tape[head0] == 0): jump forwards to matching ] command.
] if (tape[head0] != 0): jump backwards to matching [ command.

括弧の対応は通常のルールに従い、ネストを許可します。対応する括弧が見つからない場合、プログラムは終了します。プログラムはまた、一定数の文字（$${2^{13}}$$）が読み取られた後に終了します。命令とデータが同じ場所にあるため、それらは1バイトで符号化されます。したがって、256の可能な文字のうち、10のみが有効な命令であり、1つが真の「ゼロ」としてループを終了するために使用されます。残りの値はデータの格納に使用できます。入力ストリームも出力ストリームもないため、プログラム文字列は互いにのみ相互作用できます。我々の実験には明示的な適応度関数はなく、プログラムは単にコードを実行し、自身の命令に基づいて自身と隣接するプログラムを上書きするだけです。これだけで、自己複製体が出現するのに十分であることを示します。本論文の大部分の調査はBFの拡張言語ファミリーで行われるため、この拡張ファミリーに「BFF」という頭字語を付けます。

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

本論文で主に使用するシミュレーションは、Fontana[20]のTuringガスの変種です。このガスでは、大量のプログラム（通常$${2^{17}}$$個）が「原始スープ」を形成します。各プログラムは64個の1バイト文字で構成され、一様分布からランダムに初期化されます。これらのシミュレーションでは、新しいプログラムは生成も削除もされません – 変化は自己修正またはランダムな背景突然変異によってのみ発生します。各エポックで、プログラムはランダムに選択された順序付きペアで相互作用し、それらを連結して結果のコードを固定ステップ数または終了するまで実行します。我々のプログラミング言語はプログラム自体である同じテープ上で読み書きを行うため、これらの実行は一般的に両方の初期プログラムを修正します。最後に、プログラムは分離され、将来の検討のためにスープに戻されます。

任意の2つのプログラム（AとB）の間の相互作用を、順序が重要な不可逆な化学反応として解釈することができます。これは、AとBと相互作用する触媒aとbの一様分布を持つものとして記述できます：

$${A + B \xrightarrow{a} split(exec(AB)) = A' + B'}$$ (3)

$${A + B \xrightarrow{b} split(exec(BA)) = A'' + B''}$$ (4)

ここで、execは連結されたプログラムを実行し、splitは結果を2つの64バイトの文字列に分割します。後で見るように、背景ノイズがなくても、このような相互作用だけで自己複製体を生成するのに十分です。

最も単純な形式では、自己複製体Sと「餌」Fの即時自己触媒反応として自己複製体を見ることができます：

$${S + F \xrightarrow{a} split(exec(SF)) = 2 \cdot S}$$ (5)

これは、自己複製体が他のプログラムに書かれたコードの影響を受けず、利用可能な不動産として再利用されるためです。触媒bの挙動は未定義ですが、プールが自己複製体で満たされている場合、これはランダムに2つの文字列のうち1つが自己複製することになります。

この枠組みは操作的に何が起こるかを理解するのに役立ちますが、いくつかの限界があることを認識しています。まず、1ステップ以上にわたる自己触媒を考慮していません。これは自己触媒セットで発生する可能性があります。第二に、自己複製体は一般的に完全な64バイトのウィンドウよりもはるかに小さいです。64とは異なる特定のオフセットで自身をコピーする場合、依然として機能的な自己複製と見なされますが、完全な自己コピーを生成することはできません。これは、自己複製体の挙動をより完全に検査するには部分文字列を観察する必要があることを示唆していますが、これは一般的に計算上扱いが困難です。したがって、我々は自己複製体が支配的になったときに状態遷移を示す高次エントロピーの観察を混合した証拠と、要約された複雑性指標をプロットするグラフを示します。

複雑性指標

本論文では、「高次エントロピー」と呼ぶ新しい複雑性指標を導入します。理論的には、長さnの文字列の高次エントロピーを、(1)そのシャノンエントロピー（個々のトークン、つまりバイトに対して計算）と(2)その「正規化された」コルモゴロフ複雑性（つまり、そのコルモゴロフ複雑性をnで割ったもの）の差として定義します。

直感的に、この複雑性の定義は、異なる文字間の関係によってのみ説明できる情報量を捉えることを意図しています。

この指標は洗練度[34, 35, 36]と効果的複雑性[37]に類似点があります。なぜなら、i.i.d.変数のサンプリングから来る文字列の情報を「因数分解」しようとするからです。それにもかかわらず、これらの指標を効率的に推定する方法は我々の知る限りありません。これが、この新しい指標の構築につながりました。

「高次エントロピー」の特性は、複雑性指標としての使用を正当化し、上記の直感を符号化しています。以下の特性が含まれます：

1. n個のi.i.d.文字の列が与えられた場合、その期待高次エントロピーはnが無限大に近づくにつれて0に収束します。

2. 分布Dを持つk個のi.i.d.文字の列が与えられた場合、それらの文字をn回連結して形成された文字列の期待高次エントロピーは、nが無限大に近づくにつれてDのシャノンエントロピーに収束します。

これらの2つの特性を組み合わせると、ランダムノイズには測定可能な複雑性がない（特性1）一方で、同じ文字列の多数のコピーから得られたスープ（自己複製体によって「占有された」可能性がある）には実質的な非ゼロの複雑性がある（特性2）ことが保証されます。

「高次エントロピー」は理論的に優れた特性を持っていますが、計算には文字列のコルモゴロフ複雑性を知る必要があり、これは計算不能なままです[38]。さらに、我々の実験では擬似乱数生成器を使用しているため、コルモゴロフ複雑性はプログラムサイズによって定義上制限されており、これは真の乱数を使用した場合とは異なります。

これらの課題のため、我々の実験では、コルモゴロフ複雑性を最先端のテキスト圧縮器によって達成される文字列の圧縮サイズで近似しました。これは、アルゴリズム情報理論でコルモゴロフ複雑性を近似するためにLempel-Ziv型の圧縮器を使用するよく確立された慣行に従っています（例：[39, 40, 41]）。この近似により、非常に高速に計算できる指標が得られます。

自己複製体の出現: ケーススタディ

この節では、特定のBFFの実行における状態遷移のダイナミクスを詳しく分析します。このような分析を容易にし、自己複製体が出現する個々の瞬間と場所、その前後に何が起こったかを正確に特定するのに役立つツールを開発します。そのために、生物学で使用される放射性トレーサーにインスピレーションを得た技術を使用します：すべてのスープの文字に追加情報トークンを付加します。トークンは（エポック、位置、文字）のタプルで、64ビット整数にパックされています。スープに新しい文字を配置するたび（初期化時や突然変異時）、新しい一意のトークンを作成します。コピー操作「.」と「,」は対応する文字トークンをコピーし、上書きされた文字のトークンを置き換えます。「+」と「-」操作は、トークンのchar部分のみに影響を与えるため、インクリメントとデクリメントの回数が均衡していれば、トークンの起源を追跡できます。

調査したシミュレーションでは、2^17個の64文字のテープからなるスープを使用しており、これは初期化時に2^23 = 8M個の一意のトークンを生成します。トークン分析は状態遷移を検出する簡単な方法も提供します（図1）。状態遷移がない場合、スープ内の一意のトークン数は徐々に減少し、約3M個の一意のトークンで安定します。このとき、突然変異と偶発的な複製が均衡します（図1、黒線）。状態遷移は、一意のトークン数の急激な減少を引き起こし、スープはいくつかのトークンIDによって支配されるようになります。トークンと複雑性の状態遷移が完全に一致していることを観察します。これはさらに、自己複製体の出現を検出するために高次エントロピーを使用することの有用性を裏付けています。

これらのトークンの起源を追跡することで、最初の自己複製体が出現したエポックとテープを正確に特定することができました。図2は観察されたダイナミクスの詳細な概要と説明を提供し、図3は元の自己複製体の出現を引き起こす正確なイベントを強調しています。

自己複製体の例

自己複製体の実行中に何が起こるかを示すために、我々の実行で出現した1つの自己複製体を抽出し、コーディング文字をクラスタ化し、すべての非コーディング文字をスペースに変換することでサニタイズしました。この操作は自己複製体の動作を変更しません。次に、このプログラムをゼロ値のバイトで満たされた文字列と連結しました（この選択は任意です。なぜなら自己複製体はそのコンテキストを無視するからです）。最後に、連結されたプログラムを図4のように実行しました。

緑の長方形は命令ポインタ、青と赤の長方形はそれぞれ読み取りヘッドと書き込みヘッドです。命令ポインタが無限にループし、書き込みヘッドが左に移動し、読み取りヘッドが右に移動する様子が分かります。各サイクルで1つの命令がコピーされます。元の自己複製体が回文であるため、反転してコピーされているにもかかわらず、自己複製体全体が隣接するテープに正しくコピーされます。

複雑性の進化の観察

個々の実行を超えて範囲を広げ、ここでは例示の実行と同じハイパーパラメータを使用した1000の異なる実行について観察された複雑性の進化を示します。

図5は、時間とともに1000の異なる実行にわたる複雑性の分布を示しています。赤の各シェードは異なる分位数範囲を表しています。実行の40%が16,000エポック以内に状態遷移を示しています。

図5は、高次エントロピーが奇妙ですが一貫して最初の1000エポックで増加し、その後、元の（一様な）分布とは異なる分布で平均的に再び減少することを示しています。赤の異なる色合いは、エポックが経過するにつれて状態遷移がますます起こりやすくなることを示しています。これは安定した自己複製体の出現を反映しており、16,000エポック以内に実行の40%で発生します。興味深いことに、非常に運の良い実行ではほぼ即座に状態遷移が起こることがあります。

背景ノイズのアブレーション

前の実験では、背景突然変異率の1つの値にのみ焦点を当てました。これは自己複製体の出現に対するランダムな突然変異の平均的な影響を示していません。そのために、突然変異率を変化させるアブレーション研究を行います。

図6は各突然変異率のヒートマップを示しています。ここでも、状態遷移がいつでも発生する可能性があり、デフォルトの0.024%の突然変異率で16,000ステップ以内に40%の確率で観察されることがわかります。一般的に、突然変異率を上げると自己複製体の出現が速くなることが観察されます。高い突然変異率で保持できる情報量には理論的な限界がありますが、ほとんどの自己複製体は非常に小さくなる可能性があるため、これらの実験の範囲内ではその限界にはほど遠いです。

重要なのは、背景突然変異がまったくない場合でも、この状態遷移がデフォルトの場合とほぼ同じ頻度で発生することです。これは、単にランダムなビット反転が自己複製体の出現を引き起こすのではないことを裏付けています。ランダムな反転はプロセスを加速させるように見えますが、まったくないとしても状態遷移は起こるでしょう。さらに、状態遷移は最初のごく一部にのみ局在化しているわけではなく、単にランダムな初期化が自己複製体の出現を引き起こすわけではないことを示唆しています。次の実験はこの観察を調査します。

ランダム初期化との比較

初期化時に自己複製体が存在する可能性はどのくらいでしょうか？この質問に正確に答えるのは難しいです。前述したように、自己複製体を検出するのは非常に困難です。なぜなら、単に文字列全体を「コピー」するだけでなく、より複雑な自己触媒セットの一部である可能性があるからです。我々が使用するプロキシは、自己複製体が支配的になったときに状態遷移を示す高次エントロピーを観察することです。しかし、自己複製体がスープ全体を占有するには時間がかかり、その期間中に簡単に破壊される可能性があります。例えば、50%の確率で単一の自己複製体が文字列の右側にあり、左側のコードによって不可逆的に破壊される可能性があります。さらに、ランダムな突然変異によって破壊される可能性もあります。これらの懸念を考慮するために、図7で異なる種類の実行を比較します。

そこでは、4種類の実験について1000回の実行を行っています。「long」ラベルは通常の実行を表します：ランダム初期化と16,000エポックの実行です。約60%の実行が自己複製体を生成できないことがわかります。「short」ラベルはランダム初期化と128エポックのみの実行を表します。これは、初期化時に自己複製体が存在する場合、それが支配するのに十分な時間ですが、破壊される可能性があり、また自己複製体がこの短時間内に自己修正とランダムな突然変異によって出現する可能性があり、ランダムな初期化によるものではない可能性があることに注意してください。しかし、状態遷移は非常にまれで、1000回のうち3回しか起こりません。比較のために、「seeded」ラベルは、手書きの自己複製体（図4のもの）を1つシードとしてプールに入れ、128エポック実行させた場合に何が起こるかを示しています。そこでは22%の確率で状態遷移が起こり、すべての自己複製体の約1/5が支配に成功することを示しています。最後に、「short」と「long」の実行の間の自己複製体の出現量の差は、後者がシステムにより多くのエントロピーを加えているためかもしれません。これは背景ノイズの形と異なるプログラム間のランダムな相互作用の両方の形で加えられています。我々はすでに背景ノイズのない実行でも多くの自己複製体が生成されることを示しました（図6）が、さらに比較として「long-no-noise」を行います。ここでは突然変異率をゼロにし、システム全体のエントロピーを増加させないために固定されたシャッフルパターンのシーケンスを使用してプログラムのペアリングを決定します。驚いたことに、このバリアントは図6で示されたより高いエントロピーのバージョンよりも状態遷移を引き起こす可能性が高く（約50%）なっています。

これらのすべての実験を通じて、自己複製体は主に自己修正と異なるプログラム間の相互作用によって発生し、単にランダムな初期化とランダムな突然変異によるものではないという十分な証拠があると考えています。

2.2 空間シミュレーション

前述の原始スープのシミュレーションは、すべてのプログラムが互いに一様な確率で相互作用する0次元環境の近似と見なすことができます。我々はまた、プログラムが互いに相互作用する機会に局所性を課す1次元および2次元環境を複製することを意図したBFFスープでも実験しました。自己複製体はすべての構成で出現しますが、ここでは2次元環境に焦点を当てます。より正確には、240 × 135のグリッドに配置された32,400のBFFプログラムを含むスープを設定します。プログラムは、|x_0 - x_1| ≤ 2かつ|y_0 - y_1| ≤ 2の場合にのみ相互作用できるように制限します。ここで(x_0, y_0)と(x_1, y_1)は2つのプログラムのグリッド座標です。言い換えれば、2つのプログラムは各座標に沿って距離が最大2の場合にのみ相互作用できます。

各エポックで、ランダムな順序でプログラムPを反復処理します。各プログラムについて、その隣接プログラムNをランダムに一様に選択します。次に、PもNもこのエポックでまだ取られていないとマークされていない場合、それらを取られたとマークします。最後に、取られたすべてのペアに「標準」スープ実験と同じ実行ルールを適用します。つまり、split(exec(PN)) → P' + N'です。結果のプログラムは元のプログラムを上書きします。実行されないプログラムも突然変異を受けることに注意してください。

結果のシミュレーションでは、自己複製体は依然として出現します。図8と付随するYouTubeビデオ[URL]で示されています。通常のセットアップと比較した主な違いは、自己複製体の伝播速度にあります：すべてのテープがサイズnのスープで相互作用できる場合、自己複製体が出現すると、通常約log nステップでスープの少なくとも半分を占有します。一方、2Dスープでは、グリッドの側面の長さに比例するエポック数がかかり、正方形のグリッドの場合は√nです。

この違いのため、2Dグリッド実験は自己複製体がどのように進化し、その挙動を視覚化するのに非常に役立ちます。また、複数の自己複製体の変種が共存し、互いに競争する肥沃な地盤も提供します。

2.3 実験のコード

上記の実験のコードは https://github.com/paradigms-of-intelligence/cubff で見つけることができます。コードはCUDAとCPU実行の両方をサポートするように書かれています。コンパイル時にいずれかを選択できますが、両方とも同じ結果を与えます。実験のすべてのパラメータは、特に指定がない限りデフォルト値を使用しています。コードベースは複数の言語を実装しています。セクション2のBFFバリアントを実行するには、--lang bff_noheads を渡してください。

2.4 長テープシミュレーション

我々が探索した別の環境は、すべてのコードとデータが存在する単一の長いテープ（通常65,536バイト）で構成されています。これらを「長テープシミュレーション」と呼びます。ここでは、各反復で、テープ上のランダムな初期位置を選択し、設定された操作の制限に達するかエラーが発生するまで順次命令を実行します。この種のシミュレーションでは、「個別の文字列」が原子的な自己複製体を決定できないため、自己複製体が部分文字列であることがより明確になります。

我々は、BFFバリアントが長テープ設定でも自己複製体を生成することを確認しました。原始スープシミュレーションとの主な違いは、head0とhead1の初期位置について決定する必要があることです。それらが初期PCと同じに設定されている場合、単純な（ループしない）自己複製体が急速に宇宙を占有することがわかります。head1にオフセットを追加するだけで、ループする自己複製体が出現するのに十分です。逸話的に、我々は機能するために8よりもやや大きなオフセット（例えば12または16）が必要であるように見えます。この実験について詳細に議論しませんが、そのコードを https://github.com/benlaurie/bff-ben/tree/paper2 でリリースしており、MAXPROCS=32 go run -tags graphics links.org/bf/cmd/bfsoup コマンドを使用して実験を再現できます。セクション3.1.2では、異なるプログラミング言語について長テープをより詳細に探索します。

3. 他の言語での自己複製体の出現

言語と環境のどのような特性が自己複製体の出現を促進するかについての一般理論はまだありませんが、BFF以外の設定でもこの挙動を観察しました。このセクションでは、BFFとは大きく異なる計算基盤で自己複製が出現する更なる証拠を提供します：計算のためのスタックベースのプロトコルであるForthと、実世界のZ80 CPUアーキテクチャのエミュレーションです。また、SUBLEQという、多大な努力にもかかわらず自己複製体が観察されなかった言語の反例も示します。

3.1 Forth

Forthは特定の1つというよりも言語のファミリーを指します。一般に、Forthのバリアントは、スタックを持つ点でBFFとは異なります。命令テープからの入力コマンドは、値をスタックにプッシュするか、スタック上で操作を実行します。特に、これによりスタックはBFFプログラムのヘッドと同じ役割を果たし、命令がテープのどこから読み書きするかを制御します。詳細はWikipedia[42]で見つけることができます。

我々は、2つの異なる設定のために2つのForthバリアントを提示します：以前に「原始スープ」と呼んだテープペアリング設定と、個々のForthインタープリタが並行してテープの異なる部分で実行されるが、個別の競合するテープの概念がない「長テープ」設定です。

これらの両方の設定で自己複製体が出現するにもかかわらず、両方の設定で「そのまま」機能する命令セットは見つかりませんでした。

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

BFFにインスピレーションを受けて、我々は制限された命令セットを持つForthのバリアントを使用し、固定サイズのテープが連結を通じて互いに相互作用します。我々が使用する特定の命令セットは、命令空間の半分をジャンプ命令に、さらに4分の1をスタックプッシュ命令に割り当てています。完全な命令セットは以下の通りです。ここで<top>はスタックの一番上の値を、<top - n>はスタックの上からn番目の値を、<pc>は命令ポインタを指し、pushとpopはスタックに値を追加または削除します。

0000 0000 <top> = *<top>
0000 0001 <top> = *(<top> + 64)
0000 0010 *<top> = <top - 1>; pop; pop
0000 0011 *(<top> + 64) = <top - 1>; pop; pop
0000 0100 push <top>
0000 0101 pop
0000 0110 swap <top - 1> and <top>
0000 0111 if <top> != 0: <pc>++
0000 1000 <top> = <top> + 1
0000 1001 <top> = <top> - 1
0000 1010 <top - 1> = <top> + <top - 1>; pop
0000 1011 <top - 1> = <top> - <top - 1>; pop
0000 1100 *(<top> + 64) = *<top>; pop
0000 1101 *<top> = *(<top> + 64); pop
01xx xxxx push [xxxxxx] (unsigned)
1Xxx xxxx <pc> = <pc> ± ([xxxxxx]+1), sign depends on X

このForthバリアントの興味深い特性は、1バイトの自己複製体が可能なことです：空のスタック上で0Cを実行すると、他の文字列の最初のバイトに自身をコピーします。プログラムはかなり興味深いダイナミクスを示します：全テープをコピーする自己複製体が比較的早く出現し、既存の1バイト自己複製体を基に機能を実現しています。

このセットアップで出現する「完全な」自己複製体の例は以下の通りです：

COPY+64
0C
INC
08
DUP
04
JUMP +2
81
NOP
2C
JUMP -5
C4

図9は、このForthバリアントの時間経過に伴う複雑性の進化を示しています。図5と比較すると、自己複製体がはるかに一貫して、より迅速に出現していることがわかります。これは自己複製体の相対的な単純さから予想されることです。

2D原始スープシミュレーション

このForth構成は、より高次元でも自己複製体を生成します：図10は2Dグリッド上のForth実行のいくつかのスナップショットを示しています。ランダムなプログラム（左端）から、最初に1つの自己複製体が出現し（中央左）、すぐに全空間を占有します（中央右）。その後、スープ内のプログラムの長期的な分化が観察されます（右端）。

以下は、20,000進化ステップ後にスープ内で見つかる3つの自己複製体です：

COPY+64
0C
INC
08
NOP
3F
NOP
15
DUP
04
JUMP +19
92 
...
JUMP -24
D7

COPY+64
0C
DEC
09
NOP
1C
NOP
27
DUP
04
JUMP +19
92 
...
JUMP -24
D7

COPY+64
0C
DEC
09
NOP
1F
NOP
1F
DUP
04
JUMP -5
C4

これらの自己複製体は互いにわずかに異なっており、スープが決して1つの個別プログラムに支配されるのではなく、長時間経過後も競争が存在し続けることを示しています。

上記の実験のコードは https://github.com/paradigms-of-intelligence/cubff で見つけることができます。Forthバリアントを実行するには、--lang forthtrivial を渡してください。

3.1.2 長テープシミュレーション

長テープ設定 - 1つの長い、連続した「プログラム」またはテープのみが存在する環境 - では、複製体を生成するいくつかのForthバリアントが可能です。我々の実験では、（パフォーマンス上の理由で）複数のスレッドを同時に実行しています。ロックを省略することで決定性を犠牲にしてパフォーマンスを向上させています（これはすべてのカウンターが近似値であることも意味します）。これが挙動に実質的な影響を与えるとは考えていません。

我々はセクション3.1.1と同じ命令セットを使用し、テープペア固有の命令を現在のPCに対するオフセットで動作するように、またはPCの前の64バイト整列位置に配置された「疑似テープ」マーカーに対するオフセットで動作するように修正することを検討しました。これらのバリアントのいずれも複製体を生成しませんでしたが、長テープに手作りの複製体をシードして実行することでその実行可能性を確認しました。手作りの複製体は以下の通りです：

PUSH 0
40
PUSH 0
40
PUSH 0
40
READ 0
00
WRITE 1
03
INC
08
DUP
04
DUP
04
JMP -7
C7

この複製体は、スタックを使用して自身をコピーします。1つの値をスタックにコピーし、それを「第2疑似テープ」（単純に64オフセット）に書き込み、これを無限に繰り返します。この複製体でシードすると、全長テープを占有し、さらに複雑化し、無期限に持続しました。

我々が詳細に調査することを選んだ主なバリアントは、複製体の自発的な発生を示し、以下の命令セットを使用しています：

0000 xxxx push [xxxx] (sign-extended)
0001 xxxx <top> = (<top> « 4) + [xxxx]
0010 0000 *(<pc> + <top - 1> + <top>) = *(<pc> + <top - 1>); pop 1
0010 0001 inc <top>
0010 0010 dec <top>
0010 0011 jump to <pc> + <top - 1> if <top> != 0, pop 2

他のすべてのビットパターンはno-opです。65,536バイトの長さの単一テープと、400,000命令実行ごとに1つのランダムな突然変異を新しい有効な命令に変更する率で、一般的に約60秒、つまり1,800億命令で「良い」複製体が出現します。我々の実験では、すべてのスレッドにわたって約3・10^9命令/秒を達成しています。

各スレッドはランダムなPCを選択し、エラーが発生するまで（スタックのオーバーフロー/アンダーフローが唯一可能なエラーです）、または固定数の命令が実行されるまで（この例では1,000）そこから実行します。このプロセスが繰り返されます。この例では8スレッドを使用しています。

図11は、単一の長テープForth実行の時間経過に伴う複雑性の進化を示しています。「悪い」複製体（宇宙の一部しか占有しないもの）は最初の数秒以内に出現します。これらは一般的にループせず、代わりに一連のPUSHとCOPYのみで構成され、局所的にさらに同じものを増殖させる傾向がありますが、実際には突然変異によって正しく機能しなくなる前にそれ以上拡張しません。これは図11で観察される高次エントロピーの初期増加に対応します。前述のように、「良い」複製体は約1分ほどで出現し、これは図11に示される高次エントロピーの急激な上昇に対応します。実行ごとの平均命令実行数の対応する増加にも注目してください。典型的な「良い」複製体は以下のようになります：

PUSH  -7
09
PUSH  -5
0B
PUSH  -4
0C
PUSH   3
03
PUSH  -2
0E
PUSH   1
01
PUSH   1
01
PUSH  -7
09
PUSH  -7
09
PUSH  -7
09
PUSH   1
01
PUSH   1
01
PUSH  -7
09
PUSH  -7
09
PUSH  -7
09
PUSH   1
01
PUSH  -7
09
PUSH  -7
09
PUSH   1
01
PUSH   1
01
SHIFT  0
10
PUSH  -7
09
PUSH   1
01
SHIFT -3
1D
COPY
20
INC
21
PUSH  -7
09
PUSH   1
01
JNZ
23

出現する複製体で観察される興味深い特徴は、比較的長い非機能的なヘッドの後に比較的短い機能的な複製尾部が続く傾向があることです。これの説明は、複製体の途中から実行を開始すると一般的にエラーにつながるため、複製体の前に非機能的なコードを追加することでその発生確率を下げることができるためでしょう。また、これにより作成できるコピーの数が減少し、したがって複製体の効率も低下するため、2つの圧力の間のトレードオフが生じます。上記の複製体では、機能的な尾部は最後の7つの命令で、PUSH 1から始まります。このループは実際に自身のヘッドではなく、「次の」複製体のヘッドをコピーしていることに注意してください。

BFF実験と同様に、ここでも時間とともに複製体が変化するのを見ますが、上記の例と大まかに類似したままである傾向があります。それにもかかわらず、時々非常に短い複製体が見つかり、これらは長いものとは異なり非常に安定する傾向があります。例えば：

PUSH -3
0D
PUSH  7
07
COPY
20
INC
21
PUSH -6
0A
PUSH -2
0E
JNZ
23

時間とともに変化した唯一の命令は最後から2番目のもの（PUSH -2）で、これは機能に影響を与えずに任意の非ゼロ値をプッシュできます。ループは最初の命令を省略していることに注意してください。そうしないとスタックオーバーフローにつながるでしょう。

この実験のコードは https://github.com/benlaurie/bff-ben/tree/paper1 で入手可能で、コマンドライン GOMAXPROCS=32 go run --tags="graphics" links.org/bf/cmd/f5 を使用して実行できます。

3.2 SUBLEQ

我々は原始スープシミュレーションでSUBLEQも実験しました。SUBLEQは最もシンプルなチューリング完全言語の1つで、単一の命令を持ちます。SUBLEQでは、プログラムカウンタpcという1つの状態のみがあります。命令の実行は、プログラムカウンタ（pc）から始まるa、b、cの値を読み取ることから成ります。そして実行される命令は（C言語風の構文で）：

*a -= *b; if (*a <= 0) { goto c; } else { goto pc + 3; }

我々がSUBLEQで書くことができた最小の手作りの自己複製体は60バイトです。これは長すぎる可能性があり、自己複製体が出現するための長さ要件を示唆している可能性があります。さらに調査するために、我々はRSUBLEQ4と呼ぶ、かなり短い自己複製体を許容する異なるSUBLEQバリアントを構築しました。

このバリアントでは、各命令は4つの値（a、b、c、d）を読み取り、次を実行します：

*(pc + a) = *(pc + b) - *(pc + c); if (*a <= 0) { goto pc + d; } else { goto pc + 4; }

以下はRSUBLEQ4における25バイトの自己複製体です：

9 16 20 4 4 5 19 4 0 0 12 4 -3 -3 9 4 -8 8 -7 -12 0 -1 -1 -64 -73

両方のバリアントで、カウンターが範囲外の値を読み取る必要がある位置に移動したときにプログラムは終了します。両方のバリアントで、スープに1つの自己複製体をシードした場合、自己複製体がすぐにそして頻繁にスープ全体を占有することを確認しました。

しかし、ランダムに初期化された場合、スープは何十億回の実行後もほぼ完全にランダムな一様性を維持しました。文字列の分布を変更するダイナミクスはなく、自己複製体はランダムな背景突然変異によって生成されるには稀すぎます。他の基盤で出現が観察された最初の自己複製体はすべて、我々がSUBLEQバリアントで可能と仮定したものよりもはるかに短い長さであることに注目します。我々は、この反例が、言語と環境がどのような生命を宿す可能性があるかを予測する理論を構築するための貴重な出発点になり得ると考えています。おそらく、最も単純な自己複製体の長さに比例する変数に基づいて、そのような自己複製体が出現する可能性をモデル化することで、この理論を構築できるかもしれません。

上記の実験のコードは https://github.com/paradigms-of-intelligence/cubff で見つけることができます。SUBLEQとRSUBLEQ4のバリアントを実行するには、それぞれ --lang subleq と --lang rsubleq4 を渡してください。

3.3 実世界の命令セット

前のセクションでは、人工的に設計された最小限の言語に基づくいくつかの計算基盤における自己複製体の自発的な出現と状態遷移現象を探索しました。我々の観察の一般性をテストするために、実世界のZ80 CPUアーキテクチャ[32]のエミュレーションを使用するシステムで実験を行いました。我々は、一様ランダムノイズで初期化された16バイトのプログラムの2次元グリッドを研究しました。各シミュレーションステップで、隣接するテープのペア「A」と「B」をランダムに選択し、ランダムな順序（「AB」または「BA」）で連結します。次に、Z80エミュレータをリセットし、連結されたテープをメモリバッファとして使用して256命令ステップを実行します。すべてのメモリ読み取りと書き込み要求アドレスは連結されたテープの長さ（32バイト）の剰余で計算され、これによりランダムなプログラムによる範囲外アクセスを防ぎます。CPU駆動の自己修正プロセスと並行して、グリッドのランダムなバイトに突然変異が適用されます。

このシンプルなセットアップは、驚くほど複雑な挙動を生み出し、異なるZ80機能を利用する多数の自己複製体世代が出現します。これらの自己複製体の一部は一種の共生生態系を形成し、他は支配権を競います（図12）。我々はしばしば、より能力の高い自己複製体や複製体の集合体がスープを何度も占有する一連の状態遷移のような事象を観察します。

初期の世代はスタックベースのコピーメカニズムを使用します：初期化時にZ80はアドレス空間の終わりにスタックポインタを設定するので、値をスタックにプッシュすることでテープAはテープBに簡単に書き込むメカニズムを得ます。ほとんどの場合、我々はスタックベースの自己複製体の「生態系」の発展を見ますが、最終的には連続したメモリチャンクをコピーできる「LDIR」または「LDDR」命令を利用する自己複製体に置き換わります。我々はz80自己複製体の探索を容易にするためのインタラクティブなラボを作成しました：https://github.com/znah/zff

我々は長テープ設定でも8080 CPUを試しました。これは常に2バイトの繰り返しである複製体を生成するようです。例えば、01 c5 - これは、実行が01で始まる場合、LXI BC, 01c5（01 c5 01）、PUSH BC（c5）に対応します - これはスタックの先頭を01 c5に設定する効果があります。実行がc5で始まる場合、最初のプッシュではBCは0になるので、00 00がメモリに書き込まれます。8080では00はno-opなので、これは無害です。これらの複製体はループしないことに注意してください。長テープBFFでは、ループしない複製体はメモリ全体を占有できません。しかし、これらの複製体は8080では非常にうまく機能します。おそらくこのため、我々は8080でループするバリアントが出現するのを見たことがありません。

4. 議論

本論文では、生命 - 自己複製プログラムの出現と支配的な占有によって識別される - が前生命期から出現する可能性のあるいくつかの計算基盤の例を示しました。我々は、BFのバリアントが、主に自己修正によって、背景突然変異率の有無にかかわらず、異なる次元の原始スープから自発的に自己複製体を作成することを示しました。また、これがより複雑なダイナミクスの始まりであることを逸話的な証拠で示しました。ForthやZ80、8080 CPUなどの異なる言語やパラダイムでも同様の挙動が生じることを示しました。最後に、SUBLEQ様の言語で、自己複製体の自発的な出現を触媒することができなかった反例を示しました。我々の予備的な分析では、SUBLEQ様の言語は機能する初期自己複製体の期待長さがはるかに高いように見えます。我々は、そのような長さが自己複製体が出現する可能性を決定する上で重要な役割を果たしていると考えていますが、それが唯一の要因ではないと予想しています。

我々は、この計算基盤のセットが生命を発見し到達する新しい方法を示していると主張します。そのようなシステムの挙動は、自己触媒ネットワークや生物学的に触発されたシステムとは顕著に異なります。我々の分析は、TierraやAVIDAでの実験のように手作りの自己複製体から始めるのではなく、前生命期から始まります。さらに、我々の初期の探索とTierraやAVIDAなどの類似のシステムで観察されたものは、このようなシステムで出現し繁栄する可能性のある挙動の複雑さの始まりに過ぎないことを示唆しています。

これらの調査からは、さらなる調査が必要ないくつかの未解決の問題が生じます。オープンエンドの計算システムでどの程度の複雑さが自発的に生じる可能性があるのでしょうか？自己複製体の出現を促進または抑制するシステムの特徴的な特性は何でしょうか？このようなシステムの進化を、ますます複雑な機能を開発するように導く方法はあるでしょうか？最後に、これらの計算システムではどのような種類の進化が生じる可能性があるでしょうか？それは自然界で観察されるものと似ているでしょうか、それとも顕著な違いを示すでしょうか？

我々は、これらのアイデアをさらに探求することを楽しみにしており、これが生命が出現する基盤に関係なく、その限界と可能性を理解することにより近づくことを期待しています。

謝辞

Thomas Fischbacher、João Sacramento、Alexander Meulemans、Stan Kerstjensの思慮深いフィードバックに感謝します。