フォン・ノイマンの万能構築子

ジョン・フォン・ノイマンの万能構築子は、セルオートマトン(CA) 環境における自己複製機械である。これは 1940 年代にコンピュータを使用せずに設計された。この機械の基本的な詳細は、フォン・ノイマンの著書「自己複製オートマトン理論」に掲載され、フォン・ノイマンの死後、アーサー・W・バークスが 1966 年に完成させた。 ^[2]これは、オートマトン理論、複雑系、人工生命の基礎となるものとみなされている。^{[3] [4]}実際、ノーベル賞受賞者のシドニー・ブレナーは、フォン・ノイマンの自己複製オートマトンに関する研究 (チューリングの計算機に関する研究と共に) は生物学理論の中心であり、「自然機械と人工機械の両方についての思考を統制する」ことができると考えた。^[5]

フォン・ノイマンの目標は、1949 年のイリノイ大学での講義^{[2]で述べられているように、}自然淘汰を受ける生物のように、複雑さが自動的に増大する機械を設計することだった。彼は、機械が進化するために超えなければならない複雑さの閾値は何かと尋ねた。 ^[4]彼の答えは、実行時に自己複製する抽象機械を指定することだった。彼の設計では、自己複製機械は 3 つの部分から構成される。つまり、自分自身の「記述」（「青写真」またはプログラム）、任意の記述を読み取り、その記述にエンコードされた機械（記述なし）を構築できるユニバーサル コンストラクターメカニズム、および任意の記述のコピーを作成できるユニバーサル コピー マシンである。ユニバーサル コンストラクターを使用して記述にエンコードされた新しい機械を構築した後、コピー マシンを使用してその記述のコピーを作成し、このコピーを新しい機械に渡すことで、元の機械の複製が機能し、複製を継続できる。一部の機械は、これを逆に実行し、記述をコピーしてから機械を構築する。重要なのは、自己複製機械は機械自体ではなく、その説明の変異を蓄積することによって進化し、複雑さを増す能力を獲得するということです。^{[4] [5]}

フォン ノイマンは、このマシンをより詳細に定義するために、セル オートマトンの概念を考案しました。彼が使用したセル オートマトンの概念は、2 次元のセルのグリッドで構成されており、各セルは任意の時点で 29 の状態のいずれかを取ることができます。各タイム ステップで、各セルは、前のタイム ステップでの周囲のセルの状態に応じて、自身の状態を更新します。これらの更新を制御するルールは、すべてのセルで同一です。

ユニバーサル コンストラクターは、このセル オートマトン内のセル状態の特定のパターンです。これには、記述として機能するセルの行が 1 つ含まれており (チューリング テープに類似)、マシンの「青写真」として機能する一連の命令がエンコードされています。マシンはこれらの命令を 1 つずつ読み取り、対応するアクションを実行します。命令は、マシンに「構築アーム」(オペレーティング システムのように機能する別のオートマトン^[4] ) を使用して、記述テープなしで、セル グリッド内の別の場所にマシンのコピーを構築するように指示します。コンテナーに同じサイズのコンテナーを含められないのと同じように、記述には同じ長さの記述テープを作成するための命令を含めることはできません。そのため、マシンには、記述テープを読み取り、新しく構築されたマシンにコピーを渡す別のコピー マシンが含まれます。結果として得られるユニバーサル コンストラクターとコピー マシン、および記述テープの新しいセットは古いものと同一であり、再び複製を開始します。

フォン・ノイマンの設計は、伝統的に機械の自己複製の論理的要件の実証であると理解されてきた。^[3]しかし、はるかに単純な機械でも自己複製を実現できることは明らかである。例としては、単純な結晶のような成長、テンプレートの複製、ラングトンのループなどが挙げられる。しかしフォン・ノイマンは、構築、普遍性、進化といったより深遠なものに興味を持っていた。^{[4] [5]}

より単純な自己複製型 CA 構造 (特に、Byl ループとChou–Reggia ループ) は、多様な形式で存在することができないため、進化可能性が非常に限られていることに注意してください。Evoloop などの他の CA 構造はある程度進化可能ですが、それでもオープンエンドの進化をサポートしていません。通常、単純なレプリケータには構築の仕組みが完全には含まれておらず、レプリケータは周囲の環境によってコピーされた情報である程度があります。フォン ノイマン設計は論理的な構築ですが、原理的には物理的なマシンとしてインスタンス化できる設計です。実際、このユニバーサル コンストラクターは、物理的なユニバーサル アセンブラーの抽象的なシミュレーションと見なすことができます。原材料とその可用性に関するさまざまな概念があるため、複製に対する環境の寄与の問題はやや未解決です。

