ルール110セル・オートマトン
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/03/03 07:32 UTC 版)
「セル・オートマトン」の記事における「ルール110セル・オートマトン」の解説
現在の状態中央のセルの次の状態0 0 0 * 0 * 0 0 1 * 1 * 0 1 0 * 1 * 0 1 1 * 1 * 1 0 0 * 0 * 1 0 1 * 1 * 1 1 0 * 1 * 1 1 1 * 0 * 例えば「ルール30」と呼ばれるのは、上の表のように時刻t+1における中央のセルの内部状態一覧を並べると0,0,0,1,1,1,1,0となっており、この2進数の数を10進数に直すと30であるためであり、これをウルフラム・コード（英語版）と呼ぶ。 ルール30は「クラス3」の挙動を示し、単純な初期状態からもカオス的な経過を示し、無作為な履歴になっている。 ルール110はライフゲームのように「クラス4」の挙動を示し、完全な無作為でもなく、完全な反復でもない。局所的構造が現れ、様々な複雑な形で相互作用する。1994年ウルフラムの研究助手だったマシュー・クックは、それら構造の一部がチューリング完全性をサポートするのに十分であることを証明した。ルール110は非常に単純な1次元のシステムであり、具体的なことを実行するよう設計するのは困難であるため、この成果は興味深い。この結果からウルフラムはクラス4のセル・オートマトンが本質的にチューリング完全である可能性を示唆した。1998年、セル・オートマトンの学会がサンタフェ研究所で開催され、クックはその成果を発表したが、ウルフラムは A New Kind of Science の出版前にその証明の詳細を公表したくなかったため、証明の詳細は発表されなかった。2004年、Cookの証明がウルフラムの発行する雑誌 Complex Systems (Vol. 15, No. 1) で発表された。実に証明してから10年が経過している。ルール110をベースとして極小の万能チューリングマシンが構築されている。
※この「ルール110セル・オートマトン」の解説は、「セル・オートマトン」の解説の一部です。
「ルール110セル・オートマトン」を含む「セル・オートマトン」の記事については、「セル・オートマトン」の概要を参照ください。
- ルール110セル・オートマトンのページへのリンク
