可逆セルオートマトン

可逆セルオートマトンとは、すべての構成に固有の先行構成があるセルオートマトンです。つまり、セルの規則的なグリッドであり、各セルには有限の状態セットから抽出された状態が含まれます。また、すべてのセルをその近傍の状態に基づいて同時に更新するルールがあり、更新前の任意のセルの前の状態は、すべてのセルの更新された状態から一意に決定できます。可逆セルオートマトンの時間反転ダイナミクスは、常に別のセルオートマトンルールによって記述でき、おそらくはるかに大きな近傍で記述できます。

可逆なセルオートマトンルールを定義する方法はいくつか知られています。これには、各更新でセルをブロックに分割し、各ブロックに個別に可逆関数を適用するブロックセルオートマトン法や、更新ルールがオートマトンの前 2 つのステップの状態を組み合わせる2 次セルオートマトン法などがあります。オートマトンがこれらの方法のいずれかで定義されておらず、代わりにルールテーブルとして与えられている場合、ブロックセルオートマトンと 1 次元セルオートマトンでは可逆かどうかをテストする問題は解決可能ですが、他の種類のセルオートマトンでは決定できません。

可逆セルオートマトン は、超低電力コンピューティングデバイスにつながる可能性のある技術である可逆コンピューティングの自然なモデルを形成します。量子力学の原理を使用して計算を実行する方法の 1 つである量子セルオートマトンは、多くの場合、可逆であることが求められます。さらに、理想気体中の粒子の動きや磁荷の配列のイジングモデルなど、物理モデリングにおける多くの問題は、自然に可逆であり、可逆セルオートマトンによってシミュレートできます。

可逆性に関連する特性は、構成空間全体では可逆ではないが、構成空間のサブセットをアトラクターとして持つセルオートマトンの研究にも使用できます。アトラクターには、最初はランダムだったすべての構成が収束します。スティーブン・ウルフラムは、「アトラクター上では、どんなシステムでも、たとえ可逆的な基本ルールがなくても、ある意味では近似的な可逆性を示すはずです」と述べています。^[1]

セルオートマトンの定義は、セル（多くの場合、1次元または2次元配列）、各セルに格納できる値または状態の有限集合、各セルを隣接するセルの有限集合に関連付ける近傍、およびすべてのセルの値が隣接するセルの値に応じて同時に更新される更新規則です。最も単純なセルオートマトンには、1次元配列のセルがあり、各セルは2進値（0または1）を保持できます。各セルには、そのセルとその両側にある最も近い2つのセルのみで構成される近傍があります。これらは基本セルオートマトンと呼ばれます。^[2] このようなオートマトンの更新規則によって各セルが常に同じ状態に留まる場合、オートマトンは可逆的です。つまり、各セルの以前の状態と現在の状態は同じであるため、すべてのセルの以前の状態を現在の状態から復元できます。同様に、更新規則によってすべてのセルの状態が 0 から 1 に、またはその逆に変化したり、セルが固定された隣接セルの状態をコピーしたり、状態をコピーしてから値を反転したりする場合、その規則は必然的に可逆的です。^[3] Toffoli & Margolus (1990) は、各セルの状態が 1 つの隣接セルの以前の状態のみに依存するこのようなタイプの可逆セルオートマトンを「自明」と呼んでいます。その単純さにもかかわらず、各セルが隣接セルの状態をコピーする更新規則は、記号力学の理論では重要であり、シフトマップとして知られています。^[4]

もう少し自明でない例として、セルが再び 1 次元配列を形成し、各状態が順序付けられたペア( l、r ) であり、左側部分lと右側部分rで構成され、それぞれが可能な値の有限集合から抽出されるとします。セルの左側部分をその左側の隣接セルの左側部分に、セルの右側部分をその右側の隣接セルの右側部分に設定する遷移関数を定義します。つまり、左側の隣接セルの状態が( a、b )で、右側の隣接セルの状態が( c、d )である場合、セルの新しい状態は、方程式( a、b ) × ( c、d ) = ( a、d )で定義されるペアワイズ演算× を使用してこれらの状態を組み合わせた結果です。この構築の例が図に示されています。図では、左側部分が図形としてグラフィカルに表現され、右側部分が色として表現されています。この例では、各セルは、左側の隣接セルの形状と右側の隣接セルの色で更新されます。そして、このオートマトンには可逆性があります。つまり、各ペアの左側の値は右に移動し、右側の値は左に移動するため、各セルの以前の状態は、隣接するセルでこれらの値を探すことによって復元できます。このオートマトンの状態のペアを組み合わせるために使用される操作×は、長方形バンドと呼ばれる代数構造を形成します。^[5]