フォン・ノイマンの決定的な洞察は、機械の記述が、万能複写機を介して別々に複製され子孫に受け継がれるが、その記述には二重の用途があるということである。つまり、複製における構築メカニズムの能動的な構成要素であると同時に、受動的な複製プロセスのターゲットでもあるということである。この役割を担うのが、フォン・ノイマンの万能構築機と万能複写機の組み合わせにおける記述（チューリングの指示テープに似ている）である。[ 4 ]^万能構築機と複写機の組み合わせに指示テープを加えることで、i) 自己複製、および ii) 生物に見られるオープンエンドの進化、つまり複雑性の成長が概念化され、形式化される。^[3]

この洞察は、ワトソンとクリックによるDNA分子の構造の発見と、それが細胞内で個別に翻訳され複製される方法の発見に先立っていたため、なおさら注目に値する。ただし、これは、 DNAが生体内の遺伝情報の分子キャリアであることを確認したエイブリー・マクラウド・マッカーティの実験の後のことである。 ^{[6] DNA分子は、その指示（}翻訳）を実行し、新しく構築された細胞のためにDNAをコピー（複製）する別々のメカニズムによって処理されます。オープンエンドの進化を達成できるのは、自然界と同じように、遺伝子テープのコピーにおけるエラー（突然変異）がオートマトンの実行可能な変種につながり、それが自然選択によって進化する可能性があるという事実にあります。^[4]ブレナーは次のように述べています。

チューリングはプログラム内蔵型コンピュータを発明し、フォン・ノイマンは記述がユニバーサル・コンストラクタとは別であることを示した。これは簡単なことではない。物理学者エルヴィン・シュレーディンガーは1944年の著書『生命とは何か』でプログラムとコンストラクタを混同し、染色体を「建築家の設計図と建築者の技巧が一体となったもの」とみなした。これは間違いである。コード・スクリプトには実行機能の記述のみが含まれており、機能自体は含まれていない。^[5]

— シドニー・ブレナー

フォン・ノイマンの目標は、1949年のイリノイ大学での講義^{[2]で述べられているように、}自然淘汰を受ける生物と同様に、複雑さが自動的に増大する機械を設計することだった。彼は、機械が進化し複雑さを増大するためには、超えなければならない複雑さの閾値は何かと問いかけた。 ^{[4] [3]} 彼の「原理証明」設計は、それが論理的に可能であることを示した。汎用プログラマブル（「ユニバーサル」）コンストラクタと汎用コピー機を分離するアーキテクチャを使用することで、機械の記述（テープ）が自己複製において突然変異を蓄積し、より複雑な機械を進化させる方法を示した（下の図はこの可能性を示している）。これは非常に重要な結果である。なぜなら、それ以前には、そのような機械の存在には根本的な論理的障壁があると推測されていたかもしれないからである。その場合、進化し複雑さを増大する生物は、従来理解されているような「機械」ではあり得ない。フォン・ノイマンの洞察は、生命をチューリングマシンとして考えるというもので、チューリングマシンも同様に、メモリテープから分離された状態決定型の機械「ヘッド」によって定義される。^[5]

実際には、フォン・ノイマンが追求した特定のオートマトン実装を考えると、機械があまりにも脆弱であるため、進化のダイナミクスはあまり生み出されないという結論に達します。ほとんどの摂動は機械を事実上崩壊させます。^{[3]したがって、イリノイ大学の講義で概説された概念モデル[2]}は、機械が原理的にどのように進化できるかを示しているため、今日ではより興味深いものとなっています。^{[7] [4]}この洞察は、前述のように、このモデルがDNA分子の構造の発見に先行していたため、さらに注目に値します。^[6]フォン・ノイマンの設計では、自己複製自体に関与しないサブシステム（の記述）において、より複雑性に向かう突然変異が発生する必要があると考えられていることも注目に値する。これは、フォン・ノイマンが、複製に直接関与しないすべての機能を実行すると考えた追加のオートマトンDによって概念化されたものである（上の図のフォン・ノイマンの進化能力を持つ自己複製オートマトンシステムを参照）。実際、生物では遺伝コードの非常に小さな変化しか観察されておらず、これは、万能構築子（ A ）とコピー機（ B ）自体は進化せず、すべての進化（および複雑性の成長）はオートマトン D に委ねられるというフォン・ノイマンの理論と一致している。 [ 4 ]フォン・^ノイマンは未完の研究で、自己複製機械の理論から生態学的および社会的相互作用の進化を理解することに向けて、自己複製機械間の衝突と相互作用についても簡単に考察している。^{[2] : 147}

