44
Cellular automata and their eigenvalues
東洋大学

総合情報学部

佐藤忠一

Tadakazu Sato

Department of Information Science and Arts
Toyo University

1.

まえがき

一次元セルオートマトンは数学的には記号列上の行列の固有値問題である。固有値問題の行列はふつう複素数体上の行列である。量子力学における固有値問題も無限次元ではあるが関数環上の行列でその成分は可換環である。しかし、セルオートマトンは非可換環上の行列の固有値問題である。セルオートマトンの対象は記号列で乗法は連接である。
連接は最も自然な非可換演算である。複素数体上の行列を非可換環上の行列に広げるにはいろいろあるが記号列上の固有値問題は複素数体上の固有値問題の自然な拡張になっている。

セルオートマトンはその振る舞いをあらわす並列写像の性質によって単射、定数対1写像、全射、非全射の4つに大きく分類される。本論文では各クラスの固有値、固有ベクトルについて論じる。

2. 諸定義一次元セルオートマ \vdash ン CA とは CA=<Z, Q, N, f> の四組で与えられる。ここでZ は整数の集合で各オートマトンが配置されている位置の集合表わす。
Q は各オートマトンの状態を表す記号列の有限集合、

N は Z の有限部分集合で近傍と呼ばれる。

局所関数 f : Q^{|N|}arrow Q は Q=\{a_{1},\cdots,a_{m}\}, |N|=n のとき m 状態、スコープ幅 n の局所関数という。 c:Zarrow Q なる写像 c を様相といい、各オートマトンの状態の分布を表わす。この様相に局所関数 f で一斉に変換すると新しい様相 c' は

c'(i)=f(c(i),c(i+1),\cdots, c(i+|N|-1))

for alli\in Zで与えられる。 Carrow c' なる対応を為 (c)=c' と書く。 C(Q) で様 Bの集合を表すとシフト写\grave{}像 \sigma : C(Q)arrow C(Q) は \sigma(c)(i)=c(i+1) で定義される。 k\in Z に対して、写1像\sigma^{k}f_{\infty} : C(Q)arrow C(Q) を11写\}像という。

45
Q の元の連接を乗法とすると Q^{*} は単位元 1 (null word) をもつモノイ ドである。 w\in Q^{*}に対して |w| はワードの長さを表す。 C を複素数体とする。 C の元の長さは 0 である。