10進数の2倍または5倍の乗算は、セル（10進数の10桁）ごとに10の状態を持つ1次元の可逆セルオートマトンで実行できます。積の各桁は、与えられた数の2桁の近傍、つまり同じ位置の桁と1つ右の桁の桁のみに依存します。より一般的には、すべての素因数が b の素因数でもある乗数または除数 x による、任意の基数 b の二重 無限桁シーケンスの乗算または除算は、限られた数の近傍桁のみに依存し、乗法逆数が存在するため可逆であるため、セルオートマトンを形成する演算です。^[6]他の値による乗算（たとえば、10進数の3倍）は可逆のままですが、結果の1桁を決定するために必要な初期値の桁数に固定の上限がないため、セルオートマトンを定義しません。

非自明な可逆的な基本セルオートマトンはありません。^{[7]しかし、}ルール 90や排他的論理和関数に基づく他の基本セルオートマトンではニアミスが提供されます。ルール 90 では、各セルの状態は、その 2 つの隣接セルの前の状態の排他的論理和です。この排他的論理和の使用により、遷移ルール​​は局所的に可逆になり、つまり、このルールによって任意の連続した状態のサブシーケンスを生成できます。ルール 90 は可逆セルオートマトンルールではありません。ルール 90 では、セルの完全な配列への状態の割り当てごとに、正確に 4 つの先行候補が存在するのに対し、可逆ルールでは構成ごとに正確に 1 つの先行候補が存在する必要があるためです。^[8]

最も有名なセルオートマトンルールの1つであるコンウェイのライフゲームは可逆的ではありません。たとえば、完全に消滅するパターンが多数あるため、すべてのセルが死んでいる構成には多くの先行パターンがあり、先行パターンのないエデンの園のパターンもあります。ただし、発明者のトマソ・トフォリとノーマン・マーゴラスによって「クリッターズ」と呼ばれる別のルールは可逆的であり、ライフと同様の動的動作を示します。^[9]

クリッターズルールはブロックセルオートマトンであり、各ステップでオートマトン内のセルが 2×2 のブロックに分割され、各ブロックは他のブロックとは独立して更新されます。その遷移関数は、正確に 2 つのライブセルを持たないブロック内のすべてのセルの状態を反転し、さらに、正確に 3 つのライブセルを持つブロックを 180° 回転させます。この関数は可逆であるため、これらのルールによって定義されるオートマトンは可逆セルオートマトンです。^[9]

死んだ細胞の大きな領域の中心にあるランダムな細胞の小さなフィールドから始めると、生命のグライダーに似た多くの小さなパターンが中央のランダムな領域から逃げ出し、互いに相互作用します。クリッターのルールは、速度の異なるより複雑な宇宙船や、無限に異なる周期を持つ振動子もサポートできます。 ^[9]

自動的に可逆なセルオートマトンルールを構築するための一般的な方法がいくつか知られています。

ブロックセルオートマトンとは、各タイムステップでオートマトン内のセルが合同なサブセット（ブロックと呼ばれる）に分割され、各ブロックに同じ変換が独立して適用されるオートマトンである。通常、このようなオートマトンでは、ブロックへの分割が複数回行われ、システムの異なるタイムステップでこれらの分割が切り替わる。^[10]この設計でよく使用される形式は、マーゴラス近傍と呼ばれ、オートマトン内のセルが正方形のグリッドを形成し、各ステップでより大きな 2 × 2 の正方形ブロックに分割される。あるタイムステップでのブロックの中心は、次のタイムステップでは 4 つのブロックの角になり、その逆も同様である。このように、各 2 × 2 の 4 つのセルは、前の分割の 4 つの異なる 2 × 2 の正方形に属する。^[11] 上で説明したクリッターズルールは、このタイプのオートマトンの例である。

ブロックセルオートマトン用の可逆ルールの設計と、与えられたルールが可逆かどうかを判断するのは簡単です。ブロックセルオートマトンが可逆であるためには、オートマトンの各ステップで個々のブロックに適用される変換自体が可逆であることが必要かつ十分です。ブロックセルオートマトンが可逆である場合、そのダイナミクスの時間反転バージョンは、同じブロック構造を持つブロックセルオートマトンとして記述することもできます。ブロックへのセルの分割の時間反転シーケンスを使用し、各ブロックの遷移関数は元のルールの逆関数です。 ^[10]

Toffoli (1977) は、不可逆なd次元セルオートマトンルールを可逆な( d + 1)次元ルールに埋め込む方法を示しました。新しい可逆ルールの各d次元スライスは、元のルールの単一の時間ステップをシミュレートします。このようにして、Toffoli は、任意のチューリングマシンをシミュレートする機能など、不可逆セルオートマトンが持つ多くの機能が可逆セルオートマトンにも拡張できることを示しました。

Toffoli が推測し、Hertling (1998) が証明したように、Toffoli の方法によって発生する次元の増加は、その一般性に対する必要な代償です。つまり、埋め込みの平行移動不変性などの軽度の仮定の下では、エデンの園を持つセルオートマトンを可逆セルオートマトンに埋め込むと、必ず次元が増加します。

