2次セルオートマトン

基本的な CA ルール 18 (左) とその二次対応ルール 18R (右)。時間は下向きに進行します。不可逆ルールの上下非対称三角形に注意してください。

2次セルオートマトンとは、エドワード・フレドキン^[1]^{[2]によって発明された}可逆セルオートマトン（CA）の一種であり、時刻 $t$ におけるセルの状態は時刻 $t$ $- 1$ における近傍だけでなく、時刻 $t$ $- 2$ における状態にも依存する。^[3]

一般的なテクニック

一般に、2 次オートマトンの進化ルールは、セルの近傍をオートマトンの状態の順列にマッピングする関数 $fとして記述できます。各時間ステップ$ $tで、オートマトンのセル$ $c$ ごとに、この関数が $c$ の近傍に適用され、順列 $σ$ $c が$ 得られます。次に、この順列 $σ$ $c$ が時間 $t$ $- 1におけるセル$ $c$ の状態に適用され、結果が時間 $t$ $+ 1$ におけるセルの状態になります。このように、各時間ステップでのオートマトンの配置は、前の 2 つの時間ステップから計算されます。直前のステップでは、セルに適用される順列が決定され、その前の時間ステップでは、これらの順列が作用する状態が与えられます。^[4]

2 次オートマトンの逆時間ダイナミクスは、同じ近傍を持つ別の 2 次オートマトンで記述できます。この場合、近傍を順列にマッピングする関数 $gは、$ $f$ の逆順列を与えます。つまり、可能な各近傍 $N$ で、 $f (N)$ と $g (N) は$ 逆順列である必要があります。この逆ルールにより、関数 $g$ で記述されるオートマトンでは、時刻 $t$ と $t$ $+ 1$ の構成から時刻 $t - 1 の$ 構成を正しく計算します。すべての 2 次オートマトンはこのように反転できるため、オートマトンルールを決定するためにどの関数 $fが選択されるかに関係なく、それらはすべて$ 可逆セルラーオートマトンになります。 ^[4]

2状態オートマトンの場合

セルオートマトンに状態が 2 つしかない場合、状態の可能な順列も 2 つしかありません。各状態をそれ自体にマップする恒等順列と、各状態を他の状態にマップする順列です。これらの 2 つの順列を、オートマトンの状態 2 つと同一視できます。このように、すべての 2 次セルオートマトン (近傍から順列への関数によって定義) は、近傍から状態への関数によって直接定義される通常の (1 次) セルオートマトンに一意に対応します。^[4] 2 状態の 2 次オートマトンは時間反転に対して対称です。つまり、時間反転したオートマトンの動きは、元の動きと同じルールでシミュレートできます。

2 つの状態をブール値として見ると、通常のオートマトンと 2 次オートマトンの対応関係は簡単に説明できます。つまり、時刻 $t + 1$ における 2 次オートマトンのセルの状態は、時刻 $t$ $- 1$ におけるその状態と通常のセルオートマトンルールが計算する状態との排他的論理和です。 ^[4] 実際、すべての 2 状態 2 次ルールはこのように生成できます。^[1]ただし、結果として得られる 2 次オートマトンは、通常、元の通常の CA とほとんど類似していません。このようにして構築された 2 次ルールは、Stephen Wolframによって、基本ルールの番号または Wolfram コードに "R" を追加して命名されています。^[3]

アプリケーション

2次オートマトンを用いてビリヤードボールコンピュータ^[1]や統計力学における強磁性のイジング模型^[2]^[4]をシミュレートすることができる。また、暗号にも利用できる。^[5]

参考文献

^ abc Margolus, N. (1984)、「物理学に似た計算モデル」、Physica D、10 (1–2): 81–95、Bibcode :1984PhyD...10...81M、doi :10.1016/0167-2789(84)90252-5. Wolfram, Stephen編 (1986)、セルオートマトン理論と応用、複雑系に関する先進シリーズ、第 1 巻、World Scientific、pp. 232–246、Bibcode :1986taca.bookに再録.....W。
^ ab Vichniac, G. (1984)、「セルオートマトンによる物理シミュレーション」、Physica D、10 (1–2): 96–115、Bibcode :1984PhyD...10...96V、doi :10.1016/0167-2789(84)90253-7。
^ ab ウルフラム、スティーブン（2002）、A New Kind of Science、ウルフラムメディア、pp. 437–440、452、ISBN 1-57955-008-8。
^ abcde トッフォリ、トンマーゾ;マーゴラス、ノーマン(1990)、「反転セルオートマトン」、Physica D、45 (1–3): 229–253、Bibcode :1990PhyD...45..229T、doi :10.1016/0167-2789(90)90185- r特にセクション5.4「二次セルオートマトン」、238～240ページを参照してください。このPhysica D号は、Gutowitz, Howard編（1991年）、Cellular Automata: Theory and Experiment、MIT/North-Hollandとして再版されました。。
^ Chai, Zhenchuan; Cao, Zhenfu; Zhou, Yuan (2005)、「可逆な 2 次セルラーオートマトンに基づく暗号化」、並列分散処理とアプリケーション (ISPA 2005 ワークショップ)、Lecture Notes in Computer Science、vol. 3759、Springer、pp. 350–358、doi :10.1007/11576259_39、ISBN 978-3-540-29770-3。

[m84-1] Margolus, N. (1984)、「物理学に似た計算モデル」、Physica D、10 (1–2): 81–95、Bibcode :1984PhyD...10...81M、doi :10.1016/0167-2789(84)90252-5. Wolfram, Stephen編 (1986)、セルオートマトン理論と応用、複雑系に関する先進シリーズ、第 1 巻、World Scientific、pp. 232–246、Bibcode :1986taca.bookに再録.....W。

[vichniac-2] Vichniac, G. (1984)、「セルオートマトンによる物理シミュレーション」、Physica D、10 (1–2): 96–115、Bibcode :1984PhyD...10...96V、doi :10.1016/0167-2789(84)90253-7。

[nkos-3] ウルフラム、スティーブン（2002）、A New Kind of Science、ウルフラムメディア、pp. 437–440、452、ISBN 1-57955-008-8。

[tm90-4] トッフォリ、トンマーゾ;マーゴラス、ノーマン(1990)、「反転セルオートマトン」、Physica D、45 (1–3): 229–253、Bibcode :1990PhyD...45..229T、doi :10.1016/0167-2789(90)90185- r特にセクション5.4「二次セルオートマトン」、238～240ページを参照してください。このPhysica D号は、Gutowitz, Howard編（1991年）、Cellular Automata: Theory and Experiment、MIT/North-Hollandとして再版されました。。

[5] Chai, Zhenchuan; Cao, Zhenfu; Zhou, Yuan (2005)、「可逆な 2 次セルラーオートマトンに基づく暗号化」、並列分散処理とアプリケーション (ISPA 2005 ワークショップ)、Lecture Notes in Computer Science、vol. 3759、Springer、pp. 350–358、doi :10.1007/11576259_39、ISBN 978-3-540-29770-3。