自己再製オートマトン

ある世代を経た後、元の状態に戻るオートマトンのこと。

自己再製オートマトンはジョン・フォン・ノイマンの自己再製機械問題の証明に用いられ、最終的に彼の同僚だったアーサー・バークス(Arthur W.Burks)が受け継ぎ、1966(昭和41)年に編著の「自己再製オートマトンの理論(Teoryof Self-Reproducing Automata)」という題名の本の中で証明されている。

また、コンウェイはバールカンプ(E.Berlekamp)、ガイ(R.Guy)との共著本"Winning Ways" の中でライフゲームにおける自己再製を証明し、実証には懸賞金をかけMITの学生グループが自己再製するパターンを発見し、懸賞金をゲットしている。

ノイマンの記述した自己再製オートマトンについて
29種類のセル(興奮不能状態1, 静止しているが興奮可能な状態20, 興奮し
た状態8)が, チューリングマシンでテープを読み込みながら状態変化を繰
り返し, 初期のセル配置と同じ配置のセルを別の場所に作り上げる(自己
複製する)というもの.
  
セルの状態変化のルールは以下の2つ.
1. 各々のセルが, ある時点での自分の状態と回り四つのセルの状態から,
   規則表に従い自分自身の次の時点での状態を決める.
2. これを, 時系列に従い繰り返す.
  
なお, 1. の規則表はセル自身により読みこまれる.

通信用語の基礎知識検索システム WDIC Explorer Version 7.04a (27-May-2022)