セルオートマトンの合成とリミットサイクルについて
九州産業大学基礎教育センター
石田
俊一
(Toshikazu
Ishida)
Center
for Fundamental Education,
Kyushu
Sangyo
University
九州大学大学院数理学研究院
井口 修一
(Shuichi Inokuchi)
Faculty
of
Mathematics,
Kyushu
University
1
はじめに
セルオートマトン
(CA)
とは、
内部状態を持つ複数個のセルで構成される離散的な様相
$c\in C$
が、遷移
関数
$F:Carrow C$
に従って離散時間毎に変化する遷移系
$(C, F)$
である。 セルオートマトンは、
非常に単純
な構造をした計算モデルであるが、多様性に富み、かつ、複雑な挙動を示すことから、交通流などの社会、
経済現象、様々な自然現象のシミュレーションなど、多くの分野で研究、応用されている。
その中の 1
っ
に、
1 次元 2 状態のセルオートマトンの遷移規則をうまく定義することで、
最大周期
(2 のシステムサイ
ズ乗一定数)
のパターンを生成するセルオートマトンが構成できることから、
ランダムパターン生成器へ
の応用例がある。一様構造ではない，っまりセル毎に適用する規則が変わるハイブリッドセルオートマト
ンでは、研究が報告されており、最大周期をもつための必要十分条件
(遷移行列の特性多項式が原子多項
式
$)$[1]
や、原子多項式から最大周期をもつセルオートマトンを構成する方法が提案されている
[4]。一方、
一様な構造を持っセルオートマトンでは、
最大周期をもつセルオートマトンはいくつかしか知られていな
い
[3]
。しかし、ハイブリッドなセルオートマトンほどではないが、一様な構造のセルオートマトンの種類
も非常に多く、
その中に最大周期をもつセルオートマトンが存在すると思われるが、
そのすべてを考察す
るのはほぼ不可能である。
本論文では、セルオートマトンの合成により新たなセルオートマトンを構成し、挙動の関係性を考察す
る。
中でもセルオートマトンの合成が可換である組み合わせについて注目する。
つまり、 2
つのセルオー
トマトン
$CA_{1}=$
$(C,F_{1}:Carrow C),CA_{2}=(C,F_{2}:Carrow C)$
に対して、遷移関数を
$F=F_{1}\circ F_{2}=F_{2}\circ F_{1}$と定義したセルオートマトン
$CA=(C, F)$
を構成し、
$CA_{1\text{、}}CA_{2}$と
$CA$
の挙動の関連について考察する。
2
セルオートマトンとその合成
セルオートマトンの定義は様々あるが、
ここでは、論文
[2]
の定義を用いる。
定義
1
$G$を群とする。有限集合
$V\subset G,$$V’\subset 2^{V}$に対し、 $CA=(G, V,V’)$
を
$G$上のセルオートマトンと
し、
$V’$に関して、 関数
$f$:
$2^{V}arrow\{\phi, \{e\}\}$を以下で定義する。
$\forall A\in 2^{V}$のとき
$f(A)=\{\begin{array}{ll}\phi (A\not\in V’)\{e\} (A\in V’)\end{array}$
また、
$\forall X\in 2^{G}$に対し，F:
$2^{G}arrow 2^{G}$を
$F(X)= \bigcup_{g\in G}gf(g^{-1}X\cap V)$
と定義する。
このとき、
$f$を局所遷移
関数、
$F$を大域遷移関数と呼ぶ。
定義 2
$CA_{1}=(G, V_{1}, V_{1}’)$、$CA_{2}=(G, V2, V_{2}’)$
を
上のセルオートマトンとする。 このとき、合成セル
オートマトン
$CA_{1}\phi CA_{2}=(G, V_{1}\cdot V_{2}, V_{1}’\phi V_{2}’)$を以下の様に定義する。
.
$V_{1}\cdot V_{2}=\{v_{1}v_{2}\in G|v_{1}\in V_{1},v_{2}\in V_{2}\}$.
$V_{1}’\phi V_{2}’=\{X\in 2^{V_{1}\cdot V_{2}}|\{v\in V_{1}|v^{-1}X\cap V_{2}\in V_{2}’\}\in V_{1}’\}$合成に対し、以下の性質がある。
定理 3[2]
大域遷移関数」
FbA, ,
$F_{CA_{2}},F_{CA_{1}\phi CA_{2}}$に対し、
$F_{CA_{1}}\circ F_{CA_{2}}=F_{CA_{1}\phi CA_{2}}$が成り立っ。
定義
4
$C$を様相の集合、
$F$を遷移関数とする。
このとき
$F^{\infty}(C)$を以下で定義する。
$F^{\infty}(C):=\{c\in C|\exists n>0c=F^{n}(c)\}$
$c\in F^{\infty}(C)$を
$F$のリミットサイクル
$(LC)$
上の様相と呼ぷこととする。
3
合成
CA
の
LC
の周期
セルオートマトンの合成が可換となる条件はいくつか明らかになっている
[6]
。本論文では合成が可換
となるセルオートマトンに着目し、 そのリミットサイクルについて考察する。 以後、特に断わらない限
り、セルオートマトンの合成は可換であるものとする。今、セルオートマトン
$CA=(G, V, V’)$
は 2 つ
のセルオートマトン
$CA_{1}=(G,V_{1},V_{1}’)$
、$CA_{2}=(G,V_{2},V_{2}’)$
の合成で定義されているとする。すなわち、
$CA=CA_{1}\circ CA_{2}=CA_{2}\circ CA_{1}$
であり、大域遷移関数も
$F=F_{1}\circ F_{2}=F_{2}\circ F_{1}$を満たす。
補題
5
以下が成り立つ。
.
$F(C)\subseteq F_{1}(C)$.
$F(C)\subseteq F_{2}(C)$$c\in C-F(C)$
がエデンの園 (GOE)
様相であるので、上記の補題より
$C-F_{1}(C)\cup C-F(C)\subseteq C-F(C)$
となり、
$c\in C$
が呂または乃の
GOE
様相ならば、
$c$は
$F$の
GOE
様相であることを意味する。
LC
上の様相の集合について以下の性質がある。
補題
6
以下が成り立つ。
1.
$F_{1}^{\infty}(C)\cap F_{2}^{\infty}(C)\subset F^{\infty}(C)$2.
$F^{\infty}(C)\subset F_{1}^{\infty}(C)\cup F_{2}^{\infty}(C)$証明
(1)
$c\in F_{1}^{\infty}(C)\cap F_{2}^{\infty}(C)$とする。 すなわち、
$c=F_{1}^{n_{1}}(c)=F_{2}^{nz}(c)$なる
$n_{1},$$n_{2}>0$
が存在する。
い
ま、
$F_{1}\circ F_{2}=F_{2}\circ F_{1}$であるので、
$F^{n_{1}\cross n_{2}}(c)=(F_{1}\circ F_{2})^{n_{1}xn_{2}}(c)=F_{1}^{n_{1}xn_{2}}(F_{2}^{n_{1}xn_{2}}(c))=C$となり、
$c\in F_{\infty}(C)$である。
(2)
$c\in F^{\infty}(C)$とする。
すなわち、
$c=F^{n}(c)$
なる
$n>0$ が存在する。 いま、
$C$は有限集合であるので、
$nxm>\# C$ なる整数
$m$をとることができる。
$c=F^{nxm}(c)=F_{1}^{nxm}(F_{2}^{nxm}(c))(=F_{2}^{nxm}(F_{1}^{nxm}(c)))$
で
あるので、
$c\in F_{1}^{\infty}(C)(c\in F_{2}^{\infty}(C))$である。
$(t>\# C$
、
$\forall c\in C$
に対して、
$F^{t}(c)\in F^{\infty}(C)$である。
$)$口
この補題は
$c\in C$
が瓦の
LC
上の様相であり、 かつ巧の
LC
上の様相であるならば
$c$は
$F$の
LC
上の
補題
7
以下が成り立つ。
1.
$c\in F_{1}^{\infty}(C)$ならば
$F_{2}(c)\in F_{1}^{\infty}(C)$2.
$c\in F^{\infty}(C)$ならば
$F_{1}(c)\in F^{\infty}(C)$系 8 以下が成り立っ。
$(C-F_{1}^{\infty}(C))\cap(C-F_{2}^{\infty}(C))\subseteq(C-F^{\infty}(C))$上記の系より様相
$c$が
$F_{1},F_{2}$上の
LC
上になければ、
$F$の
LC
を構成する様相にはなりえないことを
表す。
次に各遷移関数に対する周期と、合成した遷移関数の周期に関して考察する。
補題
9
ある
$c\in C$
に対して、
$c=F_{1}^{n_{1}}(c)=F_{2}^{n_{2}}(c)$なる整数
$n_{1},n_{2}>0$が存在するならば
$c=F^{LCM(n_{1},n_{2})}(c)$
である。
以下の議論において、
$c\in F_{1}^{\infty}(C)\cap F_{2}^{\infty}(C)$とし、
$C_{1}=\{F_{1}^{t}(c)|t\geq 0\}$、 $C_{2}=\{F_{2}^{t}(c)|t\geq 0\}$、
とする。
また、
$\# C_{1}=n_{1\text{、}}\# C_{2}=n_{2\text{、}}\#(C_{1}\cap C_{2})=m$とする。
補題
10
$m|n_{1}$かつ
$m|n_{2}$である。
証明同じ方法で証明できることから
$m|n_{1}$のみ証明する。
$m\gamma n_{1}$と仮定する。
このとき、
$t= \min\{t’>$
$0|F_{1}^{t’}(c)\in C_{2}\}$
とする。
$c\in C_{2},F_{1}^{t}(c)\in C_{2}$を満たす。 また、
$1<t’<t$
に対して
$F_{1}^{t’}(c)\not\in C_{2}$である。
こ
のとき、
$F_{1}^{s}(c)\in C_{2}$であり、
$F_{1}^{s+s’}(c)\in C_{2}$八
$F_{1}^{s+t’}(c)\not\in C_{2}(1\geq t’<s’)\wedge t\neq s’$を満たす
$s>0,$
$s’>0$
が存在する。
ここである
$k$に対し、
$c=(F_{2}^{k}F_{1}^{8})(c)$とする。
このとき
1.
$t>s’$
ならば、
$C_{2}$ $\neq$ $F_{1}^{s’}(c)$ $=$ $F_{1}^{s’}(F_{2}^{k}F_{1}^{8})(c)$ $=$ $F_{2}^{k}(F_{1}^{s+\epsilon’}(c))$ここで
$F_{1}^{s+s’}(c)\in C_{2}$より、矛盾する。
2.
$t<s’$
のときも同様に矛盾が導ける。
ゆえに
$m|n_{1}$である。
口
系 11
$F_{1^{m}}^{\lrcorner}(C_{2})=C_{2}$であり
$F_{2^{m}}^{\simeq A}(C_{1})=C_{1}$である。
また、
$0<t<\underline{n}\perp m$に対し、
$F_{1}^{t}(C_{2})\neq C_{2}$であり、
$0<t< \frac{n}{m}a$
に対し、
$F_{1}^{t}(C_{1})\neq C_{1}$である。
定理 12
$C_{1}\cap C_{2}.=\{c\}$ならば
$\min\{t|t>0,c=F^{t}(c)\}=LCM(n_{1},n_{2})$
である。
証明
$c=F^{LCM(n_{1},n)}2(c)$
は明らかである。
$C_{1}\cap C_{2}=\{c\}$より
$n_{1}\gamma t$なる
$t>0$
に対して、
$C_{1}\neq F_{2}^{t}(C_{1})$であるので、
$c\neq F^{t}(c)(1\leq t<LCM(n_{1},n_{2}))$
となる。
よって
$\min\{t>0|c=F^{t}(c)\}=LCM(n_{1},n_{2})$
で
定理
13
$\#(C_{1}\cap C_{2})=m>1$
とし、
$t= \min\{t’>0|F_{1^{n}}^{n}(c)=F_{2^{n}}^{A}{}^{t’}(c)\}\lrcorner^{*}$とする。
このとき
$\min\{i|F^{i}(c)=c\}=LCM(\frac{n_{1}+n_{2}t}{m},n_{2})x\frac{n_{1}}{(n_{1}+n_{2}t)}$である。
証明
$F$釜
$(c)=F_{2^{m}}^{n}(F_{1^{n}}^{\lrcorner}(c))=F_{2}^{\frac{\mathfrak{n}\ell}{}}(c)\lrcorner^{n}$ ’より
$=$ $p^{LCM}t^{\frac{\hslash+\hslash\ell}{m},n_{2})x\frac{\hslash 1}{t^{\hslash}1+n2^{l})}(c)}$ $=$ $F^{tCMt^{\frac{\hslash+\hslash 1}{n},n_{2})x_{\mathfrak{n}}x_{n}^{\lrcorner}}’}\overline{1+B2^{\ell}}(c)$ $=$ $F_{2}^{LCM(n_{2})} \frac{\mathfrak{n}+*}{n},(c)$ $=$ $c$となる。 また、
$F^{k}(c)=c$
、かつ
$0<k<LCM(^{n\pm n_{L^{t}}}$
」$m,n_{2}) x\frac{n_{1}}{(n_{1}+n_{2}t)}$となる
$k$が存在したと仮定する。
系 11 より
$k$は」
$nm$の倍数でなければならないので、
$k=_{m}^{n}$」$h$と置くと、
$c=F$
箒
$h_{=F_{2^{m}}^{\underline{n}+L_{h}^{1}}(c)}arrow^{R}$となり、
」$n\mapsto ntmh$は
$n_{2}$の倍数でなければならない。ゆえに、
$LCM(^{\underline{n}_{1}}R_{n_{2})}^{nt}m,<_{m}n$」 $\simeq n$th
、すなわち、
$LCM( \frac{n+nt}{m},n_{2})x\frac{n_{1}}{(n_{1}+n_{2}t)}<\lrcorner nmh=k$となり仮定に矛盾する。よって、
$\min\{i|F^{i}(c)=c\}=LCM(^{n\pm n_{L^{t}}}$
」$m,n_{2})x$
$\frac{nr}{(n_{1}+n_{2}t)}$である。
口
系
14
$\# C_{1}=\# C_{2}=n,\#(C_{1}\cap C_{2})=m>1$
であるとする。 このとき、
$t= \min\{t’>0|F_{1^{n}}^{A}(c)=F_{2^{n}}^{1L}{}^{t’}(c)\}$とすると、
$\min\{i>0|\dot{P}(c)=c\}=\frac{n}{m}x\frac{LCM(m,t+1)}{t+1}$
である。
4
合成
CA
の挙動例
この章では周期境界を持つ 1 次元 2 状態 3 近傍セルオートマトンの合成によって出来るセルオートマト
ンの具体的な例を紹介する。なお
CA
の遷移関数は
Wolkam
の番号付けを利用する
[5]。また、各様相を 2
進数で表された数値とし、
10 進数に変換することで番号付けを行う。
セルサイズが 5 のセルオートマトンに対して、合成セルオートマトンの周期長が合成前の各セルオートマト
ンの周期長の最小公倍数になる例を挙げる。図
$1$ 、$2$、$3$は
$CA90(5)$
、CA240(5)、それらの合成セルオートマト
ンの遷移図である。
$c=9$
に対し，
Cl
$=\{6,9,15\},C_{2}=\{5,9,10,18,20\}$
であり，min
$\{t>0|F^{t}(9)=9\}=15$
である。また、合成セルオートマトンの周期長が最小公倍数になる例で、非線形セルオートマトンと練形
セルオートマトンの合成セルオートマトンの例を挙げる。
CA15(5)、
CA150(5)
、それらの合成セルオート
マトンが図
$4$ 、 $5$、$6$である。
ここで
$c=6$
に対し、
$C_{1}=\{3,6,7,12,14,17,19,24,25,28\},C_{2}=\{6,9,15\}$
であり、
$\min\{t>0|F^{t}(6)=6\}=30$
である。
5
終わりに
本稿ではセルオートマトンの合成において、合成が可換となるセルオートマトンと合成セルオートマト
ンの挙動について考察し、合成セルオートマトンの周期と合成前のセルオートマトンの挙動の関係性を示
した。
また、合成セルオートマトンの例をいくつか挙げ、
サイズは小さいが、
合成により最大周期をもっ
セルオートマトンが構成できることを示した。
今後は、合成に関して可換となる為の遷移関数の組の条件のさらなる考察、
基本となるセルオートマト
ンの挙動解析を進めることで、最大周期をもつ合成セルオートマトンの系統的な構成を目指す。
参考文献
[1] B. Elspas, The Theory of
Autonomous
Linear Sequential Networks
Circuit
Theory,
IRE
Transactions
on
Issue
Date,Volume:
6
Issue:
l,p45-60(1959)
[2]
T.
Ito,
M.
liujio,
S.
Inokuchi, Y. Mizoguchi, Composition,
union
and division of cellular
automata
on
groups,
Proc. of the 16th Intemational
Workshop
on Cellular Automata
and
Discrete Complex
Systems, Automata2010, p255-264
(2010)
[3]
M. Matsumoto, Simple Cellular
Automata
as
Pseudorandom m-Sepuence
Generators for Bulit-In
Self-Tes, ACM
Transactions
on
Modeling and Computer
Simulation,
vol.8,
$No.1,$
p31-42
(1988)
[4]
手塚集，伏見正則
VLSI
のテストパターンの生成，数理解析研究所講究録，
volume820,
P72-75
(1993)
[5]
S.
Wolfram,
Statistical Mechanics of Cellular Automata
itshape
Reviews of Modern
Physics.
volume
55,
p601-644
(1983)
[6]
石田俊一，井口修一群上のセルオートマトンにおける遷移関数の合成とその可換性について，応用数
図
1:
CA90(5)
$\infty\infty$
