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

出典: フリー百科事典『ウィキペディア（Wikipedia）』

コッドのセル・オートマトン（Codd's cellular automaton）は、1968年、イギリス人計算機科学者エドガー・F・コッドが考案したセル・オートマトン。

[編集] 解説

1940年代、ジョン・フォン・ノイマンは以下のような問題を提示した:

自身を複製するのに十分なオートマトンとはどのような論理構成か？

彼は方形グリッドと29の状態を持った Universal Constructor を構築した。コッドはもっと単純な 8 状態だけからなるマシンを発見した。したがってフォン・ノイマンの問題は次のように修正されなければならなくなった:

自身を複製するのに「必要十分な」オートマトンとはどのような論理構成か？

コッドのセル・オートマトンは 5 近傍、8 状態のセル・オートマトンである。そのコンセプトは空のフィールド(0)上の経路(1)に基づいている。経路は信号の通る導線であり、4 から 7 の数字で構成され、後ろには 1 個の 0 が置かれて転送の方向を定義している。信号が空のフィールド（0で満たされた空間）に漏れ出すのを防ぐため、経路の周囲は 2 状態の線で被覆されている。このような基本構成はその後の多くのセル・オートマトンでも採用されている。例えば、ワイヤワールドなどがある。

クリストファー・ラングトンは1984年、コッドのセル・オートマトンをさらに単純化したものを考案した。ラングトンのループと呼ばれ、同様に自己複製機能を備えている。

[編集] 参考文献

E. F. Codd, Cellular Automata (Academic Press, New York, 1968年)
Christopher G. Langton, Self-Reproduction in Cellular Automata, Physica 10D (1984年)
J. v. Neumann, The Theory of Self-Reproducing Automata. In Essays on Cellular Automata, A. W. Burks, ed. (Univ. of Illinois 1968年)