Morita (1995) は、Hertling の仮定に従わず、次元を変更しない別のタイプのシミュレーションについて説明しています。Morita の方法は、セルとそのすべての隣接セルが静止している場合、次のステップでもセルが静止したままになるような、「静止」または「デッド」状態がある任意の不可逆オートマトンについて、有限構成をシミュレートできます。シミュレーションでは、元の不可逆オートマトンと同じ次元の可逆ブロック セル オートマトンを使用します。シミュレートされたオートマトンで不可逆なステップによって破壊される情報は、代わりに構成から、シミュレートするオートマトン内の無限静止領域に送られます。このシミュレーションでは、シミュレートされたオートマトンのすべてのセルが同時に更新されるわけではありません。むしろ、1 つのステップをシミュレートする時間は、シミュレートされる構成のサイズに比例します。それでも、シミュレーションでは、すべてのセルが同時に更新されているかのように、シミュレートされたオートマトンの動作が正確に保持されます。この方法を用いると、1次元の可逆セルオートマトンでも普遍的な計算が可能であることを示すことができる。^[12]

2 次セルオートマトン技法は、任意のセルオートマトンを可逆セルオートマトンに変換する手法で、エドワード フレドキンによって発明され、1984 年に他の数人の著者によって初めて発表されました。^{[13]この技法では、時刻}tにおけるオートマトンの各セルの状態は、時刻t − 1における近傍と時刻t − 2における自身の状態の両方の関数です。具体的には、オートマトン遷移関数は、時刻t − 1における各近傍を状態セット上の順列にマッピングし、次にその順列を時刻t − 2 の状態に適用します。オートマトンを逆に動かすには、各近傍を逆順列にマッピングし、同じ手順で進めます。^[14]

バイナリ値の状態（0 または 1）を持つオートマトンの場合、状態には 2 つの可能な順列（恒等順列と 2 つの状態を入れ替える順列）しか存在せず、それ自体がバイナリ値の状態の排他的論理和として表される。このように、従来の 2 値セルオートマトンはすべて、従来のオートマトン遷移関数を時刻t − 1 の状態に適用し、これらの状態と時刻t − 2 の状態の排他的論理和を計算して時刻tの状態を決定することで、 2 次セルオートマトン規則に変換できる。ただし、このようにして決定された可逆セルオートマトンの動作は、定義の元となったセルオートマトンの動作とはまったく似ていない可能性がある。^[14]

任意の2次オートマトンは、2次オートマトンの連続する時間ステップの状態のペアを従来のセルオートマトンの各状態に結合することによって、遷移関数が前の単一の時間ステップのみに依存する従来のセルオートマトンに変換することができる。^[14]

Patt (1971) が発見した 1 次元セルオートマトンでは、4 つの連続したセルからなる近傍を使用しています。このオートマトンでは、セルはパターン「0?10」の「?」位置を占めるたびに状態を反転します。このようなパターンは 2 つ重なり合うことはできないため、反転したセルを囲む同じ「風景」が遷移後も存在し続けます。次のステップでは、同じ「?」位置にあるセルが再び反転し、元の状態に戻ります。したがって、このオートマトンはその逆であり、可逆的です。Patt は、小さな近傍を持つ 2 状態 1 次元セルオートマトンをすべて総当たりで探索しました。この探索により、このオートマトンが発見され、これが可能な限り最も単純で非自明な 1 次元 2 状態可逆セルオートマトンであることが示されました。 3セル近傍を持つ非自明な可逆2状態オートマトンはなく、4セル近傍を持つすべての2状態可逆オートマトンはすべてパットオートマトンの単純な変種である。^[15]

パットのオートマトンを振り返ってみると、可逆セルオートマトンを設計するための「保存されたランドスケープ」技法の 1 つの例として考えることができます。この技法では、セルの状態の変化は、それ自体は状態を変化させない一連の隣接セル間のパターンによってトリガーされます。このように、同じパターンの存在は、オートマトンの時間反転ダイナミクスの逆の変化をトリガーするために使用できます。パットのオートマトンは非常に単純なダイナミクスを持っています (すべての構成の循環シーケンスの長さは 2 です) が、同じ保存されたランドスケープ技法を使用して複数のトリガーパターンを使用するオートマトンでは、より複雑な動作が可能です。特に、任意の 2 次セルオートマトンをシミュレートできます。^[15]

ミラーとフレドキン（2005）のSALTモデルは、保存されたランドスケープ技術の特殊なケースです。このモデルでは、整数グリッドのセルが偶数と奇数のサブセットに分割されます。各時間ステップで、一方のパリティのセルの特定のペアが、もう一方のパリティの近くのセルの構成に基づいて交換されます。このモデルを使用するルールは、ビリヤードボールコンピューターをシミュレートしたり、^[16] さまざまな速度で移動したり、さまざまな周波数で振動したりできるライブセルの長いストリングをサポートしたりできます。^[17]