\forall_{w\in Q^{*} に対してn\psiの転置をWを反転させたワードを tw と表す。

t(rw) =\overline{r}^{t}wと定義する。ここで \overline{r} は r\forall_{r\in C^{\forall}w\in Q^{*}} に対してと共役な複素数である。

\forall_{r_{1},r_{2}\in C^{\forall}w_{1},w_{2}\in Q} に対して t(r_{1}w_{1}+r_{2}w_{2} ) =^{t}(r_{1}w_{1})+^{t}(r_{2}w_{2}) と定義する
A\in M_{n,m}(Q) に対して A=\{w_{i,j}\} の転置行列 tA を tA=\{^{t}w_{j^{j}}, } と定義する。ここで、
0w_{ij}\in R(Q) また、2つの列ベクトル u, v に対して内積を <u, v>=^{t}uv と定義する。
3. 局所関数の行列表示m

状態スコープ幅 n の局所関数 f : Q^{n}arrow Q からドブルーチングラフを次のよう作る。グラフのノードの集合は Q^{n-1} とする。ノード x_{1}\cdots, x_{\bullet-1} から ノード x_{2}\cdots,x.のエッジに f(x_{1}\cdots, x_{n}) の値を付ける。グラフは有向グラフである。このグラフの状態遷移行列を A(f) と書く。この行列のサイズは m^{n-1}\cross m_{o}^{n-1} モノイドに加法 (or) を入れ、加法,乗法に分配の法則を用いて Q^{*} から記号列上の非可換環 R(Q) が自然に定義される。

A(f) は R(Q) 上の行列である。

例1.

m

状態スコープ幅2の局所関数 f(x,y) の行列表現 A(f) はA(f)=\begin{ar y}{l f(a_{1},a_{1}) \cdots fi(a_{1},a_{m}) f(a_{m},a_{1}) \cdots f(a_{m},a_{m}) \end{ar y})
4. 並列写像の性質
並列写像の単射性、全射性を判定するアルゴリズムは1次元のセルオートマトンに限り、知られている[1] 。2次元以上のセルオー \vdash マトンではそのよ \check{9} なアルゴリズムは存在しないことが知られている [3]_{0}定理1.

f を m 状態、スコープ幅 n の局所関数とする。

\lambda_{m}=(a_{1}+\cdots+a_{m}) とする。

為は単射であるとき次の命題が成り立つ。
(1)

A(f) は唯一の非零の固有値 \lambda_{m} を持つ。

(2) rankA (f)^{n}=1vとなる最小の正の整数を k とすると A(fi)^{k}=\mathcal{V}^{t}u ,ここでと tu はそれぞれ A(f) の固有値 \lambda_{m} の列固有ベクトルと行固有ベクトルである。

またそれらの内積は

tuv=\lambda_{m}^{k}注意1. 上記の定理は局所関数のスコープ幅nには無関係で状態数mだけで決まる。

46
例2. 単射である例を示す。

A(f)=\{beginary}{l a_4},{ a_2},{ a_1},{ a_3},{ a_4},{ a_2},{ a_1},{ a_3},{ \end{ary}\\{beginary}{l _4,a}{2_ a1},{l_3a} {4,_a2}{ _1,a}{3_ \end{ary} [_{a 1}+a_{3}^a_{2}+a_{4}a_{1} 2+a_{3} 4)=[_{a 1}+a_{3}^a_{2}+ a_{4}a_{1} 2+a_{3} 4)(a_{1}+a_{2}+a_{3}+a_{4})(a_{1}+a_{4},a_{1}+a_{4},a_{2}+a_{3},a_{2}+a_{3})[_{a \imath},a_{\imath}, a_{3},a_{3}^a_{4},a_{4},a_{2},a_{2}a_{\imath} _{4}',a_{1} 4'a_{3} 2' a_{3} 2)を状態遷移行列とする。

A(f) の列固有ベク トルと行固有ベク トルを求めると次のようになる。

=(a_{1}+a_{2}+a_{3}+0_{4})(a_{1}+a_{4},a_{1}+a_{4},a_{2}+a_{3},a_{2}+a_{3})A(f)^{2}=[_{a 1}+a_{3}^{a_2}+a_{4}a_{1}a_{2}+ a_{3}a_{4})(a_{1}+a_{4},a_{1} +a_{4},a_{2}+a_{3},a_{2}+a_{3})(a_{1}+a_{4},0_{1}+a_{4},a_{2}+a_{3},a_{2}+a_{3})[_{a 1}+a_{3}^{a_2}+a_{4} a_{1}a_{2}+ a_{3}a_{4})=(a_{1}+a_{2}+a_{3}+0_{4})^{2}

また、行ベク トルと列ベク トルの内積は並列写像が定数対1写像とは適当な正の整数 k に対して、任意の様相の並列写像による原像の集合の個数が常に k 個になることである。fi が ノで置換的であるとは ノ以外の変数を固定して ノのみの 1 変数関数としたときそれが置換的(単射) になることでxxxある[2] 。
命題1.
xf を m 状態スコープ幅 n の局所関数とする。

f(x_{1}, \cdots, x_{n}) が x_{1} で置換的でかつ. で置換的ならば為は m^{n-1} 対1写像である。

定理2.

mを正の整数とする。

写像は m 対1写像であり,f(x, y)=x+(m-1)ymod mの線形局所関数の並列

A(f) はスペク トル分解される。

A(f)=\{beginary}{l a_m} {-1 .\cdota_{2} 1a_{} m\dots.c a_{3} 2: \dots _{m-2} a_{m-3}.\cdot0_{m}a -1 _{m} a_{m-2}.0_{1am}\end{ary}\, P\equiv\{begin{ary}l \end{ary}\

とおくと

47
A(f)=a_{m}l+a_{m-1}P+a_{m-2}P^{2}+\cdots+a_{1}P^{m\dashv},
ここで P^{m}=I, G=\{P^{k}|k=1, \cdots, m\} は可換群。

従って,各 p^{k}(k=1, \cdots, m) は同時に対角化され、次式のようにスペク トル分解される。

P=e^{\iota 2\pi/m}E_{1}+\cdots+(e^{\iota 2\pi/溺})^{j}E_{j}+\cdots+(e^{i2\pi/m} )^{m}E_{m} より
P^{k}=(e^{i2\pi/m})^{k}E_{1}+\cdots+(e^{i2\pi/m})^{j^{k}}E_{j}. +\cdots+(e^{i2\pi/m})^{mk}E_{m},
ここで故に

I=E_{1}+\cdots+E_{m},E_{j}E_{k}=E_{k}E_{j}=E_{k}\delta_{j,k}A(fi)= \sum_{k=0}^{m-1}a_{m-k}P^{k}=\sum_{k=0}^{m-1}0_{m-k}\sum_{J=1}^{m} (e^{i2\pi/m})^{f^{k} E,\cdot, ここで、\lambda_{j}=\sum_{k=0}^{m-1}a_{m-k}(e^{i2\pi/m})^{jk}

とおくとA(f)= \sum_{j=1}^{m}\sum_{k=0}^{m-1}a_{m-k}(e^{i2\pi/m})^{jk}E_{j}=\sum_{k=1} ^{m}\lambda_{j}E_{j}5セルオートマトンの直和

A=\{a,,j\}\in M_{n}(Q_{1}), B=\{b_{k,\ell}\}\in M_{m}(Q_{2}) に対して, A\otimes B\in M_{nm}(Q_{1}\oplus Q_{2}) は定義

A\otimesB=[_{a n1}B,a_{n }B^{a_]1}B.'\cdot.\cdot\cdot.\cdot.'a_{]n}B:) で与えられる。ここで、 a_{l\dot{j}.B=[_{(a j},b_{m1}),(a_{ij},b_{m })^{(a_i{j}.'b_{1}.)' \cdot.\cdot.\cdot.'(a_{lj}.'b_{\imath}m)j: ) とする。
性質1. テンソル積は次の性質を持つ。
(1) A\otimes(B+C)=A\otimes B+A\otimes C(2)(A+B)\otimes C=A\otimes C+B\otimes C(3)(A\otimes B)(C\otimes D)=AC\otimes BD(4)t(A\otimes B)=^{t}A\otimes tB(5)

tr(A\otimes B)=(tr4trB)(6)\lambda(A\otimes B)_{i,j}=(\lambda(A)_{i},\lambda(B)_{j})ここで \lambda(A)_{i} は A の i 番目の固有値である。
2つの1次元セルオートマトン CA_{1}=<Z, Q_{1}, n_{1}, f_{1}> とCA_{2}=<Z, Q_{2}, n_{2}, f_{2}>の直和は次のように与えられる。

CA_{1}\oplus CA_{2}=<Z, Q_{1}\cross Q_{2} , (n_{1} , n_{2}) , f_{1}\oplus f_{2} >その状態遷移行列は A(fi_{1}\oplus f_{2})=A(f_{1})\otimes A(f_{2}) で与えられる。ここで右辺はテンソル積である。

性質2.

(fi_{1})_{\infty} を k_{1} 対1写像、 (fi_{2})_{\infty} を k_{2} 対1写像のとき、 (f_{ \imath} \oplus f_{2})_{\infty} は k_{1} ち対1写像である。

例3. f(x, y)=x+ymod 2 をスコープ幅2の線形局所関数とし (f\oplus fi) を考える。
2対1写像の直和なので並列写像は4対1写像である。

0rightarrow a_{2},1rightarrow a_{1} で符号化する

48と状態遷移行列は (fi)=(_{a_{1},a_{2} ^{a_{2},a_{]} ),A

A(f) の2つの固有値 r_{1}, r_{2} は \gamma_{1}=a_{2}-a_{1},v_{1}, v_{2} ltk

v_{1}= \frac{1}{\sqrt{2} (\begin{ar y}{l -1 \end{ar y}) , v_{2}= \frac{1}{\sqrt{2} (\begin{ary}l {\imath}1\end{ary}) ,\gamma_{2}=0_{1}+a_{2}でこれらの固有ベクトルv_{j}v_{;}=\delta_{i,j}, E_{j}=v_{j}v_{j}(j=1,2) よ 1\theta_{\ovalbox{\t smalREJ CT}

A(f)=\gamma_{1}v_{1}^{t}v_{1}+7_{2}v_{2}^{f}v_{2}=7_{1}^{E_{1}}+\gamma_{2}E_{2}= \frac{1}{2} (\begin{ar ay}{l } 1 -1 -1 1 \end{ar ay}) (a_{2}-a_{1})+ \frac{1}{2} (\begin{ar y}{l 1 1 \end{ar y}) (a_{2}+a_{1})直和の遷移行列はテンソル積で表されるのでA(f)\otimesA(f)=[_{a1},0_{)(a_{1}, 2)(a_{2}, 1)(a_{2}, )} ^{(a_2} {),(a_{2} 1),(a_{1} 2),(a_{1} )}(a_{\imath},'_{2}), (a_{1}, )(a_{2},' ),(a_{2} \imath})(_{2},a \imath}),(_{2}a {2}),(a_{1} ),(a_{1} 2)
A(f)\otimes A(f) の4つの固有値は\lambda_{1}= (a_{2}, a_{2})-(a_{2}, a_{1})-(a_{1}, a_{2})+(a_{{\imath}}, a_{1})\lambda_{2}= (a_{2}, a_{2})+(a_{2}, a_{1})-(a_{1}, a_{2})- ( a_{1} , aı)\lambda_{3}= (a_{2}, a_{2})-(a_{2}, a_{1})+(a_{1}, a_{2})- ( a_{1} , aı)\lambda_{4}= (a_{2}, a_{2})+(a_{2}, a_{1})+(a_{1}, a_{2})+(a_{1}, a_{1})
性質1の (4) より \lambda_{1}=(\gamma_{1}, \gamma_{1}) , \lambda_{2}=(\gamma_{1},\gamma_{2}), \lambda_{3}=(\gamma_{2},\gamma_{1}), \lambda_{4}=(\gamma_{2},\gamma_{2}) が成立。
一方、

A(f)\otimes A(f) のスペクトル分解はA(f)\otimes A(f)=(7_{1}^{E_{1}+}7_{2}^{E_{2})\otimes(\gamma_{1}E_{1}+\gamma_{2}E_{2})}=(\gamma_{{\imath} ,\gamma_{{\imath} )(E_{1}\otimes E_{1})+(\gamma_{1}, \gamma_{2})(E_{1}\otimes E_{2})+(\gamma_{2},\gamma_{{\imath} )(E_{2}\otimes E_{1})+(\gamma_{2},\gamma_{2})(E_{2}\otimes E_{2})=\frac{\lmbda_{1}4[-1 -1 1 -1 1 -1 1)+\frac{\lambda_{2} 4[-1 1 -1 1 -1 1 -1 )+\frac{\lmbda_{3}4 \{begin{ar y}{l 1- l 1 - 1-l -1 -l 1l- \end{ar y}\+frac{\lmbda_{4} \{beginary}{l 1 l 1 l 1{\imath}1 1\end{ary}\定理3.

f を m 状態スコープ幅 n の局所関数とする。

\lambda=(a. +\cdots+a_{m}) のとき次の命題は等価である。

(1) んは全射である。
(2) A(fi) は固有値 \lambda を持つ。

系1. 並列写像は単射であれば全射である。
例4. 定数対1写像でない全射の例

49

A(f)=(\begin{ar y}{l a, c b, b c, a \end{ar y}),[_{c, a}^{a, c}b,b,b\Vert_{-1}^{1}0)=[_{a-c}^{a-c}0)=[_{-}10_{1})(a-c) (\begin{ary}l a cb, c, a\end{ary}) [-10 )=(\begin{ar y}{l 0 0 \end{ar y}),より、固有値 a-c と 0 の固有ベクトルはヌルワードで表現される。
次に固有値 \lambda=a+b+c の固有ベクトルを求める。
X は x\lambda=\mathcal{A}x を満たす任意のノンゼロの式。
z を次式で定義すると

z= \sum_{k=0}^{\infty}(a-c)^{k}cx\lambda^{-1}\lambda^{-k}\lambda=a+b+c の固有ベクトノレは

v=[b\lambda^{-1}zx)となる。

6. 参考文献[1] S. Amoroso and Y. N. Patt, Decision procedures for surjectivity and injectivity ofparallel maps for tessellation structures. J.Comput. Systems Sci.6 (ı972),448‐464.

[2] G. A. Hedlund, Endomorphisms and automorphisms of shift dynamical systems.
Mathematical systems Theory 3 (1969), 320‐375.
[3] J. Kari, Reversibility and surjectivity problems of cellular automata,J. Comput.System Sci. 48 (1) (1994), 149‐ı82.