可逆型
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/03/03 07:32 UTC 版)
現在状態から1つ前の状態（プレイメージ）が一意に求められるセル・オートマトンを「可逆的」(reversible) であるという。セル・オートマトンを状態から状態への関数と考えると、可逆性はその関数が全単射であることを意味する。可逆型のセル・オートマトンは、時間を遡った際の挙動もセル・オートマトンとして記述できる。これは、セル・オートマトンを位相幾何学的に説明したカーティス-ヘドランド-リンドンの定理（英語版）の帰結である。可逆でない有限のセル・オートマトンには、どんな状態からも絶対生成（到達）できない配置が存在する。そのような配置を「エデンの園配置」と呼ぶ。換言すれば、エデンの園パターンにはプレイメージが存在しない。 1次元のセル・オートマトンについては、プレイメージを探すアルゴリズムが知られていて、各ルールについて可逆的かそうでないかは既に判明している。2次元以上のセル・オートマトンについては、任意のルールの可逆性は決定不能であることが証明されている。Jarkko Kari による証明は、ワンのタイルのタイル並べ問題と関連している。 可逆型セル・オートマトンは、熱力学の法則に従う気体や液体の力学現象のシミュレーションに使われることが多い。その場合のセル・オートマトンは特別に可逆性を持つよう設計される。この種のシステムの研究者としてトマソ・トフォリやノーマン・マーゴラス（英語版）らがいる。意識的に可逆型セル・オートマトンを作る手法はいくつか存在する。二階セル・オートマトン（英語版）やブロック・セル・オートマトン（英語版）がそれで、どちらもセル・オートマトンの定義に何らかの修正を施す。これらは厳密には上に挙げたようなセル・オートマトンの定義から外れているが、十分に大きな近傍と多数の状態を持つ従来型のセル・オートマトンでエミュレートできることが判っており、従来型のセル・オートマトンのサブセットと見なすことができる。逆に全ての可逆型セル・オートマトンはブロック・セル・オートマトンでエミュレートできる。
※この「可逆型」の解説は、「セル・オートマトン」の解説の一部です。
「可逆型」を含む「セル・オートマトン」の記事については、「セル・オートマトン」の概要を参照ください。
- 可逆型のページへのリンク
