Von Neumann universal constructor とは

John von Neumannのユニバーサルコンストラクタは、セルオートマトン(CA)環境での自己複製マシンです。それは1940年代にコンピュータを使わずに設計されました。このマシンの基本的な詳細は、フォン・ノイマンの死後、Arthur W. Burksによって1966年に完成されたフォン・ノイマンの本「自己再生オートマトンの理論」に掲載されました。
フォンノイマンの目標は、実行時にそれ自体を複製する抽象マシンを指定することでした。彼の設計では、機械は3つの部分で構成されています:それ自身のための「青写真」、青写真を読むことができ、その青写真によって指定された機械(青写真)を構築する機構、青写真。機構が青写真によって指定された機械を構築するのに使用された後、複写機はその青写真のコピーを作成するために使用され、このコピーは新しい機械に置かれ、元の機械の複製が行われる。いくつかのマシンはこれを後方に行い、青写真をコピーしてマシンを構築します。
彼のマシンをより詳細に定義するために、フォン・ノイマンはセルオートマトンのコンセプトを発明しました。彼が使用したものは、2次元のセルのグリッドで構成されています。セルのグリッドは、いずれの時点でも29状態のいずれかになります。各タイムステップにおいて、各セルは、前のタイムステップにおける周囲のセルの状態に応じてその状態を更新する。これらの更新を管理するルールは、すべてのセルで同じです。
ユニバーサルコンストラクタは、このセルオートマトンのセル状態の特定のパターンです。これには、テープの役割を果たす1行のセルが含まれており、マシンのための「青写真」として役立つ一連の指示をエンコードします。マシンは、これらの命令を1つずつ読み取り、対応するアクションを実行します。命令は、機械に、その「建設腕」を使用して、セルグリッド内の他の場所で、テープなしで機械のコピーを構築するよう指示する。コンテナに同じサイズのコンテナを入れることができないように、テープには同じ長さのテープを作成するための指示を含めることはできません。したがって、マシンには、テープを読み取り、新しく構築されたマシンにコピーを配置する別の「コピーマシン」が含まれています。結果として得られた新しいマシンとテープは古いものと同じですが、もう一度複製を続けます。