セルオートマトンとは、各セルが有限の数の状態を持つセルの配列と、隣接するセルの状態のみに基づいてすべてのセルを同時に更新するルールから構成されます。セルオートマトンの構成とは、オートマトンの各セルに状態を割り当てることです。セルオートマトンの更新ルールは、構成から構成への関数を形成し、任意のセルの更新値はセルの有限近傍のみに依存し、関数は入力配列の変換に対して不変であるという要件を満たします。

これらの定義によれば、セルオートマトンが可逆的であるとは、以下の条件のいずれかを満たす場合であり、これらはすべて数学的に同等である。^[18]

1. オートマトンのあらゆる構成には、更新ルールによってマッピングされる一意の前身があります。
2. オートマトンの 更新規則は、全単射、つまり1 対 1 かつ上への関数です。
3. 更新規則は単射関数である。つまり、同じ共通構成にマッピングされる2つの構成は存在しない。この条件は、更新規則が単射であるという仮定によって明らかに暗示される。逆に言えば、セルオートマトンにおけるエデンの園の定理は、すべての単射更新規則が単射であることを意味する。^[19]
4. オートマトンの時間反転ダイナミクスは、別のセルオートマトンで記述できます。明らかに、これが可能であるためには、更新規則は単射でなければなりません。逆に言えば、更新規則が単射であれば、その逆関数も単射です。この逆関数はセルオートマトン規則でなければなりません。この事実の証明には、セルオートマトン規則を、配置空間上のカントル位相に関して連続する変換不変関数として位相的に特徴付けるカーティス・ヘドランド・リンドン定理が使われます。^[20]
5. オートマトンの更新規則は、状態空間とセルの格子の並進によって定義されるシフト力学系の自己同型である。つまり、カーティス・ヘドランド・リンドンの定理が示唆するように、シフトマップと可換な同相写像である。^[21]

Di Gregorio と Trautteur (1975) は、セルオートマトンにおける可逆性のいくつかの代替定義を分析している。そのほとんどは、オートマトン遷移関数の単射性または全射性と同等であることが判明している。しかし、これら 2 つの定義のどちらにも一致しないもう 1 つの代替定義がある。これは、静止状態またはデッド状態を持つライフ ゲームなどのオートマトンに適用される。このようなオートマトンでは、有限数の非静止セルのみを持つ構成を「有限」と定義でき、すべての有限構成に少なくとも 1 つの有限の前身があるオートマトン クラスを検討することができる。このクラスは、全射オートマトンと単射オートマトンの両方とは異なることが判明しており、その後のいくつかの研究では、この特性を持つオートマトンを可逆有限オートマトンと呼んでいる。^[22]

与えられた 1 次元セルオートマトンが可逆かどうかをテストする問題にはアルゴリズムによる解決法があることは、Amoroso と Patt (1972) によって初めて示されました。オートマトン理論とde Bruijn グラフに基づく代替アルゴリズムは、それぞれ Culik (1987) と Sutner (1991) によって提案されました。

• Culik は、セルオートマトンが単射遷移関数を持つのは、遷移関数が周期的な構成のサブセット (同じサブストリングを両方向に無限に繰り返す) に対して単射である場合のみであるという観察から始めます。彼は、周期的なストリングに対してオートマトン遷移ルール​​を実行する非決定性有限状態トランスデューサを定義します。このトランスデューサは、ストリングの先頭のオートマトン近傍を記憶し、その近傍を入力の末尾に連結すると非決定性に選択された遷移が正しいものになる場合に受け入れ状態に入ることで機能します。次に、Culik はトランスデューサの入力と出力を交換します。この交換によって生成されたトランスデューサは、指定されたオートマトンと逆のダイナミクスをシミュレートします。最後に、Culik は既知のアルゴリズムを適用して、結果として得られた交換されたトランスデューサが各入力を単一の出力にマッピングするかどうかをテストします。^[23]
• Sutner は、各頂点が連続するセルのシーケンス内のセルの状態の割り当てのペアを表す有向グラフ( de Bruijn グラフの一種) を定義しています。このシーケンスの長さは、オートマトンの内部近傍のサイズより 1 小さくなるように選択されます。Sutner のグラフのエッジは、1 つのセルを除いてすべて重複するセルのシーケンスのペアを表し、シーケンスの和はセルオートマトン内の完全な近傍になります。このような各エッジは、左側の重複するサブシーケンスから右側のサブシーケンスに向けられています。エッジは、セル シーケンスの重複部分で互換性のある状態割り当てを表し、オートマトン ルール (潜在的なエッジによって決定される内部近傍に適用される) により両方の状態割り当てで同じ結果が得られる場合にのみ、グラフに含められます。このグラフの線形時間の強い接続性解析を実行すると、どの頂点がサイクルに属しているかを判断できます。遷移規則が非単射となるのは、このグラフに、少なくとも1つの頂点に2つの異なる状態割り当てがある有向サイクルが含まれている場合のみです。 ^[8]

