コッドのセル・オートマトン
1940年代から50年代にかけて、ジョン・フォン・ノイマンは以下のような問題を提示した:
自身を複製するのに十分なオートマトンとはどのような論理構成か?
彼は29の状態を持つセル・オートマトン(英語版)を構築し、それを使って universal constructor を生み出した。1968年、コッドはもっと単純な 8 状態だけからなるマシンを発見した。したがってフォン・ノイマンの問題は次のように修正されなければならなくなった:
自身を複製するのに「必要十分な」オートマトンとはどのような論理構成か?
コッドのCAの発表から3年後、Edwin Roger Banks が博士論文で計算および構築の万能性を示す4状態のCAを提示した。ただし、コッドもBanksもそのCA上の自己複製機械の構成を示していない。1973年、John Devore が修士論文でコッドのCAを改良して大幅に単純化し、当時のコンピュータ上で実装可能な規模にした。しかし、自己複製のためのデータテープは非常に長く、実際に自己複製が確認できたのは Golly というプログラムが開発されてからのことである。クリストファー・ラングトンは1984年、コッドのセル・オートマトンをさらに単純化したものを考案した。ラングトンのループと呼ばれ、はるかに少ないセル数で自己複製機能を実現しているが、計算と構築の万能性は失われている。