数理解析研究所講究録
第 1799 巻 2012 年 37-43

37

セルオートマトンの合成とリミットサイクルについて
九州産業大学基礎教育センター 石田 俊一 (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)$ を構成し、2$CA_{1\text{、}}CA_{2}$と $CA$ の挙動の関連について考察する。

セルオートマトンとその合成
セルオートマトンの定義は様々あるが、 ここでは、論文 [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$ を大域遷移関数と呼ぶ。

次にセルオートマトンの合成を定義する。

38
定義 2 $CA_{1}=(G, V_{1}, V_{1}’)$.
.

、$CA_{2}=(G, V2, V_{2}’)$を $G$ 上のセルオートマトンとする。 このとき、合成セルオートマトン $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)$ 上の様相と呼ぷこととする。

合成 CA の LC の周期

3

セルオートマトンの合成が可換となる条件はいくつか明らかになっている [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)))$ でに対して、 $F^{t}(c)\in F^{\infty}(C)$ である。
あるので、 $c\in F_{1}^{\infty}(C)(c\in F_{2}^{\infty}(C))$ である。 $(t>\# C$$\forall c\in C$$)$、

口

この補題は $c\in C$ が瓦の LC 上の様相であり、 かつ巧の LC 上の様相であるならば は $F$ の LC 上の$c$様相であることを意味する。 また、合成の可換性より次の補題が言える。

39
補題 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_{1}=n_{1\text{、}}\# C_{2}=n_{2\text{、}}\#(C_{1}\cap C_{2})=m$ とする。

、

$C_{2}=\{F_{2}^{t}(c)|t\geq 0\}$、とする。

補題 10 $m|n_{1}$ かつ $m|n_{2}$ である。

証明同じ方法で証明できることから$0|F_{1}^{t’}(c)\in C_{2}\}$とする。

$m|n_{1}$$c\in C_{2},F_{1}^{t}(c)\in C_{2}$と仮定する。 このとき、 $t= \min\{t’>$を満たす。 また、 $1<t’<t$ に対してである。 このみ証明する。

$m\gamma n_{1}$$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}$$0<t< \frac{n}{m}a$に対し、口であり$F_{2^{m}}^{\simeq A}(C_{1})=C_{1}$$F_{1}^{t}(C_{1})\neq C_{1}$である。 また、$0<t<\underline{n}\perp m$に対し、 $F_{1}^{t}(C_{2})\neq C_{2}$ であり、である。

定理 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})$ である。

ロ

40
定理 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}$$=$$=$$=$$=$となる。 また、 $F^{k}(c)=c$
系 11 より$k$、より$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$」
かつ $0<k<LCM(^{n\pm n_{L^{t}}}$$m,n_{2}) x\frac{n_{1}}{(n_{1}+n_{2}t)}$ となる$k$が存在したと仮定する。

」 と置くと、は」の倍数でなければならないので、 $k=_{m}^{n}$
$h$

$nm$

$c=F$ 箒$h_{=F_{2^{m}}^{\underline{n}+L_{h}^{1}}(c)}arrow^{R}$」th、すなわち、の倍数でなければならない。ゆえに、 $LCM(^{\underline{n}_{1}}R_{n_{2})}^{nt}m,<_{m}n$」$m,n_{2})x$$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}}}$$n\mapsto ntmh$ はとなり、 」$\frac{nr}{(n_{1}+n_{2}t)}$$\simeq n$$n_{2}$である。
口系 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 のセルオートマトンに対して、合成セルオートマトンの周期長が合成前の各セルオートマトは $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$
$3$

$2$

$1$、、、である。また、合成セルオートマトンの周期長が最小公倍数になる例で、非線形セルオートマトンと練形セルオートマトンの合成セルオートマトンの例を挙げる。 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終わりに

本稿ではセルオートマトンの合成において、合成が可換となるセルオートマトンと合成セルオートマトンの挙動について考察し、合成セルオートマトンの周期と合成前のセルオートマトンの挙動の関係性を示41した。 また、合成セルオートマトンの例をいくつか挙げ、 サイズは小さいが、 合成により最大周期をもっセルオートマトンが構成できることを示した。

今後は、合成に関して可換となる為の遷移関数の組の条件のさらなる考察、 基本となるセルオートマトンの挙動解析を進めることで、最大周期をもつ合成セルオートマトンの系統的な構成を目指す。

参考文献[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. volume55, p601-644 (1983)[6] 石田俊一，井口修一群上のセルオートマトンにおける遷移関数の合成とその可換性について，応用数学合同研究集会報告集、 p112-117(2011)

42

図 1: CA90(5)$\infty\infty$

図 3: $CA\Re 1(5)xCA240(5)$43

図 5: $CA150(5)$

図 4:CA15(5)$m$

図 6: $CA15(5)xCA150(5)$