これらの方法は、入力オートマトンの状態遷移表のサイズの2乗に比例する多項式時間がかかります。 ^[24] Hillman（1991）の関連アルゴリズムは、周期境界条件を持つ有限長のセル配列に適用されたときに、与えられたルールが射影的であるかどうか、また、射影的である場合はどの長さに対してであるかを決定します。

ブロックセルオートマトンの場合、可逆性のテストも簡単です。オートマトンが可逆なのは、オートマトンブロック上の遷移関数が可逆な場合のみであり、この場合、逆オートマトンには逆遷移関数と同じブロック構造があります。^[10]

しかし、2次元以上の他の近傍を持つセルオートマトンの場合、可逆性のテストの問題は決定不能であり、常に停止し、常に問題に正しく答えるアルゴリズムは存在できないことを意味します。 Kari (1990) によるこの事実の証明は、平面をWang タイルでタイリングすることの既知の決定不能性に基づいています。Wangタイルとは、端にマークがあり、どのタイルのペアが端から端までフィットできるかを制約する正方形のタイルのセットです。 Kari は、Wang タイルのセットからセルオートマトンを定義し、与えられたタイルセットが平面全体をタイリングできる場合にのみ、オートマトンが単射でなくなるようにします。彼の構築では、フォンノイマン近傍と、多数の状態を持つセルを使用します。同じ論文で、Kari は、2次元以上の特定のセルオートマトンルールが全射であるかどうか (つまり、エデンの園があるかどうか) をテストすることも決定不能であることを示しました。

セルあたりn個の状態を持つ 1 次元可逆セルオートマトンにおいて、セルの近傍がm個のセルの区間である場合、逆ダイナミクスを表すオートマトンには最大でn ^{m − 1} − m + 1個のセルからなる近傍が含まれる。この制限はm = 2の場合に厳しいことが知られている。つまり、2 個のセルの近傍を持つn状態の可逆セルオートマトンが存在し、その時間反転ダイナミクスは近傍サイズがちょうどn − 1のセルオートマトンを形成する。^[25]

任意の整数mに対して、フォン・ノイマン近傍を持つ2 次元可逆m状態セルラーオートマトンが有限個しか存在しない。したがって、フォン・ノイマン近傍を持つm状態セルラーオートマトンのすべての逆が半径が最大でf ( m )の近傍を使用するように明確に定義された関数f ( m )が存在する。つまり、有限個の可逆m状態セルラーオートマトンすべての中で、オートマトンの時間反転ダイナミクスを表すために必要な近傍サイズの最大値をf ( m )とする。しかし、カリの決定不能性の結果により、 f ( m ) を計算するアルゴリズムは存在せず、この関数の値はどの計算可能な関数よりも急速に増加するはずである。^[12]

スティーブン・ウルフラムによるセルオートマトン分類は、ランダムな初期条件でのセルオートマトンの動作を研究したものです。可逆セルオートマトンの場合、初期構成がすべての可能な構成の中から一様にランダムに選択されると、その後のすべての状態に対して同じ一様ランダム性が維持されます。したがって、ほとんどの可逆セルオートマトンがウルフラムのクラス 3 であると思われます。クラス 3 とは、ほとんどすべての初期構成が疑似ランダムまたはカオス的に進化するオートマトンです。ただし、ローカル摂動がオートマトンの動作に与える影響を分析することで、異なる可逆セルオートマトンを区別することは可能です。可逆セルオートマトンの初期状態を変更すると、その後の状態への変更が境界領域内にとどまるか、不規則だが境界なしに伝播するか、急速に広がるかのいずれかになります。ウルフラム (1984) は、これら 3 種類の動作すべてを示す 1 次元可逆セルオートマトン規則をリストしています。

ウルフラムのその後の研究は、この点で特に興味深いものとして、1次元ルール37Rオートマトンを特定した。周期境界条件を持つ有限のセル配列で実行すると、より大きな空の近傍の中心にあるランダムセルの小さなシードから始まり、秩序立った状態と混沌とした状態の間を変動する傾向がある。しかし、同じ初期条件を無制限のセルセットに適用すると、その構成はいくつかの種類の単純な移動粒子に自ら組織化する傾向がある。^[26]

可逆セルオートマトンを形式化する別の方法として抽象代数があり、この形式化は可逆セルオートマトン規則のコンピュータによる検索の開発に役立っています。Boykett (2004) は、半中心双群体を、要素の集合Sと要素のペアに対する 2 つの操作→と←から構成される代数構造として定義し、次の 2 つの等式公理を満たします。

• Sのすべての要素a、b、cについて、( a → b ) ← ( b → c ) = bであり、
• Sのすべての要素a、b、cについて、( a ← b ) → ( b ← c ) = bです。

例えば、演算→が右引数を返し、演算←が左引数を返す2つの演算の場合、これは当てはまります。これらの公理は、中心群の定義公理（単一の二項演算の場合）を一般化します。^[5]

