予稿集

高次保存量をもつ CA の Max-Min-Plus 解析について
松木平淳太 1 , 高橋大輔 2
1
龍谷大学，2 早稲田大学
e-mail : [email protected]
1
はじめに
R(= l + r + 1) 近傍の 1 次元セルオートマト
ン (CA)
に変換することができるが、この表現を用いる
∑L−1 n
ことによって、保存量 I1 = j=0
uj をサイト
∑L−1 n
数 L で割った密度 ρ = j=0 uj /L と粒子の流
量 Q の関係が
un+1
= f (unj−l , unj−l+1 , . . . , unj , . . . , unj+r ),
j
が、α 次の保存量
Iα =
L
∑
E(unj , unj+1 , . . . , unj+α−1 ),
Q = min(ρ, 1 − ρ),
で与えられることを厳密に示すことができる。
この式をグラフにしたものは基本図と呼ばれ、
ルール 184 の基本図は下図のようになる。
j=1
Q
を持つための必要十分条件は服部と武末によっ
て得られている [1]。ただし、unj は時刻 n にお
けるサイト j のセルの状態を表し、セルの状態
は周期的境界条件 unj+L = unj を満す。
α = 1, E(x) = x の場合、1 次元の保存量
I1 =
L
∑
1
2
0
unj ,
1
2
1
ρ
j=1
は状態が unj = 1 であるセルの総数を表すが、こ
の保存量を持つ CA は相互作用しながら運動す
る粒子の系と見なすことができる。1 次元 3 近
傍 CA である ECA(Elemetary CA) において、
単なる平行移動となるルールを除くと、上記の
保存量を持つ ECA はルール 184 とルール 226
のみである。また、ルール 226 はルール 184 を
左右反転したルールである。
ルール 184 は最も単純な交通流 CA モデルと
して非常によく研究されているが、Burgers 方
程式を超離散化することによって得られる以下
の Max-Min-Plus 表現がルール 184 となること
が西成と高橋によって明らかになっている [2]。
un+1
= unj +min(unj−1 , 1−unj )−min(unj , 1−unj+1 ).
j
この方程式は超離散 Cole-Hopf 変換
1
n
unj = Fjn − Fj−1
− ,
2
によって、超離散拡散方程式
n
n
Fjn+1 = max(Fj−1
, Fj+1
),
2
2 次の保存量を持つ ECA
1 次の保存量を持つ非自明な ECA は 184(お
よびその反転の 226) しかないが、2 次の保存量
L
∑
unj−1 ⊕ unj
j=1
と持つ ECA はルール 12, 14, 15, 34, 35, 42,
43, 51, 140, 142, 170, 204 など多数存在する。
ただし、
a ⊕ b = a + b mod 2
である。2 次の保存量に対しても基本図を考え
ることができるが、Fuk`s はルール 142 に基本
図がルール 184 の基本図に類似していることを
発見した [3]。さらに Fuk`s は Boccara によって
発見された ECA のルール間の関係式
f60 ◦ f142 = f226 ◦ f60 ,
を用いて基本図の解析を行った [4][5]。
我々はこの関係式を用いて、以下のルール 142
の Max-Min-Plus 表現を得ることに成功した。
un+1
= unj ⊕ min(unj ⊕ unj+1 , 1 − unj−1 ⊕ unj ).
j
この表現を用いることによって、2 次の保存量
を持つルール 142 と、1 次の保存量を持つルー
ル 226 と以下のように変換可能であることを示
すことができる。
[4] N. Boccara, Transformations of onedimensional cellular automaton rules
by translation-invariant local surjective
mappings, Physica D: Nonlinear Phenomena, Vol.68(1993), 416–426.
un+1
= unj ⊕ min(unj ⊕ unj+1 , 1 − unj−1 ⊕ unj )
j
[5] H. Fuk´s, Dynamics of the Cellular Au↓ vjn = unj−1 ⊕ unj
tomaton Rule 142, Complex Systems,
n+1
n
n
n
n
n
= vj ⊕ min(vj , 1 − vj−1 ) ⊕ min(vj+1 , 1 − vj )
vj
Vol.16(2005), 123–138.
↓ Z2 → Z
n
n
vjn+1 = vjn + min(vj+1
, 1 − vjn ) − min(vjn , 1 − vj−1
)
また、上記から
L
∑
j=1
vjn+1 =
L
∑
vjn
j=1
を示すことによって、ECA142 が 2 次の保存量
を持つことを代数的に示すことが容易にできる。
3
2 次の保存量を持つ 4 近傍 CA
4 近傍 CA においても、1 次の保存量を持つ
CA と 2 次の保存量を持つ CA が互いに変換可
能であることを示すことができる。以下は、1
次の保存量を持つ CA から変換された 2 次の保
存量を持つ CA の Max-Min-Plus 表現である。
un+1
= unj ⊕ min(unj−2 ⊕ unj−1 + unj−1 ⊕ unj , 1 − unj ⊕ unj+1 ),
j
un+1
= unj ⊕ max(−unj ⊕ unj+1 , min(unj−2 ⊕ unj−1 + unj−1 ⊕ unj − 1, 1 − unj ⊕ unj+1 )),
j
un+1
= unj ⊕ max(0, min(unj−2 ⊕ unj−1 + unj−1 ⊕ unj − 1, 1 − unj ⊕ unj+1 )).
j
本研究によって、高次保存量を持つ CA の代数
的な構造の一端が示されたと考えられるが、一
般的な理論の構築は今後の課題である。
参考文献
[1] T. Hattori and S. Takesue, Additive
conserved quantities in discrete-time
lattice dynamical systems, Physica D:
Nonlinear Phenomena, Vol.49(1991),
295–322.
[2] K. Nishinari and D. Takahashi, Analytical properties of ultradiscrete Burgers equation and rule-184 cellular automaton, J. Phys. A: Math. Gen,
Vol.31(1998), 5439.
[3] H. Fuk´s, Second order additive invariants in elementary cellular automata,
arXiv preprint nlin/0502037.

Download Report