コッドのセルオートマトン

コッドのセルオートマトンとは、 1968年にイギリスのコンピュータ科学者エドガー・F・コッドが考案したセルオートマトン（CA）である。フォン・ノイマンのCAの計算および構築の普遍性を再現するように設計されたが、状態数は29ではなく8であった。コッドは、フォン・ノイマンの普遍構築子と同様の方法で、CAで自己複製マシンを作成できることを示したが、完全な実装は示さなかった。

1940年代から50年代にかけて、ジョン・フォン・ノイマンは次のような問題を提起した。^[1]

• オートマトンが自己複製できるようにするには、どのような論理構成で十分でしょうか?

彼は29の状態を持つセルオートマトンとそれを用いたユニバーサルコンストラクタを構築することができた。コッドはフォン・ノイマンの研究を基に、8つの状態を持つより単純なマシンを発見した。^[2]これによりフォン・ノイマンの疑問は修正された。

• オートマトンが自己複製できるようにするには、どのような論理構成が必要ですか?

コッドの研究から3年後、エドウィン・ロジャー・バンクスは博士論文で4状態のCAを示したが、これもまた普遍的な計算と構築が可能であったが、自己複製マシンは実装していなかった。^[3]ジョン・デボアは1973年の修士論文でコッドのルールを微調整し、コッドの設計を大幅に縮小した。デボアの設計のシミュレーションは1992年の第3回人工生命会議で実演され、子孫パターンの構築と活性化の最終段階を示したが、完全な自己複製は2000年代になってGollyを使用して初めてシミュレートされた。クリストファー・ラングトンは1984年にコッドのセルオートマトンに別の微調整を加えてラングトンのループを作成し、以前のルールで自己複製に必要だったよりもはるかに少ないセルで自己複製を示したが、普遍的な計算と構築の能力が削除された。^[4]

Codd の CA には、回転対称性を持つフォン ノイマン近傍によって決定される 8 つの状態があります。

以下の表は、さまざまなタスクを実行するために必要な信号列を示しています。一部の信号列は、干渉を避けるためにワイヤ上の 2 つの空白 (状態 1) で区切る必要があるため、上の画像で使用されている「拡張」信号列は、ここでは「70116011」として表示されます。

コッドは、ワンのWマシンをベースに、セルオートマトンで自己複製するコンピュータを設計した。しかし、その設計は巨大だったため、2009年にティム・ハットンが明示的な構成を構築するまで実装されなかった。^[5]コッドの設計には小さな誤りがいくつかあったため、ハットンの実装は構成とルールセットの両方でわずかに異なっている。

• 人工生命
• セルオートマトン
• コンウェイのライフゲーム
• ラングトンループ
• フォン・ノイマン型セルオートマトン
• ワイヤーワールド

• ルール テーブル リポジトリには、Codd の CA の遷移テーブルが含まれています。
• Golly - Codd の CA とGame of Lifeおよびその他のルールセットをサポートします。
• 完全なマシン (13MB) と詳細情報をダウンロードしてください。
• [1]はバンクスIVについてさらに詳しく示しています。