Boykett が主張するように、任意の 1 次元可逆セル オートマトン は、セルが各時間ステップで半単位オフセットされ、オートマトンの前向き進化と逆進化の両方で、各方向に半単位離れた 2 つのセルのみの近傍を持つ長方形形式のオートマトンと同等です。可逆オートマトンが 2 つのセルよりも大きい近傍を持つ場合、近傍がより小さく、セルあたりの状態が多い可逆オートマトンでシミュレートできます。この場合、シミュレートするオートマトンの各セルは、シミュレートされるオートマトン内の連続したセル ブロックをシミュレートします。半中心双群体の 2 つの公理は、これらの 2 セル近傍の順方向および逆方向の遷移関数が互いに逆になるために必要な条件とまったく同じです。つまり、すべての半中心双群体は長方形の可逆セルオートマトンを定義し、その中でオートマトン遷移関数は→ 操作を使用してその近傍の2つのセルを結合し、← 操作は同様にオートマトン逆ダイナミクスを定義します。すべての1次元可逆セルオートマトンはこの形式のものと同等です。^[5]

ボイケットはこの代数的定式化を、すべての可能な非等価な可逆セルオートマトンを網羅的にリストするアルゴリズムの基礎として使用した。^[27]

研究者が物理システムをシミュレートするために可逆セルオートマトンを設計する場合、通常はシステムの保存則を設計に組み込みます。たとえば、理想気体をシミュレートするセルオートマトンでは、気体粒子の数とそれらの総運動量が保存される必要があります。そうしないと、正確なシミュレーションが提供できないためです。ただし、意図的な設計とは無関係に、可逆セルオートマトンが持つことができる保存則に関する研究もいくつか行われています。これらの研究で測定された保存量の典型的なタイプは、オートマトンのすべての連続したk個のセルのサブセット全体にわたる、各サブセットのセルの状態の数値関数の合計の形をとります。このような量は、有限値を取るたびに、その値がオートマトンの各タイムステップを通じて自動的に一定のままである場合に保存され、この場合、オートマトンk次不変量と呼ばれます。^[28]

たとえば、長方形のバンドの例として定義された 1 次元セルオートマトンを思い出してください。このセルオートマトンでは、セルの状態は、左の値と右の値のセットLとRから抽出された値のペア ( l、r )であり、各セルの左の値は各タイムステップで右に移動し、各セルの右の値は左に移動します。この場合、バンドの左または右の値xごとに、保存量、つまりその値を持つセルの合計数を定義できます。左の値がλ個で右の値がρ 個ある場合、独立した 1 次不変量はλ + ρ − 2 個あり、どの 1 次不変量もこれらの基本的な不変量の線形結合として表すことができます。左の値に関連付けられた保存量は、一定の速度で右に均一に流れます。つまり、線のある領域C内のxに等しい左の値の数が時間0にある特定の値を取る場合、時間tにシフトした領域C + t /2でも同じ値を取ることになります。同様に、右の値に関連付けられた保存量は左に均一に流れます。^[29]

任意の 1 次元可逆セル オートマトンを長方形形式にすることができ、その後、その遷移規則を、状態セットの順列とともに、べき等半中心二群 (単一の状態値を持つセルの領域が境界でのみ変化する可逆規則) の作用に因数分解することができます。オートマトン規則 (順列を省略することによって形成される修正規則) のべき等持ち上げの 1 次不変量は、必然的に長方形バンドの不変量のように動作します。つまり、相互作用なしで一定速度で左または右に流れる不変量の基底を持ちます。オートマトン全体の 1 次不変量は、順列の同じ軌道に属するすべての状態ペアに等しい重みを与えるべき等持ち上げの不変量とまったく同じです。ただし、規則内の状態の順列により、これらの不変量はべき等持ち上げの場合とは異なる動作をし、不均一に相互作用しながら流れることがあります。^[29]

物理システムでは、ノイマンの定理は保存則とシステムの対称性の間に同等性を与える。しかし、セルオートマトンの場合、この定理は直接適用されない。なぜなら、システムのエネルギーによって支配されるのではなく、オートマトンの動作はそのルールにコード化されており、オートマトンが従う可能性のある保存則に関係なく、特定の対称性（空間と時間の両方における並進不変性）に従うことが保証されているからである。しかし、特定の可逆システムの保存量は、いくつかの点でエネルギーと同様に動作する。たとえば、オートマトンの各領域で保存量の平均値が異なる場合、オートマトンルールによってこの量が消散し、後の状態で量の分布がより均一になる可能性がある。これらの保存量をシステムのエネルギーの代用として使用することで、古典物理学の方法を使用してシステムを分析できる。^[30]

