2次セルオートマトン

可逆セルオートマトンの種類

基本的なセルオートマトンのルール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階セルオートマトン（2階セルオートマトン）は、近傍から状態への直接的な関数で定義される通常の（1階セルオートマトン）に一意に対応する。^[4] 2状態2階オートマトンは時間反転に関して対称的である。つまり、時間反転したオートマトンのダイナミクスは、元のダイナミクスと同じ規則でシミュレートできる。

2つの状態をブール値と見なすと、通常の2階オートマトンと2階オートマトン間の対応関係は簡単に記述できます。時刻 $t + 1$ における2階オートマトンの各セルの状態は、時刻 $t$ $- 1$ におけるその状態と、通常のセルオートマトンルールが計算する状態との排他的論理和です。 ^[4] 実際、すべての2状態2階オートマトンルールはこのように生成できます。^[1]しかし、結果として得られる2階オートマトンは通常、その元となった通常のセルオートマトンとはほとんど類似点がありません。このように構築された2階オートマトンルールは、スティーブン・ウルフラムによって、基本ルールの番号またはウルフラムコードに「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次セルラーオートマトンに基づく暗号化」、Parallel and Distributed Processing and Applications (ISPA 2005 Workshops)、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次セルラーオートマトンに基づく暗号化」、Parallel and Distributed Processing and Applications (ISPA 2005 Workshops)、Lecture Notes in Computer Science、vol. 3759、Springer、pp. 350– 358、doi :10.1007/11576259_39、ISBN 978-3-540-29770-3。