オートマトン理論では、エデンの園のパターン(先行するものがない構成)が存在するため、ユニバーサル コンストラクターの概念は重要になります。ただし、簡単に定義すると、ユニバーサル コンストラクターは、非励起 (静止) セルの任意の有限パターンを構築できます。

アーサー・バークスらはフォン・ノイマンの研究を拡張し、フォン・ノイマンの自己複製装置の設計と動作に関するより明確で完全な詳細を提供しました。JW サッチャーの研究は特に注目に値します。彼は設計を大幅に簡素化したからです。しかし、彼らの研究は、自己複製を実証できる構成の細胞ごとの完全な設計には至りませんでした。

レナート・ノビリとウンベルト・ペサヴェントは、フォン・ノイマンの研究からほぼ50年後の1995年に、初めて完全に実装された自己複製セルオートマトンを発表しました。^{[1] [8]彼らはフォン・ノイマンの元の}29状態仕様の代わりに32状態のセルオートマトンを使用し、より簡単な信号交差、明示的なメモリ機能、よりコンパクトな設計を可能にするように拡張しました。彼らはまた、元の29状態CA内の汎用コンストラクタの実装も発表しましたが、完全な複製はできませんでした。構成はテープを複製することも、子孫をトリガーすることもできず、構成は構築することしかできませんでした。^{[8] [9]}

2004年にD. Mangeらはフォン・ノイマンの設計と一致する自己複製装置の実装を報告した。^[10]

2007年、Nobiliはランレングス符号化を使用してテープサイズを大幅に削減する32状態の実装を公開しました。 ^[11]

2008年、ウィリアム・R・バックリーは、フォン・ノイマンのオリジナルの29状態セルオートマトン内の自己複製子である2つの構成を発表しました。^[9]バックリーは、フォン・ノイマンの29状態セルオートマトン内の信号の交差は、自己複製子の構築には必須ではないと主張しています。^[9]バックリーはまた、進化の目的のために、各複製子は複製後に元の構成に戻り、（理論上）複数のコピーを作成できるようにする必要があると指摘しています。発表された1995年のノビリ・ペサベントの設計はこの要件を満たしていませんが、2007年のノビリの設計は満たしています。同じことはバックリーの構成にも当てはまります。

2009 年、バックリーはゴリーと共同で、フォン ノイマン 29 状態セルラー オートマトンの第 3 の構成を発表しました。この構成では、全体的な自己複製、または部分的な構築による自己複製のいずれかを実行できます。この構成では、フォン ノイマン 29 状態セルラー オートマトン内の自己複製子の構築に信号の交差は不要であることも実証されています。

2002年にCL Nehanivが、また2004年にY. Takadaらが、同期セルオートマトンではなく非同期セルオートマトン上に直接実装されたユニバーサルコンストラクタを提案した。 ^{[12] [13]}

フォン・ノイマンの定義によれば、普遍的構成は受動的な構成のみを構成する。したがって、普遍的構成の概念は単なる文学的（またはこの場合は数学的）装置にすぎない。この概念は、うまく構築された機械は自己複製を行う可能性があるなどの他の証明を容易にしたが、普遍的構成自体は単に最小限のケースで想定されただけだった。この基準の下での普遍的構成は自明である。したがって、ここで示したすべての構成は任意の受動的な構成を構築できるが、ゴーマンが考案したリアルタイムのクロッシングオルガンを構築できるものはない。^[9]

フォン ノイマンの自己複製マシンのすべての実装は、コンピュータ上で実行するためにかなりのリソースを必要とします。たとえば、上に示した Nobili-Pesavento の 32 状態の実装では、マシンの本体は 6,329 個の空でないセル (サイズ 97x170 の長方形内) のみですが、145,315 個のセルの長さのテープが必要であり、複製には 630 億のタイムステップがかかります。1 秒あたり 1,000 タイムステップで動作するシミュレーターでは、最初のコピーを作成するのに 2 年以上かかります。最初の実装が公開された 1995 年には、作成者は自分のマシンが複製されるのを見たことがありませんでした。しかし、2008 年に、ハッシュライフアルゴリズムが拡張され、 Gollyの 29 状態および 32 状態のルールセットがサポートされるようになりました。現代のデスクトップ PC では、かなりの量のメモリが必要になりますが、複製には数分しかかかりません。

• 
  29 状態の読み取りアームの例。

• コッドのセルオートマトン
• ラングトンループ
• ノービリセルオートマトン
• Quine、出力として自分自身を生成するプログラム
• サンタクロースマシン
• ワイヤーワールド

• ジョン・フォン・ノイマンの 29 状態セルオートマトンをDon Hopkinsが OpenLaszlo に実装