格子ガスオートマトンとは、流体または理想気体中の粒子の動きをシミュレートするために設計されたセルオートマトンである。このようなシステムでは、ガス粒子は他の粒子と弾性衝突するまで、一定速度で直線上を移動する。格子ガスオートマトンでは、一定数の速度（通常は1つの速度と4方向または6方向の運動）のみを許可し、起こり得る衝突の種類を単純化することで、これらのモデルを単純化している。^[31]

具体的には、HPP 格子ガス モデルは、 4 つの軸平行方向に単位速度で移動する粒子で構成されます。2 つの粒子が反対方向の同一線上で出会うと、それらは衝突し、衝突点から垂直線上で外側に送り出されます。このシステムは物理ガスの保存則に従い、物理ガスの挙動に似たシミュレーションを生成します。ただし、非現実的な追加の保存則に従うことが判明しました。たとえば、任意の単一線内の全運動量は保存されます。また、このモデルにおける軸平行方向と非軸平行方向の差 (異方性) は望ましくないほど高くなります。FHP格子ガス モデルは、粒子が 4 方向だけでなく、互いに 60 度の角度で 6 つの異なる方向に移動するようにすることで、HPP モデルを改良しています。正面衝突では、2 つの出ていく粒子は、2 つの入ってくる粒子から 60 度の角度で偏向します。 FHPモデルでは三方向衝突も可能であり、総運動量を維持し、HPPモデルの非物理的な追加保存則を回避する方法で処理されます。^[31]

これらのシステムにおける粒子の運動は可逆的であるため、通常は可逆セルオートマトンで実装されます。特に、HPPとFHPの格子ガスオートマトンの両方は、マーゴラス近傍を使用した2状態ブロックセルオートマトンで実装できます。^[31]

イジングモデルは、磁気システムの挙動をモデル化するために使用されます。これはセルの配列で構成され、各セルの状態はスピン（上向きまたは下向き）を表します。システムのエネルギーは、互いに同じスピンを持つ隣接するセルのペアの数に依存する関数によって測定されます。したがって、セルに2つの状態の隣接セルが同数ある場合、セルは総エネルギーを変更せずに自身の状態を反転することができます。ただし、このような反転は、隣接する2つのセルが同時に反転しない場合にのみエネルギーを保存します。^[32]

このシステムのセルオートマトンモデルは、正方格子を交互に2つのサブセットに分割し、一度に2つのサブセットのうちの1つを更新します。各更新では、反転可能なすべてのセルが反転します。これにより、イジングモデルの調査に使用できる可逆セルオートマトンが定義されます。^[32]

Fredkin と Toffoli (1982) は、可逆コンピューティングの研究の一環として、ビリヤードボール コンピュータを提案しました。ビリヤードボール コンピュータは、同期した粒子 (ビリヤード ボール) のシステムで構成され、固定された一連の障害物によって誘導されながらトラック内を移動します。粒子が互いに衝突したり障害物に衝突すると、実際のビリヤード ボールと同じように弾性衝突が発生します。コンピュータへの入力は、特定の入力トラック上の粒子の有無を使用してエンコードされ、出力も同様に出力トラック上の粒子の有無を使用してエンコードされます。トラック自体はワイヤとして考えられ、粒子はそれらのワイヤ上を伝送されるブール信号として考えられます。粒子が障害物に当たると、その障害物から反射します。この反射は、粒子がたどるワイヤの方向の変化として解釈できます。異なるトラック上の 2 つの粒子が衝突し、衝突ポイントに論理ゲートが形成される場合があります。^[33]

Margolus (1984) が示したように、ビリヤードボール コンピュータは、Margolus 近傍を持つ 2 状態可逆ブロック セル オートマトンを使用してシミュレートできます。このオートマトンの更新ルールでは、正確に 1 つのライブ セルを持つブロックは 180° 回転し、対角線上の 2 つのライブ セルを持つブロックは 90° 回転し、他のすべてのブロックは変更されません。これらのルールにより、孤立したライブ セルは、対角軌道上を移動するビリヤード ボールのように動作します。複数のライブ セルが接続されたグループは、代わりにビリヤードボール コンピュータの固定された障害物のように動作します。付録で、Margolus は、2 次元ムーア近傍を使用する 3 状態 2 次セル オートマトンがビリヤードボール コンピュータをシミュレートできることも示しました。

ビリヤードボールモデルのような可逆的な普遍的計算モデルを研究する理由の 1 つは、理論的には、消費エネルギーが非常に少ない実際のコンピュータ システムにつながる可能性があることです。ランダウアーの原理によれば、不可逆な計算ステップではステップごとに一定の最小量のエネルギーが必要ですが、可逆なステップではステップごとにゼロに任意の近い量のエネルギーで実行できます。^[34]しかし、ランダウアーの限界よりも少ないエネルギーで計算を実行するには、セル オートマトンがグローバルに可逆な遷移関数を持つだけでは不十分です。必要なのは、遷移関数のローカルな計算も可逆的に行うことです。たとえば、可逆ブロック セル オートマトンは常にローカルで可逆です。つまり、個々のブロックの動作には、有限個の入力と出力を持つ可逆関数の適用が含まれます。Toffoli と Margolus (1990) は、すべての可逆セル オートマトンがローカルで可逆な更新規則を持つかどうかを最初に尋ねました。 Kari (1996) は、1次元および2次元のオートマトンでは答えが肯定的であることを示し、Durand-Lose (2001) は、任意の可逆セルオートマトンが（おそらく異なる）局所的に可逆なセルオートマトンによってシミュレートできることを示した。しかし、すべての可逆遷移関数が2次元以上の場合は局所的に可逆であるかどうかという疑問は未解決のままである。^[35]

