コッドのセルオートマトン
コッドのセルオートマトン（Codd's Cellular Automaton ）は、 1968年にイギリスのコンピュータ科学者エドガー F. コッドによって考案されたセルオートマトン（CA）である。これは、フォン ノイマンの CAの計算および構築の普遍性を、状態数が少ない 8 (29 ではなく 8) で再現するように設計された。コッドは、フォン ノイマンのユニバーサル コンストラクターと同様の方法で、自身の CA で自己複製マシンを作成できることを示したが、完全な実装は示さなかった。
歴史
1940年代から50年代にかけて、ジョン・フォン・ノイマンは次のような問題を提起した。[ 1 ]
- オートマトンが自己複製できるようにするには、どのような論理構成が必要ですか?
彼は29の状態を持つセルオートマトンと、それを用いたユニバーサルコンストラクタを構築することに成功した。コッドはフォン・ノイマンの研究を基に、8つの状態を持つより単純な機械を発見した。[ 2 ]これによりフォン・ノイマンの疑問は修正された。
- オートマトンが自己複製できるようにするには、どのような論理構成が必要ですか?
コッドの研究から3年後、エドウィン・ロジャー・バンクスは博士論文の中で、やはり普遍的な計算と構築が可能な4状態のセルオートマトンを示したが、やはり自己複製マシンは実装していなかった。[ 3 ]ジョン・デボアは、1973年の修士論文で、コッドのルールを微調整してコッドの設計を大幅に縮小した。デボアの設計のシミュレーションは、1992年の第3回人工生命会議で示され、子孫パターンの構築と活性化の最終段階を示したが、完全な自己複製は、2000年代になってGollyを使用して初めてシミュレートされた。クリストファー・ラングトンは、1984年にコッドのセルオートマトンに別の微調整を加えてラングトンのループを作成し、以前のルールで自己複製に必要だったセルよりもはるかに少ないセルで自己複製を示したが、普遍的な計算と構築の能力を削除するという犠牲を払った。[ 4 ]
CAルールセットの比較
| カリフォルニア州 | 州の数 | 対称性 | 計算と構築の普遍性 | 自己複製機械のサイズ |
|---|---|---|---|---|
| フォン・ノイマン | 29 | なし | はい | 130,622個の細胞 |
| コッド | 8 | 回転 | はい | 2億8312万6588個の細胞[ 5 ] |
| デボア | 8 | 回転 | はい | 94,794個の細胞 |
| バンクスIV（バンクスIVセルオートマトン） | 2 - 4 [ 6 ] [ 3 ] | 回転と反射 | はい | 約100,000,000,000個の細胞 |
| ラングトンループ | 8 | 回転 | いいえ | 86個のセル |
仕様
コッドの CA には、回転対称性を持つフォン ノイマン近傍によって決定される 8 つの状態があります。
下の表は、様々なタスクを実行するために必要な信号列を示しています。一部の信号列は、干渉を避けるために、配線上で2つの空白（状態1）で区切る必要があります。そのため、上の画像で使用されている「拡張」信号列は、ここでは「70116011」と表示されています。
| 目的 | 信号列車 |
|---|---|
| 伸ばす | 70116011 |
| 左に延長 | 4011401150116011 |
| 右に拡張 | 5011501140116011 |
| 撤回する | 4011501160116011 |
| 左に引っ込める | 5011601160116011 |
| 右引き込み | 4011601160116011 |
| マーク | 701160114011501170116011 |
| 消去する | 601170114011501160116011 |
| センス | 70117011 |
| キャップ | 40116011 |
| 注入シース | 701150116011 |
| トリガーを挿入 | 60117011701160116011 |
ユニバーサルコンピュータコンストラクター
コッドは、ワンのWマシンをベースに、セルオートマトンで自己複製するコンピュータを設計した。しかし、その設計はあまりにも巨大だったため、2009年にティム・ハットンが明示的な構成を構築するまで実装は実現しなかった。[ 5 ]コッドの設計にはいくつかの小さな誤りがあったため、ハットンの実装は構成とルールセットの両方において若干異なっている。
参照
参考文献
- ^フォン・ノイマン、ジョン、バークス、アーサー・W. (1966). 「自己増殖オートマトン理論」 . www.walenz.org. 2008年1月5日時点のオリジナルよりアーカイブ。 2012年1月28日閲覧。
- ^コッド、エドガー・F. (1968).セルラーオートマトン. アカデミック・プレス, ニューヨーク.
- ^ a b Banks, Edwin (1971).セルオートマトンにおける情報処理と伝送. MIT機械工学科博士論文.
- ^ Langton, CG (1984). 「セルオートマトンにおける自己複製」(PDF) . Physica D: 非線形現象. 10 ( 1–2 ): 135– 144. Bibcode : 1984PhyD...10..135L . doi : 10.1016/0167-2789(84)90256-2 . hdl : 2027.42/24968 .
- ^ a b Hutton, Tim J. (2010). 「Coddの自己複製コンピュータ」（PDF） . Artificial Life . 16 (2): 99– 117. doi : 10.1162/artl.2010.16.2.16200 . PMID 20067401. S2CID 10049331.オリジナル（PDF）から2012年2月5日にアーカイブ。 2010年8月1日閲覧。
- ^ 「ロジャー・バンクスによるセルオートマトンにおける普遍計算の証明」。
外部リンク
- ルールテーブル リポジトリには、Codd の CA の遷移テーブルが含まれています。
- Golly - Codd の CA に加えて、Game of Lifeやその他のルールセットもサポートします。
- 完全なマシン (13MB)と詳細情報をダウンロードしてください。
- [1]はバンクスIVについてさらに詳しく述べています。
