高次保存量を持つCAの確率化について

高次保存量を持つ CA の確率化について
延東和茂 1 , 高橋大輔 1 , 松木平淳太 2
1
早稲田大学、2 龍谷大学
e-mail : [email protected]
1
はじめに
状態変数が 0 と 1 のみである Cellular Automata (CA) のうち、ある時刻における状態
変数の総和が時刻に依存しないものを我々は粒
子 CA と呼んでいるが、これは保存量が 1 次の
タイプのものである。これら粒子 CA に確率変
数を導入した CA についてはさまざまな研究が
なされている。今回は 2 次の保存量を持つ CA
に対して同様に確率変数を導入したモデルにつ
いて議論を行う。なお、本予稿では 2 値 3 近傍
の CA すなわち ECA (Elementary CA) につい
てのみ説明を行う。
2
2 次保存量を持つ ECA
256 個存在する ECA のうち、以下の形の 2
次保存量を持つものは 34 個存在する。
L
∑
j=1
unj−1 ⊕unj
L
∑
=
{unj−1 (1−unj )+(1−unj−1 )unj }
j=1
この保存量により、1 個以上連続する 1 の領域の
数（時間発展パターンにおいては縞模様の縞に
見える）が時刻によって変化しないことになる。
conjugation や reflection、ガリレイ変換、偶奇
ステップの片方をビット変換することによって
合同であるとみなせるものを除くと、独立なも
のは 9 個存在することが分かる。
つ ECA との関連に着目する。1 次保存量を持
つ ECA226 (f226 と表記) と 2 次保存量を持つ
ECA142 (f142 ) には、
f60 ◦ f142 = f226 ◦ f60
(1)
という関係が成り立つことが知られている。ま
た、ECA184 の reflection である ECA226 につ
いては、すでに確率化に成功している。(1) の
f226 をこの確率版 ECA226 で置き換えること
により確率版 ECA142 (SECA142)
un+1
= unj ⊕ min(anj , unj ⊕ unj+1 , 1 − (unj−1 ⊕ unj ))
j
{
1(確率 p)
n
aj =
0(確率 1 − p)
を得ることができる。SECA142 と SECA226
の関係は以下のようになる。
un+1
= unj ⊕ min(anj , unj ⊕ unj+1 , 1 − (unj−1 ⊕ unj ))
j
↓
vjn = unj−1 ⊕ unj
n
vjn+1 = vjn ⊕ min(anj−1 , vjn , 1 − vj−1
)
n
⊕ min(anj , vj+1
, 1 − vjn )
↓
vjn+1
=
Z2 → Z
vjn
n
+ min(anj , vj+1
, 1 − vjn )
n
− min(anj−1 , vjn , 1 − vj−1
)
最後の式の両辺を j = 1, 2, . . ., L で足し合わ
せると
L
L
∑
∑
n+1
vj
=
vjn
j=1
j=1
が得られる。この等式および vjn = unj−1 ⊕ unj の
L
∑
(unj−1 ⊕
関係より SECA142 では 2 次保存量
j=1
ECA142 の時間発展の例
3
2 次保存量 ECA の確率化
保存量を持つ CA にその保存量を壊さない
ように確率変数を導入することを、本研究で
の確率化と定義する。2 次保存量を持つ上記の
ECA を確率化するには、まず 1 次保存量を持
unj ) が存在することがわかる。
SECA142 は、確率変数 anj が 1 の時は ECA142
の時間発展ルールに等しい。anj が 0 の場合は
ECA204 となり、この ECA も同じく 2 次保存
量を持っている。すなわち、この式は確率変数
の値によって 2 次保存量を持つ異なる ECA がス
イッチするという構造になっており、ECA142
の確率化であると同時に ECA204 の確率化に
もなっている。この特徴を利用して、2 次保存
量を持つ他の 7 つの ECA についても、互いの
ECA にスイッチするように確率変数を導入す
るという手法を考案した。この手法に基づいて、
2 次保存量を持つ全ての ECA を確率化するこ
とができた。その結果を以下に示す。
が導かれる。前節で取り上げた SECA142 では、
前述の関係 (1) より、SECA226 の ρ が 10 のパ
ターンの密度 ρ10 に対応し、Q が 10 の運動量
平均 Q10 に対応するので、理論式 (2) がそのま
ま流用できる。講演では、すべての 2 次保存量
を持つ SECA について、それらの基本図の曲
線を理論的に求めて報告を行う予定である。
• f14 ⇄ f12
0.5
un+1
= unj ⊕ min(unj−1 + min(anj , unj ⊕ unj+1 ),
j
0.4
1 − (unj−1 ⊕ unj ))
0.3
• f42 ⇄ f34
un+1
j
=
0.2
min(max( min(anj , 1 − unj−1 ),
1 − unj ), unj+1 )
0.1
0.2
• f35 ⇄ f51
un+1
j
=1−
0.6
0.8
1.0
SECA142 の基本図（α = 0, 0.2, . . ., 1.0）
unj
⊕
min(anj , unj−1 ,
1 − unj , 1
− unj+1 )
• f140 ⇄ f142 ⇄ f204
=
⊕ min(unj ⊕ unj+1 , 1 − (unj−1 ⊕ unj ),
max(min(unj−1 , 1 − anj ), min(1 − unj−1 , bnj )))
un+1
j
0.4
unj
5
今後の課題
本講演では 2 次保存量を持つ ECA の確率化
について述べるが、より高次の保存量を持つも
のや、ひとつの ECA で同時に複数の保存量を
持つものもすでに多数確認されている。それら
の確率化を行い基本図の理論曲線の導出をする
ことは今後の課題である。
ここで anj , bnj は以下で定義される確率変数で
ある。
{
{
1
(
確率
α)
1 (確率 β)
参考文献
anj =
, bnj =
0 (確率 1 − α)
0 (確率 1 − β) [1] 桑原英樹，池上貴俊，高橋大輔，確率変
なお ECA142 は、2 種類の確率変数を導入する
ことにより、その確率変数の値に応じて ECA140
と ECA204 の 2 つの方程式にスイッチするこ
とが分かった。
4
基本図
粒子 CA における系の特性に対する重要な表
現手法として、基本図と呼ばれるものがある。
横軸に保存量である粒子密度 ρ をとり、適当
な初期条件から時間発展を行い、時刻無限大に
おける粒子の運動量平均 Q を計算する。この
ρ–Q 依存性をプロットしたものが基本図であ
り、決定論的な ECA184 では、Q = 12 − |ρ − 12 |
となって ρ = 21 で相転移が起こることが如実に
わかる。確率パラメータを導入した SECA184
では、
√
1 − 1 − 4αρ(1 − ρ)
Q=
(2)
2
数を含む粒子セルオートマトンについて，
日本応用数理学会論文誌, vol.23(2013), 113.
[2] Henlyk Fuk´s, Dynamics of the Cellular
Automaton Rule 142, Complex systems,
16(2005), 123-138.
[3] Tetsuya Hattori and Shinji Takesue, Additive conserved quantities in discretetime lattice dynamical systems, Physica
D: Nonlinear Phenomena, 49(3)(1991),
295-322.

Download Report