トフォリとマーゴラスの「トロン」ルールは、マーゴラス近傍を持つ可逆ブロックセルルールである。2×2のセルブロックがすべて同じ状態にある場合、ブロックのすべてのセルの状態が変化する。それ以外の場合は、ブロックのセルは変化しない。トフォリとマーゴラスが主張するように、このルールによって生成されるパターンの進化は、マーゴラス近傍の他のルールを同期するためのクロックとして使用できる。このように同期されたセルオートマトンが非同期セルオートマトン上で実行されている間、標準的なマーゴラス近傍ルールと同じダイナミクスに従う。^[36]

Kari (1990) は、多次元可逆セルオートマトンを暗号化システムとして使用することを提案した。Kari の提案では、セルオートマトン規則が暗号化キーとなる。暗号化は規則を 1 ステップ前進させることで実行され、復号化は規則を 1 ステップ後退させることで実行される。Kari は、このようなシステムを公開キー暗号システムとして使用できることを示唆している。原理的には、攻撃者は、可逆性のテストの決定不能性のため、与えられた暗号化キー (前進規則) から復号化キー (逆規則) をアルゴリズム的に決定することはできないため、システムのセキュリティを危険にさらすことなく前進規則を公開することができる。しかし、Kari は、このようなシステムにどのタイプの可逆セルオートマトンを使用すべきかを指定せず、このアプローチを使用する暗号システムで暗号化/復号化キーのペアを生成できる方法も示さなかった。

Chai、Cao、Zhou (2005) は、別の暗号化システムを提案しました。彼らのシステムでは、暗号化キーによって 1 次元セルオートマトンの各セルのローカルルールが決定されます。そのルールに基づく 2 次オートマトンが入力に対して数回実行され、暗号化された出力に変換されます。オートマトンには可逆性があるため、同じシステムを逆に実行することで、暗号化されたメッセージをすべて復号化できます。このシステムでは、暗号化と復号化の両方に同じキーが使用されるため、キーは秘密にしておく必要があります。

量子セルオートマトンとは、状態と状態遷移が量子力学の法則に従うオートマトン配列である。量子セルオートマトンとは、計算モデルとしてファインマン（1982）によって提案され、ワトラス（1995）によって初めて形式化されたものである。これらのオートマトンに関するいくつかの競合する概念は現在も研究中であり、その多くは、このようにして構築されたオートマトンが可逆的であることを要求している。^[37]

Janzing (2010) は、セルオートマトンが物理的に普遍的である可能性があるかどうかを問いました。これは、オートマトンセルの任意の境界領域について、その領域をセルで囲み、そのセルの状態が適切なサポート足場を形成し、オートマトンがその領域内の状態セットに対して任意の変換を実行できるようにすることを意味します。このようなオートマトンには可逆性、または少なくとも局所的に単射性が必要です。この特性を持たないオートマトンにはエデンの園のパターンがあり、エデンの園を作成する変換を実行することはできないためです。

Schaeffer (2015) は、この意味で物理的に普遍的な可逆セルオートマトンを構築しました。Schaeffer のオートマトンとは、2 つの状態と Margolis 近傍を持つブロックセルオートマトンで、ビリヤードボールモデルや HPP 格子ガスのオートマトンと密接に関連しています。ただし、ビリヤードボールモデルは物理的に普遍的ではありません。これは、ある領域内の状態が読み取られて変換されるのを防ぐ侵入不可能な壁を構築するために使用できるためです。Schaeffer のモデルでは、すべてのパターンは最終的に 4 方向に斜めに移動する粒子に分解されます。したがって、彼のオートマトンがチューリング完全ではありません。ただし、Schaeffer は、有限の構成を、それよりもゆっくりと減衰する足場によって囲むことが可能であることを示しました。構成が粒子に分解された後、足場はそれらの粒子を傍受し、足場内に構築されたブール回路のシステムへの入力として使用します。これらの回路は、初期構成の任意の関数を計算するために使用できます。次に、足場は回路の出力を移動する粒子のシステムに変換し、粒子は最初の領域に収束し、互いに衝突して変換された状態のコピーを構築します。このように、シェーファーのシステムは、状態空間の任意の境界領域に任意の関数を適用するために使用でき、このオートマトンルールが物理的に普遍的であることを示しています。^[38]