数理解析研究所講究録1020 巻 1997 年 103-126

103

セルオートマトンの保存量
京都大学総合人間学部

1

武末真二 (TAKESUE, Shinji)

はじめに
力学系の議論をする際に、 まず考えるべきことは、系がどのような構造を持つかということであろう。あらわに見えている構造もあれば、 隠れた構造もある。構造を理解することによってはじめて、その上に立った応用の議論が可能になる。離散力学系であるセルオー
トマトン$(\mathrm{C}\mathrm{A})$においても、 この研究会の大きなテーマであるソリトンセルオートマトンのように美しい構造を示すものがある。 しかし、 もちろんソリトンだけが$\mathrm{C}\mathrm{A}$の取りうる構造ではない。 それ以外の構造についても調べておくことは意味のあることであろう。
ここでは$\mathrm{C}\mathrm{A}$の持つ保存量に着目してみよう。 ソリトンセルオートマトンでは無限個の保存量が存在することがいえるが、保存量ということだけに注目してみれば、 ソリトンとは無関係にその存在条件を導き出すことができる。以下では、$\mathrm{C}\mathrm{A}$がある形の保存量を持つための必要十分条件を導き、それをもとにいくつかの例について具体的に保存則を求める。 また、 そのような保存章を持つ

2$\mathrm{C}\mathrm{A}$の動力学的特徴についても述べる。

保存量条件
この節ではまず簡単な形の$\mathrm{C}\mathrm{A}$について保存量条件を求め、後の節でその–般化を考えることにする。

次の形の 3 近傍の 1 次元$\mathrm{C}\mathrm{A}$を考えよう。

(1)$\mathrm{x}_{i^{+}}^{\mathrm{t}1}=\mathrm{g}(\chi_{i-1}, \chi \mathrm{x}_{i}^{\mathrm{t}})\mathrm{t}\mathrm{t}i’+1$

ここに、$\mathrm{x}_{i}^{\mathrm{t}}\in\chi$は時刻$\mathrm{t}\in \mathbb{Z}_{+}=\{\mathfrak{n}\in \mathbb{Z}|\mathrm{n}\geq 0\}$におけるセル$i\in \mathbb{Z}$の状態を表す。 セルが取り得る状態の集合 X は保存量条件を導くためには任意で良いが、 この条件を用いて実際に保存量を求めるためには有限集合でなければならない。セル
態はセル

$i$

$i$

の次の時刻における状の近傍 $i-$ ] $\sim i+1$ の現在の値によって決まり、状態の更新はすべてのセルで同時に行われる。 したがって、 3 変数の写像佳:$\mathrm{X}^{3}-\prec \mathrm{X}$を与えると時間発展のルールが 1つ決まる。後で詳しく議論することになる 2 つの例を紹介しておこう。

104

例 1: $\mathrm{X}=\{0,1\}$ の場合を Elementary CA (ECA) と呼ぶ [1]。関数佳は 3 変数のフ “ 一ノレ関から (1, 1, 1) までの 8 個の値に対してそれぞれ または 1 を割
数であり、
$0$

$(0,0, \mathrm{o})$り振ることにより決まるので、 ECA には $2^{8}=256$ 個のルールが属することになる。
これらを Wolfram にしたがって(2)$\mathrm{N}_{\mathrm{g}}=\sum\sum 111\sum 2^{4}\chi+2_{\mathrm{U}+}\mathrm{z}(\mathrm{g}\mathrm{x},v, z)$$\mathrm{x}=0v=0\mathrm{z}=0$という番号を用いて、「ルール$\mathrm{N}_{\mathrm{g}}$」 と呼ぶことにしよう。 (すなわち、「ルール O」から「ルール $255$ 」 までがある。)
例 2: $\mathrm{X}=\{0,1\}^{2\iota},$$\mathrm{X}_{i}=(\sigma_{i’ i}^{\mathrm{t}}\theta^{\mathrm{t}})\in \mathrm{X}$と分解したとき、時間発展則が$+:\{\mathrm{o}, 1\}^{3}arrow\{0,1\}$を用いて$\sigma_{i}^{\mathrm{t}+1}$$=$$\delta_{i}^{\mathrm{t}+1}$

$=$

{

(3)

$(\sigma_{i-\iota)}\sigma\sigma\iota)\mathrm{t}\mathrm{t}\iota\oplus i’ i+\delta_{i}\mathrm{t}$(4)$\sigma_{i}^{\mathrm{t}}$と表せるものを Elementary Reversible CA (ERCA) と呼ぶ。 ただし \oplus (は代数でいう排他的論理和) を表$0\oplus 0=0,0\oplus 1=1\oplus 0=1$ なる 2 項演算 ($\rceil\oplus 1=$$\text{フ^{}\backslash }-\backslash l\mathrm{s}$す。 これが可逆 (reversible) であることは、式 (3), (4) から逆の時間発展が$=$$\sigma_{i}^{\mathrm{t}}$$=$$\theta_{i}^{\mathrm{t}}$

.

(5)

電+1

(6)

$\mathrm{f}(\theta_{i-1i}^{\iota 1}+, \theta\iota+1, \theta^{\mathrm{t}}+1i+1)\oplus\sigma_{i^{+}}\mathrm{t}1$) 関数
によりルールが決まと書けることから明らかである。やはり 3 変数の(式 (2) のるので、 ERCA も ECA と同様 256 個のルールを持つ。 これらを番号.
$\text{フ^{}\backslash ^{\backslash }}-$$\mathrm{s}$$+$$\mathrm{N}_{\mathrm{f}}$$\mathrm{g}$に {を代入したもの)$255\mathrm{R}\rfloor$

さて、周期と「可逆」 を表す “ ” を用いて 「ルール OR」から 「ルール$\mathrm{R}$までの名前で呼ぶことにしよう。
$\mathrm{N}$の周期境界条件$(\mathrm{x}_{i+\mathrm{N}}^{\mathrm{t}}=\mathrm{x}_{i}^{\mathrm{t}})$のもとでの 1 次元$\mathrm{C}\mathrm{A}(1)$に対し、次の形の加法的な量を考えよう。
(7)$\Phi(\{..\mathrm{x}_{i}^{\mathrm{t}}\})=\sum_{i=0}^{\mathrm{N}-}\mathrm{F}(1\mathrm{x}_{i)}\mathrm{t}\mathrm{X}_{i+\iota}\ldots, \chi i+\alpha)\mathrm{t}\mathrm{t})$ただし、$\alpha\geq 0$は与えられた整数、$\mathrm{F}:\mathrm{X}^{\alpha+}1arrow \mathbb{R}$

えられたとき、任意の N 、任意の初期条件
刻$\mathrm{t}$において成り立つとき、$\Phi$$\{\mathrm{x}_{i}^{0}\}$は $\alpha+1$ 変数の関数である。ルールが与に対してを加法的保存量、$\mathrm{F}$$\Phi(\{\mathrm{x}_{i}^{\mathrm{t}+1}\})=\Phi(\{\mathrm{x}_{i}^{\mathrm{t}}\})$

が任意の時をその密度関数と呼ぶ。

服部と著者は論文 [2] にお恥て加法的保存量についての以下の定理を証明した。

105

定理

$\Phi$

が加法的保存量となるための必要十分条件は、任意の$\mathrm{x}_{0},$$\mathrm{x}\iota_{)\alpha}\ldots,\mathrm{x}+2\in\chi$に対して次式が成り立つことである。
$\mathrm{G}(\mathrm{x}_{0,1}\mathrm{x}, \ldots, \mathrm{x}\alpha+2)-^{\mathrm{p}(,\mathrm{x}_{\alpha+1}}\chi_{1}\mathrm{x}_{2_{)\cdot)}}..)=$

ただし、 関数$\mathrm{G}:\mathrm{X}^{\alpha+3}arrow \mathbb{R}$I(8)$(\mathrm{x}_{0_{)}1}\chi, \ldots, \mathrm{X}_{\alpha+}1)-\mathrm{I}(\mathrm{x}_{1}, \mathrm{x}2, \ldots, \chi\infty+2)$は(9)$\mathrm{G}(\mathrm{x}_{0}, \chi 1, \ldots)\mathrm{x}_{\alpha}+2\mathrm{I}=\mathrm{F}(\mathrm{g}(\chi_{0}, \chi_{1}, \chi_{2}\mathrm{I}, \ldots, \mathrm{g}(\mathrm{x}_{\alpha}, \mathrm{X}\alpha+1, \mathrm{x}_{\infty}+2))$

により定義され、 関数 I:$\mathrm{X}^{\alpha+2}arrow \mathbb{R}$は$\mathrm{I}(\chi 1\chi 2,.\cdots,\mathrm{x}\infty\backslash \cdot’.+2)=-\sum_{i=1}^{\alpha+2}[\mathrm{G}(\mathrm{P}, \ldots, \mathrm{P}, \mathrm{x}1_{)}\cdots, \chi i)-\mathrm{F}(\mathrm{p}, \ldots, \mathrm{P}, \mathrm{X}1)\ldots, \mathrm{X}i-1)]$である。 ただし、は$\mathrm{F}(\mathrm{P}, \ldots, \mathrm{p})$$\mathrm{P}\in\chi$は任意の固定値を表す。 ( $i=1$ のとき、(10)$\mathrm{F}(\mathrm{P}, \ldots, \mathrm{P}, \mathrm{x}_{1_{)}\cdots,i-\iota}\chi)$を表す。 もしくは I には定数項の不定性があるので、$0$としても良い。)

式 (8) はいわゆる 「連続の式」の離散版である。 この定理はそれが保存則と等価であることを示し、 さらに保存量の流れ I を保存量密度$\mathrm{F}$と時間発展ルール$\mathrm{g}$を用いて表す方法を与えるものである。

定理の証明は以下に示すように簡単にできる。次の補題を示せばよい。
補題 1$\mathrm{a}+1$

変数関数$\mathrm{H}:\mathrm{X}^{\mathfrak{a}+1}arrow \mathbb{R}$に対し、恒等的に(11)$\sum_{i=\mathit{0}}^{\mathrm{N}-1}\mathrm{H}(\mathrm{X}i, \mathrm{X}i+\iota, \ldots, \mathrm{x}i+\mathrm{a})=0$が成り立つならば、$\mathrm{a}$変数関数$1<:\mathrm{X}^{\mathrm{a}}arrow \mathbb{R}$(12)$\ldots)\mathrm{x}_{i})$$1<(_{\mathrm{X}_{1}}, \mathrm{X}_{2\cdot\cdot,\mathrm{a}},.\chi)=-\sum_{i=1}\mathrm{H}(^{\mathrm{p}}, \ldots)\mathrm{p}_{\mathrm{x}},\iota,$を用いて$\mathrm{H}(\mathrm{x}_{0)}\chi_{1}, \ldots)a\mathrm{x}1=\mathrm{K}(\mathrm{x}_{0}, \mathrm{x}\iota, \ldots, \mathrm{x}a-1)-\mathrm{K}(\chi 1, \chi_{2,\ldots,a}\mathrm{x}\mathrm{I}$(13)と書ける。 またその逆も成立する。
証明:.

式 (13)ればよい。

$\Rightarrow$

式 (11) は自明なので、式 (11)$\mathrm{H}(\mathrm{x}_{i}, \mathrm{x}_{i+}1, \ldots)\chi i+\mathrm{a})$$\mathrm{H}(\mathrm{x}i, \mathrm{x}i+1, \ldots)\mathrm{X}i+\mathrm{a})|\mathrm{x}_{0}=\mathrm{P}$$\Rightarrow$

式 (13) を十分大きなの独立変数が恥を含むとき、. その値を$\mathrm{N}$$\mathrm{P}$について証明すと置いたものをと書くことにすると$\sum_{i=0}^{\mathrm{N}_{-}\iota}[\mathrm{H}(\chi_{i}, \chi_{i+\rceil}, \ldots, \mathrm{X}_{\mathrm{i}+}\mathrm{a})-\mathrm{H}(\mathrm{X}i, \mathrm{X}i+1, \ldots, \mathrm{X}_{i+}\mathrm{a})|\mathrm{x}0=\mathrm{p}]=0$

(14)

106

が成り立つ。

$\mathrm{x}_{0}$を含んでいない項はキャンセルするので、 これは(15)$\sum_{i=-\mathrm{a}}^{0}[\mathrm{H}(\chi i)i\chi+^{\iota,\ldots i} , \mathrm{x}+\mathrm{a})-\mathrm{H}(_{\mathrm{X}_{i}}, \mathrm{x}i+1, \ldots)\mathrm{x}i+\mathfrak{a})|\mathrm{x}_{0}=\mathrm{P}]=0$と同じ。 ここで、$\mathrm{x}_{-1}=\mathrm{x}_{-2}=\ldots=\mathrm{X}-\alpha \mathrm{P}=$とおくと、式 (12) の$\sum_{i_{-}-\mathrm{a}}^{0}[\mathrm{H}(\mathrm{p}, *\cdot., \mathrm{P}, \mathrm{x}_{0)}\mathrm{x}1, \ldots, \mathrm{X}i+\mathrm{a})-\mathrm{H}(\mathrm{p}, \ldots \mathrm{P})’ \mathrm{X}\iota).

.

$\mathrm{K}$の定義より、, , \mathrm{x}_{i+\mathrm{a}})]$$\mathrm{x}_{\mathrm{a}})^{*})-\mathrm{K}(\mathrm{x}0, \ldots)\chi_{\mathfrak{a}}-\iota)-\mathrm{H}(\mathrm{P}, \ldots, \mathrm{p})$$=$$\mathrm{H}(\mathrm{x}_{0}, \mathrm{x}_{1,..\prime}, \mathrm{x}_{\mathrm{a}})+,\mathrm{K}(\chi_{\mathrm{l}}..,$

$=$

$0$

(16)

が得られる。 ところで、式 (11) ですべての変数を$\mathrm{P}$とおけば$\mathrm{H}(\mathrm{p}, \ldots \mathrm{p}))0=$であることがわかる。 したがって、式 (13) が成立する。 口定理を証明するためには、(17)$\mathrm{H}(_{\mathrm{X}_{0},\mathrm{X},..\mathrm{X}}1\cdot)\alpha+2)=\mathrm{F}(\mathrm{g}(\mathrm{x}0, \mathrm{x}1, \chi_{2}1, \ldots, \mathrm{g}(_{\mathrm{X}}\alpha’\chi\alpha+1, \chi\alpha+2))-\mathrm{F}(\mathrm{X}1)\ldots, \mathrm{x}_{\alpha}+1)$として補題 1 を適用すればよいだけである。
ここで 2 点注意を述べる。 1 つは、保存量密度である。任意の関数$\mathrm{S}:\mathrm{X}^{\infty}arrow \mathbb{R}$$\mathrm{F}$はただ 1 つには決まらないということにより$\mathrm{F}’(\chi 0, \mathrm{x}1, \ldots, \mathrm{X}\alpha)=\mathrm{F}(\chi_{\mathit{0}},\mathrm{X}1, ‘.

.

. .,

, \mathrm{x}_{\alpha})+\mathrm{S}(\mathrm{x}_{01)}\mathrm{x})\ldots,\mathrm{X}\alpha-1)-\mathrm{S}(\chi_{1}, \chi 2).$$\mathrm{x}_{\alpha}$

(18)

)

と定義すると$\mathrm{N}-\mathrm{l}$(19)$\Phi(\{\mathrm{x}_{i}\})=\sum_{i=\mathit{0}}\mathrm{p}(_{\mathrm{X}}i, \ldots, \mathrm{X}i+\alpha)=\sum \mathrm{F}’(i=0\chi_{i}, \ldots,\mathrm{X}_{i}+\alpha)$4が成り立つので、
流れ$\mathrm{I}’$$\mathrm{F}’$も同じ加法的保存量の密度になる。 このとき、$\mathrm{F}’$に対応する保存量のは次のようになる。

$\mathrm{I}’(_{\mathrm{X}}0, \ldots,\mathrm{X}\alpha+\iota)$$=$$\mathfrak{s}(_{\mathrm{X}\mathrm{X}}0, \ldots,\infty+^{\iota})+\mathrm{s}(\mathrm{p}, \ldots, \mathrm{P})-^{\mathrm{s}}(\mathrm{x}1, \ldots, \mathrm{x}_{\alpha})-^{\mathrm{s}}(9(^{\mathrm{p}\mathrm{P}},, \mathrm{p}), \ldots, 9(\mathrm{P}, \mathrm{p}, \mathrm{P}))$$+\mathrm{S}(\mathrm{g}(_{\mathrm{X}}0,\chi 1,\chi 2), \ldots)\mathrm{g}(_{\mathrm{X}}\alpha-1)\alpha \mathrm{x},$$\mathrm{X}\alpha+1))$(20)

この任意性 (表面項の自由度) を取り去って、 がただ 1 つに決まるようにするためには、$\mathrm{F}$例えば$\mathrm{F}(\mathrm{P}, \mathrm{x}_{1_{)}}\lambda 2, \ldots, \mathrm{X}\alpha)=0$

(21)

107

といった条件をおけばよい。 こうすると式 (10) の右辺は$\mathrm{F}$の項が大部分消え、保存量条

件 (8) は、$\mathrm{G}(\mathrm{x}_{0,1)\alpha+2}\mathrm{x}\ldots, \mathrm{X})-\mathrm{F}(\mathrm{X}_{0}\ldots, \chi))\alpha=\sum_{0i=}^{\alpha+\mathrm{l}}[\mathrm{G}(\mathrm{P}, *\cdot., \mathrm{P}, \chi 1, \ldots, \mathrm{X}i+\iota)-\mathrm{G}(\mathrm{p},$$\mathrm{p}_{\mathrm{x}_{0}},,$$\ldots,$$\ldots,$$\mathrm{X}i$

Il

(22)
と多少簡単化される。
もう 1 つの注意は、密度関数自身が保存量となる場合があるということである。正確にうと、表面項を適当に選ぶことによって$=\square$(23)$\mathrm{F}’(\mathrm{X}_{i}^{\iota 1}, \mathrm{x}\ldots,\mathrm{x})+\mathrm{t}+1i+1’ i+\alpha \mathrm{t}+\iota=\mathrm{F}’(\chi_{i’ i+}\mathrm{t}\mathrm{X}^{\mathrm{t}}1’\ldots, \mathrm{X}_{i+}^{\mathrm{t}})\propto$が成り立つようにできる場合がある。 この場合、流れは当然恒等的に(24)$\mathrm{I}’(\mathrm{X}0, \mathrm{X}_{1}, \ldots, \mathrm{x}_{\alpha+}1)=0$となる。 このような保存量を局在保存量と呼ぼう。局在保存量が存在するとき、$\mathrm{X}^{\alpha+1}$

を$\mathrm{F}$の値によって、$\chi\infty+1=\bigcup_{\mathrm{a}}\mathrm{x}_{\mathfrak{a}}$,$\cdot$$\mathrm{X}_{\mathrm{a}}=\{(\chi \mathit{0})\ldots , \chi\alpha)\in \mathrm{X}^{\alpha+\iota_{1(_{\mathrm{X}}\ldots,)}}\mathrm{F}0)\propto \mathrm{x}=\mathrm{a}\}$と分解すると、セル $i\sim i+\alpha$ の値$\chi_{\mathrm{a}}$$(\mathrm{x}_{i},., \mathrm{x}_{i+}^{\iota})\mathrm{t}..\alpha$(25)

は、初期条件によって決まるある 1 つのの中でしか変化しない。 こうして加法的保存量は、式 (24) が成り立つ局在性のものと、そうでない伝播性のものとに分類される。

ECA, ERCA の保存量3

前節の結果を用いて ECA と ERCA の加法的保存量を求めてみよう。

ECA にはルール$0$からルール 255 までの 256 個のルールが存在するが、左右反転
佳 (X, $V,$や$0$$\mathrm{z}$

)

(26)

$\Leftrightarrow 9(\mathrm{z}, \mathrm{v}, \mathrm{x})$と 1 を入れ換える操作$\mathfrak{g}(\mathrm{x},\mathrm{v}, \mathrm{z})\Leftrightarrow\rceil-\mathrm{g}(1-\chi, ]-\mathrm{v},$$]-\mathrm{Z})$(27)

により移り変わるルールは同形なので、 これらを同–視すると 88 個の同値類に分類される。 したがって 88 個のルールについて考えればよい。

108$\alpha$を 1 つ固定すると、関数$\mathrm{F}(\mathrm{x}_{0}, \chi 1, \ldots, \mathrm{X}_{\alpha})$い。そのうち表面項の自由度が$2^{\alpha}$の独立変数の取り得る値は$2^{\alpha+1}$である。前節の注意を考慮に入れて、 (通りしかな$\mathrm{P}=0$

として)

(28)

$\mathrm{F}(\mathrm{o}, \mathrm{x}_{1,2}\chi, \ldots\chi))\alpha=0$の条件を課すと、$\mathrm{F}$は$\mathit{2}^{\alpha}$

個のパラメータ$\{\mathrm{b}\mathrm{k}\}1\leq \mathrm{k}\leq 2\alpha$を用いて以下のように表すことができる。
$\mathrm{F}(\chi 0, \chi 1)\ldots,$$\sum$$=$$\chi\propto)$...

$\mathrm{b}_{\mathrm{l}\mathrm{c}\mathit{0}}\mathrm{X}\chi \mathrm{x}\mathrm{a}\iota.\mathfrak{a}_{2}12$(29)$\mathrm{x}_{\alpha}^{\mathrm{a}_{\alpha}}$$(\mathrm{a}_{1}, \ldots, \mathrm{a}_{\alpha})\in\{0,1\}^{\infty}$$\mathrm{k}=1+\sum_{1=}^{\alpha}\uparrow \mathrm{a}_{1}2^{\mathrm{t}_{-}1}$$=$

この展開形の利点は、ある$\alpha$(30)$\mathrm{b}\iota \mathrm{x}_{0}+\mathrm{b}_{2}\mathrm{X}_{0}\mathrm{x}_{1}+\mathrm{b}_{3}\mathrm{x}_{0^{\mathrm{x}_{2}}}+\mathrm{b}_{4}\mathrm{x}_{012}\mathrm{x}\chi+\mathrm{b}_{50^{\mathrm{x}_{3}}}\mathrm{x}+\ldots$

における展開が、それより小さい$\alpha$の展開をそのまま含むということにある。

ECA のルールが与えられたとき、 この展開形を保存量条件 (8) に代入すると、パラメー
タ$\{\mathrm{b}_{1_{\mathrm{C}}}\}1\leq \mathrm{k}\leq 2\propto$

に対する線形同次の連立方程式が得られる。その独立解の個数を、 このルー

ルが持つ加法的保存量の個数と定義する。 この数はもちろん
法的保存量は、$\alpha’(<\alpha)$$\alpha$に依存し、 ある$\alpha$での加の保存量を含んでいる。

このようにして得られた保存量の個数とその具体的な形については論文 [2] を参照されたい。そこに、 $\alpha=6$ までのルール毎の加法的保存血の個数と、 $\alpha=4$ のすべての解が掲載されている。加法的保存量はルールによってさまざまであり、 1 個も保存量を持たない
ルールもあれば、任意の$\mathrm{F}$が保存量となるルールもある。保存量を持たないものも、$\alpha=6$で持たないというだけであって、 より大きな

ECA については$\mathrm{W}\mathrm{o}\mathrm{l}\mathrm{f}\mathrm{r}\mathrm{a}\mathrm{m}[1]$$\alpha$では持つのかもしれない。

による分類が有名である。彼は ECA および類似の$\mathrm{C}\mathrm{A}$を、ルールが生成する時空パターンによって次の 4 つのクラスに分類した。
クラス 1 一様な状態に収束する
クラス 2 領域に分かれ、各領域では周期的パターンに落ち着く
クラス 3 カオティック、 もしくはフラクタルな非周期的パターンを生成
クラス 4 複雑な局在パターンを生成$\alpha=6$の加法的保存量を持つルールは実はすべてクラス 2 に属している。 これは、大変雑な議論をすれば、次のように考えることができる。 クラス 1 では、 ほとんどどんな初期状

態から始めても、時間がたてば–様な状態に収束する。 したがって、保存量があったとしても、ほとんどの状態は–様な状態と同じ値を持つことになる。加法的保存量でそれを実109現するのは困難である。逆にクラス 3 は簡単なパターン (例えば 1 つのセルだけが 1 で、他のすべてのセルは$0$の状態) から始めてもフラクタル的な時空パターンを生成する。加

法的保存量は、 そのとき現れるすべての空間配位に対して同じ値を持つわけだから、 これも難しい。 クラス 4 は定義自身不明確なものだが、複雑な局在パターンの時間発展に対して、時刻$\mathrm{t}$によらない同じ値を与えるようにするためには、$\alpha$は相当大きくなければならないだろう。
次に ERCA の保存量について考える。 この場合も左右反転と$0$と 1 を入れ換える操作

により、 256 個のルールを 88 個の同値類に分けることができる。 ただし、 ECA と違って後者は$\mathrm{f}(\mathrm{x},\mathrm{v}, \mathrm{z})\Leftrightarrow+(1-\chi, ]-\mathrm{v},$$]-Z)$(31)$=$

で与えられるので、 ルール番号の分かれ方は ECA の場合と異なる。
変数を$\mathrm{x}_{i}^{\mathrm{t}}=(\sigma_{i}^{\mathrm{t}}, \theta_{i}^{\mathrm{t}})\in\{0,1\}^{2}\text{、}$こう。 ECA の場合と同様に保存量密度を$\mathrm{P}=(\mathrm{O}, 0)$$\mathrm{F}(\mathrm{x}_{0}, \ldots, \chi_{\infty})=\mathrm{F}(\sigma_{0}, \delta_{\mathit{0}};\ldots;\sigma_{\alpha}, \delta_{\alpha})$

と書

として、

$\mathrm{F}(0,0;\sigma 1, \theta 1;\cdots ; \sigma\alpha’\theta_{\alpha})=0$(32)の条件を課すと、 の–般形を$\mathrm{F}$.

$\mathrm{F}(\sigma_{0}, \theta_{0};\sigma_{1}, \theta_{\rceil\cdot;\sigma \mathrm{a}_{\alpha})}).$$=$$.\alpha$ ’$\mathrm{b}_{\iota}\sigma_{0}+\mathrm{b}2\theta_{0}+\mathrm{b}3\sigma 0\theta 0+\mathrm{b}4\sigma 0\sigma 1+\mathrm{b}_{5}\theta_{0}\sigma \mathrm{I}+\mathrm{b}_{6}\sigma_{0^{\delta\sigma}}\mathit{0}1+\mathrm{b}_{7}\sigma_{0^{\theta_{1}}}$$+\mathrm{b}_{8}\theta_{0^{\theta}\iota}+\mathrm{b}_{9}\sigma_{0}\theta_{\mathit{0}}\mathrm{e}_{1}+\mathrm{b}_{\iota 0}\sigma_{0}\sigma_{1}\theta_{1}+\mathrm{b}_{\mathrm{l}1}\theta_{\mathit{0}}\sigma_{\iota}\theta\iota+\mathrm{b}_{12}\sigma 0\theta 0\sigma 1\theta_{1}$(33)$+\mathrm{b}_{13}.$ $\sigma_{0}\sigma_{2}+\mathrm{b}_{1}4\theta_{0}\sigma_{2}+\ldots$.

$=$$\sum$$\mathrm{b}_{\mathrm{k}}\sigma_{\mathit{0}}^{\mathrm{a}0}\mathrm{a}_{0}^{\hat{\mathfrak{a}}}0\ldots\sigma_{\alpha\alpha^{\alpha}}^{\mathfrak{a}_{\propto \mathrm{e}}}\hat{\mathfrak{a}}$(34)$(\mathrm{a}_{\mathit{0},\mathit{0}}\hat{\alpha}, \cdots, \mathrm{a}_{\alpha},\hat{\alpha}_{\alpha})\in\{0,1\}^{2}\infty+2$.

$(\mathrm{a}_{0}, \alpha_{0})\mathrm{A}\neq(0,0)$$\mathrm{k}=\mathrm{a}_{\mathit{0}}+2\hat{\mathrm{a}}_{\mathit{0}}+\cdot 3\sum_{1=1}^{\alpha}(\mathrm{a}_{1}+2\hat{\alpha}_{\mathrm{t}})4^{\mathrm{t}}-1$のように 3$\mathrm{x}4^{\alpha}$

入し、に関して解くことにより、各ルールにおける加法的保存量が求められる。論文$\{\mathrm{b}_{\mathrm{k}}\}$[2] では$\alpha=\mathit{2}$個のパラメータ$\{\mathrm{b}_{\mathrm{k}}\}$

によって表すことができる。 これを保存量条件に代までの加法的保存量の個数と$\mathrm{F}$の関数形を求めたが、 ここでは $\alpha=3$ までの加法的保存量の個数を表 1 に示す。

表 1 に示した保存量の大多数は前節の注意で述べた局在保存量である。局在保存量が存在する系は、空間的に互いに相互作用しないいくつかの部分に分かれる傾向がある。たとえばルール$73\mathrm{R}$は$\mathrm{F}(\sigma_{0}, \delta_{\mathit{0};\sigma_{1}}, \delta_{\iota)}.\sigma 2)\theta_{2})=(1-\sigma_{0})(1-\delta_{\mathit{0}})\sigma 1\theta_{1}(1-\sigma_{2})(1-\theta_{1})$

(35)

110

に対し、与えられた での加法的保存
表 1: ERCA の加法的保存量。 ERCA の各量の数を示す。空欄は を表す。「ルール」の欄における Conj. は左端のルールに対して. は両方の操作を施したルール
反転したルール、 Refl. は左右反転したルール、を表す。
$-\mathrm{K}\mathrm{s}$$\alpha$$0$$0\Leftrightarrow 1$$\mathrm{C}.\mathrm{R}$111で表される局在保存量を持つが、$\mathrm{F}(\sigma i_{)}\delta i;\sigma i+\iota)\mathrm{e}i+1;\sigma_{i2}+$, 合 i+2) $=1$ となるのは(36)$(\sigma_{i}, \delta_{i}\cdot\sigma_{i+1}, \delta i+1;\sigma_{i}+2, \delta_{i+})2)=(0,0,1, \rceil, 0, \mathrm{o})$の場合だけであり、 それ以外はすべて$\mathrm{F}=0$となる。 したがって、 セル $i\sim i+2$ が初期条件で式 (36) の値を取れば、他のセルの状態に関わりなくすべての時刻において同じ値となり、 セル間の相互作用を阻む壁として機能する。 このような壁と壁にはさまれた領域

は、他の領域と無関係に時間発展する。 (図 1(a) 参照)。

(a)(b) ルール$\mathrm{K}\mathrm{s}-\mathrm{K}\mathrm{s}73\mathrm{R}$$24\mathrm{R}$

図 1: 局在保存量を持つルール。横軸はセル の位置、縦軸は下向きに時刻を表す。
を表し、空白はい l 占は$i$$\mathrm{t}$を表す。黒$\sigma_{i}^{\mathrm{t}}=0$$\sigma_{i}^{\mathrm{t}}=\rceil$

図 1(b) はルール

$24\mathrm{R}$の時間発展を示す。 このルールでは$\mathrm{F}(\sigma_{0}, \delta 0;\sigma_{1}, \delta 1)=(1-\theta_{\mathit{0}})\sigma_{1}+(]-\sigma_{1})\mathrm{e}1+\sigma_{\mathit{0}}(\theta 0-\mathrm{a}_{\rceil})$

(37)

112

が局在保存量となるが、 この場合は明確な壁のようなものはできていない。 )$\mathrm{s}-$$.$$59\mathrm{R}$.

$\mathrm{K}\mathrm{s}\mathit{2}7\mathrm{R}\text{、}$なども同様の性質を示す局在保存量を持っている。

局在しない加法的保存量だけが存在するルールでは、保存量が粒子のように動き回り衝突散乱する過程が見られる。 ルール$26\mathrm{R}$

は密度関数

(38)

$\mathrm{F}(\sigma_{0}, \delta_{0)}.\sigma 1_{)}\theta_{1})=(\sigma_{\mathit{0}}-\mathrm{a}_{\rceil})2+(\epsilon_{0}-\sigma\rceil)^{2}$で表される加法的保存量を持つが、 その時間発展の様子を図 2 に示す。

(a) 力学変数の時間発展
図 2:(b) 保存量の時間発展の時間発展。 (a) はを、 (b) は (a) に対応する式 (38) の保存量の時間発展を表す。黒い点は ( , 合も \mbox{\boldmath $\sigma$}F+I’’F)=2、灰色の点は 1 、空白は を表す。
$j\mathrm{s}-/\mathrm{s}\mathit{2}6\mathrm{R}$$\{\sigma_{i}^{\mathrm{t}}\}$$\mathrm{F}$$\sigma_{i}^{\mathrm{t}}$$0$このような ERCA の]- では、加法的保存量をエネルギーとみなして、統計力学を構成することができる。 Gibbs 流の統計力学の議論を行うための条件は、相空間体積の保存 (Liouville の定理) とエネルギー保存則の成立だが、前者は ERCA の可逆性から保証さ113

れているからである。 例えば分配関数は(39)$\mathrm{Z}=\sum \mathrm{e}^{-\beta\Phi(\{\sigma_{i},\sigma_{i}\}})$$\{\sigma_{i},\delta_{i}\}$で与えられ、通常の手続きにしたがって、逆温度と保存量の平均密度$\beta$$\Phi/\mathrm{N}$の問の関係が得られる。 また境界条件を変えて、熱源を表すように、両端の変数の時間発展を確率的にすると、熱伝導のシミュレーションができる。 こうしてを用いて統計力学の成立条$\mathrm{C}\mathrm{A}$

件について問うことが可能になる。 これらについては、文献 [3, 4, 5] を参照されたい。

ここでは、統計力学的応用には踏み込まずに、保存量を粒子、 もしくは準粒子とみなしたときの散乱の振る舞いについて述べる。 ルール

1と$91\mathrm{R}$の 2 個のルールについて考$\mathit{2}3\mathrm{R}$

えよう。これらは、次の密度関数で与えられる $\alpha=1$ の加法的保存量を共通に持っている。
$\mathrm{F}(\sigma_{0}\delta_{0};\sigma_{\rceil)}\delta\rceil))$$=$$\rceil+\sigma_{0}\mathrm{e}_{0+\theta}\sigma 11-[]-2(1-\sigma_{\mathit{0}})(1-\theta_{1})][1-\mathit{2}(1-\delta_{0})(1-\sigma_{1})|$

(40)

$=$

どちらのルールにも他の保存量が存在するのだが、今は無視しよう。上式の保存量を 「エネルギー」 と呼ぶことにする。無限系を考え、最もエネルギーの小さい基底状態を求めると、 空間的に –様、 時間的には周期 3 を持つ次の図のような時間発展を示す $\Phi=0$ の状態が得られる。 (この図は

電$=\sigma_{i}^{\mathrm{t}-1}$$\{\sigma_{i}^{\mathrm{t}}\}$$i$は右向き、、 時刻$\mathrm{t}$は下向きに増大する。

なので、 これで時間発展が完全に表せていることに注意。)

. .
.
. .
.

:.

. .

$\Phi=\rceil$

を表し、位置$0$$0$$\rceil$$0$$0$$\rceil$$0$$0$$\rceil$$0$$0$$\rceil$

$0$

$0$

$0$

$0$

$0$

$0$

$0$

$0$

$0$

$0$

$\rceil$$\rceil$$\rceil$$\rceil$

$0$

$0$

$0$

$0$

$0$

$0$

$0$

$0$

$0$

$0$

$0$

$0$

$0$

$0$

$0$

$0$

$0$

$\rceil$$\rceil$$\rceil$$\rceil$$\rceil$.

$\rceil$$0$$\rceil$

.
.

.

I1

の状態は存在できず、最もエネルギーの低い励起状態は $\Phi=2$ になる。 それには次の 5 種類のモードが存在する。 ($\mathrm{F}\neq 0$に関係するセルの値は太字で表す)

114

. .
.

$0$

$\mathit{0}$$0$$\rceil$

$0$

$0$

$0$

$0$

$0$

$0$

$0$

$0$

$\rceil$

$0$

$0$

$0$

$0$

1

1

1

1

1

1

1

$0$

$0$

$0$

$0$

$\rceil$

$0$

$0$

$0$

$0$

$0$

$0$

$0$

$0$

$\rceil$

$0$

$0$

$0$

$0$

1

1

1

1

1

1

$0$

$0$

$\rceil$$\rceil$

. .

.

.

.

$0$

$\rceil\cdot\rceil$$\rceil$.

\yen - ト “

$0$

$0$

$0$

$0$

$\rceil$

$0$

$0$

$0$

$0$

$0$

$\rceil$$\rceil$$\rceil$$\rceil$

1

1

1

1

$0$

$0$

$\mathit{0}$

$0$

$0$

$0$

$\rceil$

$0$

$0$

$0$

$0$

$0$

$0$

$\rceil$$\rceil$

1

1

1

$0$

$0$

$\rceil$$0$$0$$\rceil$$\rceil$$0$.

$\rceil$$\rceil$

$0$

$0$

$0$

$\mathit{0}$

$0$

$0$

$\rceil$$\rceil$

$0$

$0$

$0$

$\mathit{0}$

$0$

$0$

$\rceil$1$\rceil$$\rceil$$\rceil$

$0$

$0$

$0$

$\mathit{0}$$\mathit{0}$

$0$

$0$

$0$

$0$

$0$

1
$0$

$0$

$\mathit{0}$

$0$

$0$

$0$

$0$

$0$

$\rceil$$\rceil$

1

1

1

1

1

1

$0$

$\mathrm{S}$$\rceil$$\rceil$$\rceil$$\rceil$$\rceil$$\rceil$$\rceil$$0$$0$$\mathit{0}$$0$$\mathrm{B}$1$0$$\mathit{0}$

$0$

$0$

$\rceil$

$0$

$0$

$0$

$0$

$0$

$0$

$0$

$\rceil$$\rceil$

$0$

$0$

$0$

$\rceil$

$0$

$0$

$0$

$\rceil$$\rceil$

$0$

$0$

$0$

$0$

$0$

$\rceil$$\rceil$

1

1

$0$

$0$

\yen - ト “$\mathrm{C}$は周期 3 の静止したパターンを作る。 モ $-$ ト “

1$\rceil$$\rceil$$\rceil$$\rceil$$\mathrm{A}_{\text{、}}\mathrm{B}$.

$\rceil$

$0$

$0$

$0$

$0$

i\in - ト “

モード

$0$

$0$

$0$

$\rceil$1$\rceil$

- ト“

$0$

1

1

$0$

$\rceil$

$0$

$0$

$0$

$\rceil$

1

$0$

$0$

$0$

$0$

$0$

$0$

$0$

1

$0$

$\mathit{0}$

$0$

$0$

$\rceil$$\rceil$

$0$

1

$0$

$\rceil$$\rceil$$0$$0$$\mathit{0}$

$0$

$0$

$\rceil$$0$$0$$\mathit{0}$

$0$

$0$

$0$

$0$

$0$

$0$

$0$

$\mathit{0}$$0$$\mathit{0}$$\mathit{0}$q\doteqdot - ト “ A\yen
$0$

.

$0$

$\rceil$$\rceil$.

.

$\mathrm{S}$

$0$

$0$

$0$

. .

1

$\rceil$$\rceil$$\mathrm{D}$では、 時間が 3 進むと左へ

1 だけシフトする。 したがってエネルギーも $-$ ] $/3$ の速度で移動する。 同様に、モード$\mathrm{D}$は$\mathrm{C}_{\text{、}}$

1/3 の速度を持つ。 ここまでは、 両ルールに共通の性質である。

モード$\mathrm{S}$とその他のモード、 モード$\mathrm{A}_{\text{、}}\mathrm{B}$とモード$\mathrm{C}_{\text{、}}\mathrm{D}$は衝突が可能である。 2 体衝突の振る舞いを調べてみると、 これはルールによって異なる。例えば、 モード$\mathrm{S}$A の衝突は次のようになる。
$0$

$0$

$0$

$0$

$0$

$\rceil$

$0$

$0$

1

$0$

$0$

$\mathit{0}$$0$$\rceil$$0$$0$$\rceil$$\rceil$$\rceil$$\rceil$$\rceil$$\rceil$

$0$

$0$

$0$

$0$

$0$

$\rceil$$0$$\rceil$

$0$

$0$

$0$

$\mathit{0}$$\mathit{0}$$\rceil$$0$$\rceil$$\rceil$

$0$

$0$

$0$

$\rceil$

$0$

$0$

$0$

$0$

$0$

$0$

$\rceil$$\mathit{0}$$0$$\rceil$$\rceil$

1

1

$0$

$0$

$0$

$0$

$0$

$0$

1

$0$

$0$

$\rceil$

1

1

1

1

1

$0$

$0$

$\mathit{0}$

$0$

$0$

$\rceil$$0$$\rceil$$0$$\mathit{0}$

$0$

$0$

$0$

$\rceil$$\rceil$$\rceil$$\rceil$$\rceil$$\rceil$

.

1

1

1

1

$0$

$0$

$0$

$0$

$0$

$\rceil$$\rceil$$0$$\mathit{0}$

$0$

$0$

$0$

$0$

$0$

$0$

$0$

$0$

$\rceil$$\rceil$1

1$\rceil$$\rceil$$0$$0$$\rceil$

$0$

$0$

$0$

$0$

$0$

$\rceil$$\rceil$$\rceil$$\rceil$

$0$

$0$

$0$

$0$

$0$

$0$

$0$

$0$

$0$

$\rceil$$\rceil$$\rceil$

$0$

$0$

$0$

$0$

$\rceil$

$0$

$0$

$0$

$0$

$0$

$\rceil$$0$$0$$\rceil$

$0$

$0$

$0$

$0$

$0$

$\rceil$$\rceil$$\rceil$$\rceil$$\rceil$$0$$0$$\rceil$

$0$

$0$

$0$

$\mathit{0}$$0$$\rceil$

$0$

$0$

$0$

$0$

$\rceil$$\rceil$1$0$$\rceil$

$0$

1

1

1

$0$

$0$

$0$

$\rceil$

$0$

$0$

$0$

$\rceil$$\rceil$

$1$

1

$0$

$0$

$\rceil$$\mathit{0}$ルール$\rceil$$0$91$\mathrm{R}$$\mathrm{S}:\mathrm{A}arrow \mathrm{A}:\mathrm{S}$$\rceil$$0$$0$$\rceil$

$0$

1

$0$

$\rceil$$\rceil$

1

1

1

$0$

$0$

$\rceil$

$0$

$0$

1

1

$\mathit{0}$$0$$\rceil$$\rceil$$\mathit{0}$$1$$\rceil$$\rceil$

$0$

$0$

$0$

$\rceil$$\rceil$$\rceil$$\rceil$ル一$\mathrm{K}\iota\prime 123\mathrm{R}$$\mathrm{S}:\mathrm{A}arrow \mathrm{B}:\mathrm{D}$$\rceil$

$0$

とモード

115

ルール

1

$\mathit{2}3\mathrm{R}$$91\mathrm{R}$では、$\mathrm{B}$では、シフトを伴うだけで衝突後も衝突前と同じモードが現れるが、ルールと$\mathrm{D}$という全く別のモードに変化してしまう。 同様の現象が、衝突でも観測される。 この場合は、 モード$\mathrm{C}$$\mathrm{C}$とA のと A の距離によって、下図のように 2 種類の散乱が起こりうる。
$\mathit{0}$

$0$

$0$

$0$

$0$

$0$

$\rceil$$\mathit{0}$$\mathit{0}$$0$$\rceil$$\rceil$$\rceil$$0$$\mathit{0}$$\rceil$$\rceil$$0$$0$$\rceil$$\rceil$$0$$\rceil$$\rceil$

$0$

$0$

$0$

$0$

$\rceil$$0$$0$$\mathit{0}$$0$$\rceil$$\rceil$$0$$\rceil$$\rceil$$\rceil$$\rceil$$\rceil$$\rceil$

$0$

$0$

$0$

$\rceil$

$0$

$0$

$0$

$\mathit{0}$

$0$

$0$

$0$

$0$

$\mathit{0}$$0$$\rceil$$\rceil$$\rceil$

$0$

$0$

$0$

$0$

$0$

$0$

$\rceil$$0$$0$$\mathit{0}$$\mathit{0}$$\mathit{0}$$\rceil$$\rceil$$\rceil$$\rceil$$\rceil$$\mathit{0}$

$0$

$0$

$\rceil$$\rceil$$\rceil$$\rceil$$\rceil$$\rceil$

$0$

$0$

$0$

$0$

$0$

$0$

$\rceil$A$\rceil$$0$$\rceil$$0$$0$$\mathit{0}$$\rceil$$\rceil$$\rceil$

$0$

$0$

$0$

$0$

$\rceil$$\rceil$$\rceil$$0$$\mathit{0}$

$0$

$0$

$0$

$0$

$\mathit{0}$$0$$\rceil$

$0$

$0$

$0$

$\rceil$$\rceil$$0$$0$$\rceil$$\rceil$$\rceil$$\rceil$

$0$

$0$

$0$

$\rceil$$0$$\mathit{0}$$\mathit{0}$

$0$

$0$

$0$

$\mathit{0}$$\rceil$$\rceil$$\rceil$$0$$\rceil$$\rceil$$\rceil$$\rceil$$\rceil$$l\triangleright-l\triangleright 123\mathrm{R}$

$0$

$0$

$0$

$0$

$0$

$\rceil$$0$$\mathit{0}$$0$$\rceil$$\rceil$$\rceil$$\rceil$$0$$\mathit{0}$$\rceil$$\rceil$$0$$0$$\rceil$$0$$0$$\rceil$$\rceil$$\rceil$$0$$\mathit{0}$A$:\mathrm{C}$

1

$0$

$0$

$0$

$0$

$0$

$0$

$0$

$\rceil$$\mathit{0}$

$0$

$0$

$\rceil$$\rceil$$\rceil$$\rceil$$0$$0$$\mathit{0}$$\rceil$$\rceil$$0$$0$$\rceil$$0$$0$$\mathit{0}$$\rceil$$\rceil$$\rceil$

$0$

$0$

$0$

$0$

$0$

$0$

$\rceil$$\rceil$

$0$

$0$

$0$

$0$

$0$

$0$

$\rceil$$\rceil$$0$$\mathit{0}$

$0$

$0$

$\rceil$$\rceil$

$0$

$0$

$0$

$0$

$0$

$0$

$0$

$0$

$\rceil$$\rceil$$\mathit{0}$

$0$

$0$

$0$

$\rceil$$\rceil$$\rceil$

$0$

$0$

$0$

$0$

$\rceil$$\rceil$$\rceil$$0$$0$$\mathit{0}$$\rceil$$\rceil$$\rceil$$\rceil$$\rceil$$\rceil$

$0$

$0$

$0$

$0$

$\rceil$

$0$

$0$

$0$

$0$

$\rceil$$\rceil$$\rceil$

$0$

$0$

$0$

$\rceil$$\rceil$

$0$

$0$

$0$

$0$

$\mathit{0}$

$0$

$0$

$0$

$0$

$\rceil$$\rceil$$\rceil$$\rceil$

$0$

$0$

$0$

$0$

$0$

$0$

$\rceil$$\rceil$

$0$

$0$

$0$

$\rceil$

$0$

$0$

$0$

$\rceil$$\rceil$$0$$\rceil$$\rceil$$\rceil$$0$$\rceil$$0$$\rceil$$\rceil$$\rceil$$\rceil$

$0$

$0$

$0$

$0$

$0$

$\rceil$$0$$\rceil$$\rceil$$0$$\mathit{0}$

$0$

$0$

$\rceil$$0$$\rceil$

$0$

$0$

$0$

$\rceil$$\rceil$$\rceil$$\rceil$

$0$

$0$

$0$

$\rceil$$\rceil$$\rceil$$\rceil$$\rceil$$\rceil$$\rceil$1$\mathit{0}$

$0$

$0$

$0$

$\rceil$$0$$0$$\rceil$$\rceil$$\mathit{0}$

$0$

$0$

$0$

$\rceil$$0$$0$$\rceil$$0$$0$$\rceil$$\rceil$$\rceil$$\rceil$$\rceil$$0$$0$$\rceil$$\rceil$$\rceil$$\mathrm{C}:\mathrm{A}arrow \mathrm{A}:\mathrm{C}$$91\mathrm{R}$$\rceil$$0$$\rceil$$\mathrm{K}\triangleright-l\triangleright 91\mathrm{R}$ルール$\rceil$$\mathit{0}$$\mathrm{C}:\mathrm{A}arrow$$0$$\rceil$$\rceil$$0$$:\mathrm{C}$$0$$\rceil$$\rceil$$0$$l\triangleright-j\triangleright 91\mathrm{R}$$\mathrm{C}:\mathrm{A}arrow$$\rceil$$\rceil$$0$$\rceil$

$0$

$0$

$0$

$0$

$0$

$\rceil$

$0$

$0$

$0$

$\mathit{0}$

$0$

$0$

$0$

$0$

$0$

$\rceil$$\mathit{0}$$\rceil$$\rceil$$\rceil$$\rceil$$0$$0$$\rceil$$\rceil$$\rceil$$\rceil$$\mathit{0}$$\rceil$$0$$\rceil$

$0$

$0$

$0$

$0$

$\rceil$$\rceil$$\mathit{0}$$\mathit{0}$$\mathit{0}$$0$$\rceil$$0$$\mathit{0}$$\mathit{0}$$0$$\rceil$

1

$0$

$0$

$\rceil$$\mathit{0}$$\rceil$$\mathit{0}$$\rceil$$\mathit{0}$$0$$\rceil$

$0$

$0$

$0$

$0$

$0$

$0$

$\rceil$$\rceil$$0$$\mathit{0}$

$0$

$0$

$\rceil$

$0$

$0$

$0$

$0$

$\rceil$$\rceil$$0$$0$$\rceil$$\rceil$$\rceil$$j\triangleright-[]\triangleright 123\mathrm{R}$.

$\mathrm{C}’$$\mathrm{A}arrow \mathrm{S}:\mathrm{D}$ではどちらの場合も衝突によるモードの変化がないのに対して、ルール 1$\mathit{2}3\mathrm{R}$ではモードが変化する場合としない場合とがある。考えられるすべての 2 体衝突に対して、衝突の前後のモードを表 2 に示す。上で見られた性質は、実はすべての 2 体衝突に対して当てはまることがわかる。
ルール
ル$91\mathrm{R}$$91\mathrm{R}$が示すこの性質は、ソリトンが衝突において示す性質と似ている。では、ルーはソリトンオートマトンなのであろうか? 実は、 3 体以上の多体衝突の挙動を調べると、 そうではないということがわかる。例えば、 モード

うになる。

$\mathrm{D}_{\text{、}}\mathrm{C}_{\text{、}}\mathrm{B}$の 3 体衝突は次のよ

116

表 2: ルール

. .

.
. .

111

$91\mathrm{R}$

$0$

$0$

$\rceil$$\rceil$$\mathit{0}$

$0$

$0$

$\rceil$

1

1

$0$

$\mathit{0}$

$0$

$0$

$0$

$0$

$\rceil$

$0$

$0$

$0$

$0$

$0$

$0$

$0$

$\rceil$$\rceil$$\rceil$

1
1
11111

. 1111

. .
.

. .
.

.

.

とルー)I23R の 2 体衝突

.
. .
.

1

$0$

$0$

$0$

$0$

$0$

$0$

$0$

$0$

$0$

1

1

$0$

1

1

1

$0$

$0$

$0$

$0$

$\rceil$$\mathit{0}$

$0$

$0$

$0$

$0$

$0$

$0$

$0$

$0$

$0$

$0$

$0$

$0$

$0$

$0$

$0$

$\rceil$$\rceil$$0$$\rceil$

1

1

1

$0$

$0$

$0$

$0$

$0$

$\rceil$$\rceil$$0$$\rceil$$0$$0$$\mathit{0}$

$0$

$0$

$0$

$\mathit{0}$

$0$

$0$

$0$

$\mathit{0}\cdot 0$

$0$

$0$

$0$

$0$

$0$

$\rceil$$\rceil$

1

1

1

1

$0$

$0$

$0$

$0$

$0$

$0$

$\rceil$

$0$

$0$

$0$

$\mathit{0}$

1
1

$0$

$0$

$\rceil$

1111

1
1

1

1

$0$

$0$

$0$

$0$

$0$

$0$

$\rceil$

$0$

$0$

$0$

$\rceil$

$0$

$0$

$0$

$0$

$\rceil$

1

1

1

1

$0$

$0$

$0$

$\mathit{0}$

$0$

$0$

$0$

$0$

$\mathit{0}$

$0$

$0$

$0$

$\rceil$1

11$\rceil$$\rceil$$\rceil$$\rceil$

$0$

$0$

$0$

$0$

$\rceil$$0$$0$$\rceil$$\rceil$:$\mathrm{C}$1$\rceil$:$\mathrm{R}$$\Phi=\mathit{2}$

.
.

.
.
.

.

.

1 1 1 . .

$0$$\rceil$

. .

.

. .
.

の 3 体衝突$\mathrm{B}arrow \mathrm{A}$

ここで、 $W$ と書いたモードは、保存量の値$91\mathrm{R}$1$0$$\mathrm{D}$

ルール

$0$

$0$

ル一]9\rceil

度 1/6 のパターンであり、$0$$\mathit{0}$. . 111.

1
1$\rceil$. 11111.

$\rceil$$\rceil$$4_{\text{、}}$: $W$
時間が 6 進むと右へ 1 だけシフトする速のモードとは異なる新しいモードである。 このように、では、 2 体衝突の和に還元されない多体衝突が存在する。 -方おもしろいことに、 ルール 1$\mathit{2}3\mathrm{R}$では、多体衝突は 2 体衝突の和に還元できる。 このように、保存量を持つ系には、 ソリトンとは違う動力学的性質を示すものが存在している。
以上 ECA と ERCA の加法的保存量について見てきたが、 この 2 つの例に限らず、 X が有限であれば、保存量条件 (8) を用いて保存量を求めることが可能であることがおわかりいただけると思う。 また、保存量に着目することにより、系の興味深い性質が見えてくる117ということも、納得していただけたのではないだろうか。

4

保存量条件の拡張
この節では、 2 節で求めた保存量条件を、いくつか違った方向に拡張することを考える。

4.1

近傍数

2 節では 3 近傍の$\mathrm{C}\mathrm{A}$ことは直ちにできる。

に対して条件を求めたが、 これを任意の近傍数の CA に拡張する$\mathrm{C}\mathrm{A}$の時間発展則が$\mathrm{x}_{i}^{\mathrm{t}+1}=$で与えられるとしよう。近傍数は

佳

(42)

$(\mathrm{x}_{i-\mathrm{b}}^{\mathrm{t}}, \mathrm{x}^{\mathrm{t}}i-\mathrm{b}+1)\ldots)\mathrm{x}_{i+\mathrm{c}}^{\mathrm{t}})$である。 さて$\mathrm{b}+\mathrm{C}+\rceil$(43)$\Phi(\{\mathrm{x}_{i}^{\mathrm{t}}\})=\sum_{i}\mathrm{F}(\mathrm{X}^{\mathrm{t}\mathrm{t}}i’ i\mathrm{x}+1’\cdots,i+\mathrm{x}^{\mathrm{t}})\alpha$が加法的保存量であることは、$\mathrm{G}(\mathrm{X}_{\mathit{0}1}, \chi, \ldots, \chi_{\mathrm{b}\alpha}+\mathrm{C}+)=\mathrm{F}(\mathrm{g}(\mathrm{X}0, \ldots, \mathrm{X}\mathfrak{a}+\mathrm{b}), \ldots, \mathrm{g}(\mathrm{X}\alpha)\ldots, \chi \mathrm{b}+\mathrm{c}+\alpha))$

(44)

として、
$\mathrm{N}-\rceil$$\sum_{i=0}[\mathrm{G}(\mathrm{x}i, \mathrm{x}i+\mathrm{t}, \ldots, \chi i+\mathrm{b}+\mathrm{c}+\alpha)-\mathrm{F}(\mathrm{X}i+\mathrm{b}, \ldots , \chi_{i\mathrm{b}}++\alpha)]=0$(45)が成り立つことと等価であるから、補題 1 がそのまま使える。 したがって、 この場合の保存量条件は$\mathrm{G}(\mathrm{x}_{0}, \mathrm{x}_{\rceil}, \ldots, \mathrm{X}_{\mathrm{b}}+\mathrm{C}+\alpha)-\mathrm{F}(\mathrm{X}\mathrm{b}_{)}\cdots , \chi_{\mathrm{b}+\alpha})=\mathrm{I}(_{\mathrm{X}_{0,\ldots \mathrm{b}+\rceil}})+\mathrm{C}\alpha-)\mathrm{x}-\mathfrak{s}(\mathrm{x}_{1,)}\ldots \mathrm{X}\mathrm{b}+\mathrm{C}+\alpha)$で与えられる。 ここでI$( \mathrm{x}_{0}, .

.

.

ただし、

$\mathrm{I}(\mathrm{x}\mathit{0}, \ldots)\mathrm{X}_{\mathrm{b}}+\mathrm{C}+\infty-\rceil)$は次式で定義される。

, \mathrm{X}_{\mathrm{b}+\mathrm{C}+-1}\alpha)=-\sum_{-^{-}1}^{+\mathrm{c}}\mathrm{G}(\mathrm{P}, \ldots, \mathrm{p}_{\chi_{\rceil_{)}}}\mathrm{b}.+\alpha,.

$\mathrm{F}(\mathrm{P}, \ldots, \mathrm{P})$

(46)

.

.

, \mathrm{x}_{i})+\sum_{=\mathrm{C}}^{\mathrm{C}}\mathrm{b}+i+\iota+\alpha \mathrm{F}(\mathrm{P}, .

.

., \mathrm{P}, \mathrm{x}_{1}, \ldots, \mathrm{x}i-\mathrm{c})$(47)による定数項は適当に調整した。

この拡張を用いて得られた結果を 1 つ述べておこう。保存量条件はルールを与えれば密度関数$\mathrm{F}$に対する条件になるが、逆に保存量の関数形を指定してルールに対する条件を与えるものともみなすことができる。 そこで、 $\mathrm{X}=\{0,1\}$ は固定して近傍数を変化させたときに、 1 の数を保存する (すなわちに変化するかを調べてみると、$\mathrm{F}(\mathrm{x})=\mathrm{x}$が保存量密度となる) ルールの数がどのよう

118

近傍数
3 近傍 (ECA)
4 近傍
5 近傍

1 の数を保存するルール数

同値類の数

全ルール数

256
3
7
65536
129 4294967296

5
22
428

であることがわかった。

Staggered Invariants

4.2

加法的保存量はセルに関する和の形に書ける量であったが、位相因子を含む次の形の量に拡張することができる。

(48)$i+\infty \mathrm{t}$$\Psi(\{\mathrm{x}_{i}\mathrm{t}\})=\mathrm{e}^{2\pi i\iota/\tau}\mathrm{N}\sum_{1=0}\mathrm{e}^{2\pi i\mathrm{t}}(\mathrm{X}\chi\ldots\chi \mathrm{I}-1/\lambda \mathrm{p}\mathrm{t}i’ i+\mathrm{t}\rceil$”

ただし$\mathrm{N}/\lambda\in \mathbb{N}$とする。 $\lambda=\tau=\rceil$ の場合が加法的保存量であり、$\lambda$

または$\tau$

が 2 以上の整数の場合がその–般化であり、 staggered invariants と呼ぶ。 このような保存量は、流体系のシミュレーションに用いられる格子気体オートマトンのある種のモデルにも存在することが知られている [7]。

詳細は省略して結果のみ書くと、$\mathrm{e}^{\frac{2\pi i}{\mathrm{T}}}\mathrm{G}(\mathrm{x}0)\ldots,$$\mathrm{x}\infty+2)-\mathrm{F}(\mathrm{x}\uparrow, , .

.

$\Psi$

が保存量となるための条件は次のように書ける。

, \mathrm{X}\alpha+1)=\mathrm{I}(\chi_{\mathit{0},.,1}..\mathrm{X}_{\infty+})-\mathrm{e}^{\frac{2\pi i}{\lambda}}\mathrm{I}(\mathrm{X}\iota, \ldots)\mathrm{x}\alpha+2)$

(49)

ただし、

I

$(_{\mathrm{X}_{\mathit{0},\ldots 1}}))\chi_{\alpha+}$$= \mathrm{c}_{\tau,\lambda}+\sum_{=1\mathit{0}}^{\alpha+1}\mathrm{e}-\frac{2\pi i(\iota+1)}{\lambda}[\mathrm{F}(\mathrm{P}, .

ここで、

,

$\mathrm{c}_{\mathrm{r},\lambda}$.

., \mathrm{P}, \mathrm{x}_{0\cdot\cdot\iota},.\mathrm{X}_{\alpha-}))-\mathrm{e}^{\frac{2\pi i}{\tau}}\mathrm{G}(\mathrm{P}, \ldots, \mathrm{p}, \chi \mathit{0}, \ldots, \mathrm{X}\alpha+\iota-\iota)](50)$は次式で定義される定数である。
$0$

for

$\frac{\mathrm{e}^{-\frac{2\pi i\{\alpha+2)}{\lambda}}}{1-\mathrm{e}^{\frac{2\pi i}{\lambda}}}[\mathrm{e}^{\frac{2\pi i}{\mathrm{T}}}\mathrm{G}(\mathrm{P}, \ldots, \mathrm{P})-\mathrm{p}(\mathrm{P}, \ldots, \mathrm{p})]$otherwise$\lambda=1$$\mathrm{c}_{\tau,\lambda}=\{$(51)

よってこの場合も連続の式が得られる。
この条件を用いて ECA や ERCA の staggered invariants を求めるのは 3 節の場合とほとんど同様にできる。ただ 1 つ注意すべきことは、$\lambda=1$

かつ $\tau\neq 1$ の場合は、式 (29) や(34) の展開に定数項を含めておく必要があるという点である。導出の詳細と結果について
は文献 [6] を参照のこと。

119

4.3

2 次元系

次のように補題 1 を 2 次元の場合に拡張することができる。 関数
考えようを水平方向のインデックス、$\mathrm{o}i$の変数の値をで表す。 周期境界条件$\mathrm{x}_{i,\mathrm{i}}$$\mathfrak{j}$$\mathrm{H}:\mathrm{X}^{(\mathrm{a}+}1$)($\mathrm{b}+1\mathrm{I}arrow \mathbb{R}$を垂直方向のインデックスとして、 セル$\mathrm{x}_{i+\mathrm{N},\mathrm{i}}=\mathrm{x}_{i,\mathrm{i}+\mathrm{M}}=\mathrm{x}_{i,\mathrm{i}}$を$(i, \mathfrak{j})$のもとでN-I M-l$\sum\sum \mathrm{H}(\mathrm{X}_{i,\mathrm{i})}\chi i,;+1,$$\ldots,$$i=0$$\mathrm{X}_{i,\mathrm{i}+\mathrm{b};}\mathrm{X}i+1)\mathrm{i},$$\ldots)\chi_{i+1,\mathrm{b}}\dot{1}+).\ldots$;$\mathrm{x}_{i+\mathfrak{a}_{\dot{\mathrm{I}}})},\cdots,$$\mathrm{X}_{i+\mathrm{a},\mathrm{i}\mathrm{b}}+)=0$(52)$\dot{\mathrm{I}}^{=0}$が恒等的に成り立つための条件は次のように与えられる。
補題 2 関数$\mathrm{H}$に対する条件 (52) は$\mathrm{H}$が次のように書けることと等価である。

(53)$\mathrm{H}(\mathrm{x}_{i},\mathrm{i}, \ldots, \chi_{i}+\mathrm{a},\mathfrak{j}+\mathrm{b})=\Delta_{\mathrm{b}}\mathrm{I}_{\mathrm{b}}+\Delta_{\mathrm{v}}\mathrm{I}\mathrm{V}$

ただし$\Delta_{\mathrm{b}}$と$\Delta_{\mathrm{v}}$は、それぞれ水平方向、垂直方向の差分演算を表す。 また$\mathrm{I}_{\mathrm{b}^{\text{、}}}\mathrm{I}_{\mathrm{V}}$l よ次式

で定義される関数である。
$\mathrm{I}\mathrm{b}(_{\mathrm{X}}\mathit{0},\mathit{0}, \ldots, \mathrm{x}0,\mathrm{b}).1\chi,\mathit{0})\ldots,$$=$;$\chi_{\mathrm{a}-}1,0$)$\ldots,1\mathrm{X}_{\mathfrak{a}-},\mathrm{b}$

)

(54)

$\sum_{i=0}^{\mathrm{a}-}\mathrm{H}(^{\mathrm{p}..\mathrm{p}},.,;\mathrm{x}\mathit{0},\mathit{0}_{)}\cdots, \mathrm{X}_{\mathit{0},\mathrm{b}};\ldots ; \mathrm{x}i,0, \ldots)\mathrm{x}i,\mathrm{b})\rceil$$\mathrm{I}_{\mathrm{V}}(_{\mathrm{X}0,0}, \ldots, \chi_{\mathit{0}},\mathrm{b}-\rceil;\mathrm{x}\rceil,-\mathrm{b}, .

$=$$\mathrm{X}\rceil,\mathrm{b};\cdots$.

, , \mathrm{X}\rceil,\mathrm{b}-\rceil;\cdots).a,-\mathrm{X}\mathrm{b},$,$\ldots)\mathrm{b}-1)\mathrm{x}_{\mathrm{a}}$$\sum_{i=0\mathfrak{j}}^{\mathrm{a}}\sum \mathrm{H}(\mathrm{P}, \ldots , \mathrm{p};\mathrm{x}0,0, \ldots, \mathrm{x}_{0,\mathfrak{j}}; \ldots ; \chi i,\mathrm{j}-\mathrm{b})\mathrm{b}-=0\rceil\ldots,$$\mathrm{x}i,\mathrm{i})$$- \sum_{\mathit{0}i=}^{\mathrm{a}-1}\sum^{\mathrm{b}}\mathrm{H}(\mathrm{p}, \ldots, \mathrm{p}, \mathrm{x}_{1_{)}},-\mathrm{b}, \ldots, \mathrm{X}_{\rceil},;;\ldots;\mathrm{x}i+\rceil,)-\mathrm{b},)\mathrm{j}=0-\rceil.\ldots)\mathrm{x}i+1,\mathrm{j}$証明は 1 次元の場合と同様にできる。式 (53)$\Rightarrow(52)$は自明なので、式 (52)$\Rightarrow(53)$

(55)
を示せ

ばよい。 まず、式 (52) より、$\mathrm{H}(\mathrm{P}, \cdots, \mathrm{P})=0$(56)が成り立つことに注意しておく。次に、$\mathit{0}$$=$$\sum_{i=0}^{\mathrm{N}-}\sum \mathrm{H}(\chi_{i},\mathrm{i}, \ldots, \mathrm{x}_{i}+(1,)+\mathrm{b})-\mathrm{H}(\mathrm{x}i,\mathfrak{j}, \ldots, \mathrm{X}i+\mathrm{a},\mathrm{i}+\mathrm{b})\iota \mathrm{M}-\mathrm{i}=0\rceil|\mathrm{x}\mathit{0},0^{=}\mathrm{P}$$= \sum_{i=-\mathrm{a}=}^{0}.\sum_{)-\mathrm{b}}\mathrm{H}(\mathrm{x}_{i,\mathrm{i},\ldots i+)+}, \chi\cdot \mathrm{b})\mathrm{a},-\mathrm{H}(\mathrm{X}_{i}\mathfrak{j},., \mathrm{x}_{i}+\mathrm{a},\mathrm{i}+\mathrm{b})|0,\cdot\cdot\chi_{0,0=}\mathrm{p}$

(57)

120

が得られるから、 ここで

$0$

$=$

(

$‘ i<\mathit{0}$

”

または

“

$i=0$ かつ$\mathfrak{j}<0$”$\sum_{i=-\mathrm{a}\mathfrak{j}=}^{0}\sum_{-\mathrm{b}}^{\mathit{0}}\{\mathrm{H}(\mathrm{p}, \ldots, \mathrm{P}, \mathrm{x}_{0},0, \mathrm{x}\mathit{0},\rceil\cdots)\mathrm{X}0,\mathrm{j}+\mathrm{b}).\ldots$$-\mathrm{H}(^{\mathrm{p}\ldots \mathrm{P},,\mathrm{X},\chi},)0,1,$$\ldots 0,\mathrm{i}+\mathrm{b};\cdots$

ただし最後の項は$\mathfrak{j}=-\mathrm{b}$

のときには

;

ならば

;

$\chi i+\mathfrak{a},\mathrm{j}$$\mathrm{x}i+\mathrm{a},\mathrm{j},$)$\mathrm{X}_{i},;=\mathrm{P}$$\ldots,$$\ldots,$とおくと、$\chi i+\mathrm{a},\mathfrak{j}+\mathrm{b}$$\mathrm{x}i+\mathrm{a},\mathrm{i}+\mathrm{b}$

)

)}

(58)

を
$\mathrm{X}_{i}+\mathrm{a},\mathit{0})))$,$\mathrm{H}(\mathrm{p}, \ldots \mathrm{p}\cdot\chi_{1},-\mathrm{b})\ldots,$$\mathrm{X}_{\rceil}\mathit{0})\ldots)\chi_{i}+\mathrm{a},-\mathrm{b})\ldots,$表すものとする。 ここでインデックスを適当に付け替えて、式 (56) を用いると、$\mathrm{H}(_{\mathrm{X}_{0,\mathit{0}}}, \ldots, \mathrm{x}_{\mathrm{a}},\mathrm{b})$$=$$\mathrm{a}\mathrm{b}-;=0\rceil$$\sum_{i=\mathit{0}}\sum\{\mathrm{H}(\mathrm{p}, \ldots, \mathrm{P}, \mathrm{x}_{0},1)\cdot,$$.,$ $\chi_{0},\mathrm{i}+\rceil;\cdots$;$\mathrm{X}i,\mathrm{j}-\mathrm{b}+\rceil,$$-\mathrm{H}(\mathrm{p}, \ldots, \mathrm{p}_{\mathrm{X}},\mathit{0},0, \ldots)0\mathrm{x},\mathrm{j};\cdots$$\mathrm{a}-\rceil$;$\mathrm{X}i,\mathrm{j}-\mathrm{b}$)$\ldots,$$\ldots$,$\mathrm{X}i,;+1$$\mathrm{x}$ $i,\mathrm{i}^{)}$

)

}

b-l

$- \sum_{i=0\mathrm{j}}\sum_{=0}\{\mathrm{H}(\mathrm{p}, \ldots)\mathrm{p};\mathrm{x}_{1,\mathrm{b}}\mathfrak{j}-+\rceil)\ldots$,$.\mathrm{X}i+1,\mathrm{j}-\mathrm{b}+1,$$1$$\chi,\mathrm{j}+\rceil;\cdots)$$\mathrm{x}i+1,\mathrm{i}+1)$$\ldots,$$-\mathrm{H}(^{\mathrm{p}}, \ldots)\mathrm{P};\mathrm{x}\iota,\mathrm{i}-\mathrm{b})\ldots);\mathrm{x}_{\rceil,\cdot\cdot;})..\mathrm{X}i+\rceil,\mathrm{j}-\mathrm{b})\ldots)\mathrm{x}_{i+}\iota,\mathrm{j})\}$$\mathrm{X}i+1,\mathrm{b})\rceil$$+ \sum_{i=0}^{\mathfrak{a}-}\{\mathrm{H}(\mathrm{P}, \ldots \mathrm{P}\cdot \mathrm{X}_{1},0)\ldots,1\mathrm{X}\mathrm{b};)),\cdots).\chi_{i\rceil}+,0,$$\ldots,$$-\mathrm{H}(^{\mathrm{p}\ldots \mathrm{P}\ldots,\cdot,)},);\mathrm{x}_{0},\mathit{0},)\chi_{\mathit{0}}\mathrm{b};\cdots)i,0,)\mathrm{b}\}\mathrm{x}\ldots \mathrm{X}_{i}$

$=$

(59)
(60)

$\Delta_{\mathrm{b}}\mathrm{I}\mathrm{b}+\Delta \mathrm{V}\mathrm{I}\mathrm{v}$を得る。ただし、式 (57) の右辺の 2 個の 2 重和の部分が$\Delta_{\mathrm{v}}\mathrm{I}\mathrm{V}$であり、 1 重の和の項が$\Delta_{\mathrm{b}}|_{\mathrm{b}}$を表す。 これで補題 2 は証明された。

補題 2 を用いて保存量条件を書き下すことは読者に任せる。この条件を用いて、 von Neumann 近傍 (図 3 参回) を持つ 2 状態$(\mathrm{X}=\{0,1\})$の$\mathrm{C}\mathrm{A}$うなものがあるか調べてみたところ、 すべて 1 次元ので、 1 の数を保存する, ものはどのよ$\mathrm{C}\mathrm{A}$に還元できるものばかりである

ことがわかった。

図 3: von Neumann 近傍 (左) と Moore 近傍 (右)121

保存量を持つ 2 次元でよく知られているものに、 Ising 系のシミュレ一ションを決定$\mathrm{C}\mathrm{A}$論的に行うために考案された Creutz モデル [8] と$\mathrm{Q}\mathit{2}\mathrm{R}[9]$と呼ばれるモデルがある。 これらのモデルでは正方格子を 2 つの副格子に分け、副格子ごとに状態更新を行うので、 ここで考えている$\mathrm{C}\mathrm{A}$とは若干異なる。 しかし、 この場合も連続の式が導かれる。 (詳細の説明は省略する。 )3 次元以上の5$\mathrm{C}\mathrm{A}$においても、 同様の補題が–般的に成り立つものと予想される。

保存量を持つ$\mathrm{C}\mathrm{A}$と計算

最後に少し毛色の変わった問題を考えよう。 セルオートマトンにおける計算の問題である。

セルオートマトンにおける計算に関しては、von Neumann 以来の歴史があり、万能 Tur-ing 機械や自己増殖機械の構成が有名である。 これは、論理ゲートを CA の中に作り、 それらを組み合わせることで実現される。 ここでは、 そのような von Neumann 型の計算ではなく、 CA の並列過程自身が何らかの大域的な情報処理を表現しているような場合について考える。 CA の素子は局所的に比較的単純な作業を行っているに過ぎないが、 そうい
うものに大域的な情報が扱えるだろうかという問題である。 このような計算過程は 「創発計算」 [10] という名で呼ばれることがある。

そのような計算過程の中で、次に述べる密度分類課題と呼ばれるものについて考えよう。
周期$\mathrm{N}$の周期境界条件の下での 1 次元、 2 状態

ける 1 の密度を$\mathrm{p}=\sum_{i^{\mathrm{X}_{i}^{0}}}$とする。 また$(\mathrm{X}=\{\mathit{0},1\})$$0<\mathrm{p}_{\mathrm{C}}<\rceil$の$\mathrm{C}\mathrm{A}$を考え、 初期状態におなる定数 Pc (閾値) を選び、$\mathrm{C}\mathrm{A}$に対し次の要請をおく。
$\bullet$$\bullet$$\mathrm{M}$$\mathrm{P}<\mathrm{p}_{\mathrm{c}}$$\mathrm{P}>\mathrm{p}_{\mathrm{c}}$は周期$\mathrm{N}$ならば、$\mathrm{M}$ならば、$\mathrm{M}$ステップ以内にすべてのセルの値が$0$の定常状態に収束する。

ステップ以内にすべてのセルの値が 1 の定常状態に収束する。

に依存してよい。 また、$\mathrm{p}=\mathrm{p}_{\mathrm{c}}$の場合の動作については特に指定しない。 これが密度分類課題である。
例えば、 この課題を近似的に解く CA として次のような GKL$j\mathrm{s}-$]$\triangleright[11]$と呼ばれるものが知られている。
$\mathrm{m}a\mathfrak{j}0\tau i\mathrm{t}v\{\mathrm{X}_{i}^{\mathrm{t}}-3’ \mathrm{X}^{\mathrm{t}}-, \mathrm{X}\}i1i\mathrm{t}$$\mathrm{x}_{i}^{\mathrm{t}+1}=\{$$\mathrm{m}a\mathfrak{j}0\tau i\mathrm{t}v\{\mathrm{x}_{i’ i}\mathrm{t}\chi\chi \mathrm{t}+\mathrm{t}’ i+3\mathrm{t}\}$

ここで$\mathrm{m}a\mathfrak{j}_{0}\Gamma i\mathrm{t}v\{\mathrm{a}, \mathrm{b}, \mathrm{c}\}$以上含めば$\mathrm{p}\simeq \mathrm{p}_{\mathrm{c}}$$0$は「多数決」を表し、$\{\mathrm{a}, \mathrm{b}, \mathrm{C}\}$となる関数である。 このルールは閾値

の場合には間違うことも多い。

if
if$\mathrm{x}_{i}^{\mathrm{t}}=0$(61)$\mathrm{x}_{i}^{\mathrm{t}}=\rceil$が 1 を 2 個以上含めば$\mathrm{p}_{\mathrm{c}}=1/2$$1_{\text{、}}0$を2個でかなりよく分類を行うが、122$\mathrm{M}\mathrm{i}\mathrm{t}\mathrm{c}\mathrm{h}\mathrm{e}\mathrm{l}\mathrm{l}[12]$らは、遺伝的アルゴリズムを用いてこの課題を解く

深い振る舞いをするルールを発見したが、完全にこの課題を解く
実は 「密度分類課題を完全に解く 1 次元$\mathrm{C}\mathrm{A}$$\mathrm{C}\mathrm{A}$$\mathrm{C}\mathrm{A}$の探索を行い、興味は見つからなかった。

は存在しない」 ことが証明されているのである [13]。

ところが最近、 すべてのセルがとにより$[14]_{\text{、}}$

もしくは 2 種類のても密度分類を行う$\mathrm{C}\mathrm{A}$$\mathit{0}$またはすべてのセルが 1 という出力条件を緩和するこ$\mathrm{C}\mathrm{A}$を用いることによって [15] 、いかなる初期条件に対しが得られることが報告された。 どちらも本質的には同じであり、ECA のルール 184 を用いる。 このルールは、 (i) 1 の個数を保存するルールであり、 しか以と 1 を可能な限り交互に並べようとする。 したがって、ある時刻
も (ii)であることを示し、 11 というブロッ
降に 00 というブロックが検出されたならば$(\mathrm{M}=[\mathrm{N}/2|)$$0$$\mathrm{p}<\rceil/2$

クが検出されたならば
あるいは、時刻$\mathrm{M}$$\mathrm{p}>$]$/\mathit{2}$を示す。 こうして閾値$\mathrm{p}_{\mathrm{c}}=1/2$の密度分類が達成される。

においてルール 232 という多数決のルールに切り替えることにより、元の出力条件を満たすようにすることも可能である。
ルール 184 の性質 (i) は加法的保存則であり、 この「計算」過程において本質的な役割を果たしている。では、 このような計算過程は$\mathrm{C}\mathrm{A}$においてどれくらい–般的に見られるものであろうか。 あるいは、 このような計算を行うための条件とは何だろうか。

この問題を考えるために、 まずルール 184 と同様の性質を示す
質 (i) に着目して 1 の個数を保存する$\mathrm{C}\mathrm{A}$$\mathrm{C}\mathrm{A}$を探してみよう。性を選び出し、それらが密度分類を行うかどうかを調べる。 ECA の範囲では、 1 の個数を保存するルールは 184 以外は恒等変換とシフトだけであり、 これらが分類を行わないことは明らかである。そこで、 4 近傍のルール(62)$\mathrm{x}_{i}^{\mathrm{t}+1}=\mathrm{g}(_{\mathrm{X}^{\mathrm{t}\iota \mathrm{t}}}i-1’ i)i+\iota’ i+2)\mathrm{X}\chi\chi^{\mathrm{t}}$について考える。 4.1 節の表にあるように、 4 近傍のルールで 1 の数を保存するものは (対称性の変換で移り変わるものを同–視すると) 7 個しかない。そのうちの 3 個は ECA に現れるものと同じなので、新しいルールは 4 個だけになる。 Wolfram のやり方を拡張して各ルールに$\sum 2^{8\mathrm{x}+}4\mathrm{v}+2\mathrm{Z}+\mathrm{w}9(\mathrm{x},\mathrm{v},$(63)$\mathrm{z},\mathcal{W}\mathrm{I}$$\mathrm{x},\mathrm{v},\mathrm{z},\mathrm{w}$という番号を付けると、各同値類を代表する最も番号の若いルールは$43944\text{、}48\mathit{2}68\text{、}48\mathit{7}70\text{、}$$51448$ である。

これらのルールが$\mathrm{P}$に関して分類を行うかどうかを調べた結果は、次のようになった。

で分類43944 閾値ルール 48268 2 個の閾値 Pcl
Pc2
ルール 48770 2 個の閾値 Pcl
ルール 51448 分類しないルール$\mathrm{p}_{\mathrm{c}}=1/3$$=1/2_{\text{、}}$$=\mathit{2}/3$$=1/3_{\text{、}}\mathrm{p}_{\mathrm{c}2}=2/3$

で分類
で分類

123

この結果は、ブロックパターンに対する preimages を調べることにより証明できる。例えばルール 43944 では、次の 3 つの命題が成立する。

1.

$\mathrm{t}>0$において$(\mathrm{X}^{\mathrm{t}}\mathrm{X}^{\mathrm{t}}\mathrm{X}^{\mathrm{t}})i)i+1)i+2=(0,0, \mathrm{o})$ならば、$(\mathrm{x}_{i-1’ i’ i+1}^{\mathrm{t}}-1\mathrm{X}^{\mathrm{t}1}-\chi^{\mathrm{t}1}-)=(0,0, \mathrm{o})$でなければならない。

2.

$\mathrm{t}>0$3.

$\mathrm{t}>\mathit{0}$で$(\chi^{\mathrm{t}}\chi i’ i+1)=(1,1)$

で

ならば、

$(\mathrm{x}_{i}^{\mathrm{t}-1}+2’ i\mathrm{X}^{\mathrm{t}1}-)+3=(1,1)$$(\mathrm{x}_{i}^{\mathrm{t}}, \mathrm{X}_{i+1)i+2}\mathrm{t}\mathrm{x}\mathrm{t})=(1,0,1)$$(\mathrm{x}_{i-}, \mathrm{x}-1\mathrm{x}\mathrm{t}-\iota \mathrm{t}1i’ i+1\mathrm{t}-\rceil)=(\mathit{0},1,1)$

ならば、

である。

$(\mathrm{x}_{i^{-}}-1’ \mathrm{x}-1\chi_{i+1}\mathrm{t}\iota \mathrm{t}i’ \mathrm{t}-\rceil)=(1,0,1)$

またはのいずれかが成り立つ。

これらは、ルール表を見ながら可能なパターンを –つ–つ調べることによって証明される。
そしてこれらの命題から、 もし$(\mathrm{x}_{i}^{\mathrm{t}}, \mathrm{x}_{i}^{\mathrm{t}\mathrm{t}}\mathrm{X})+\rceil)i+2=(0,0, \mathrm{o})$値からずっと速度 1 で右ヘシフトを続けてきたのであり、であれば、 このパターンは初期$(\mathrm{X}_{i}^{\mathrm{t}}, \mathrm{x}^{\mathrm{t}\mathrm{t}}i+\iota’ \mathrm{x}_{i+2})$が 2 個以上の 1 を含むならば、そのようなブロックは初期値からずっと速さ 2 で左ヘシフトを続けてきたのだということがわかる。 したがって、 もし$\mathrm{t}>[\mathrm{N}/3]$

でこの 2 種類のブロックが共存していたとするならば、 過去においてそれらが 2 個以上の連続したセルにおいて交わりを持っていたことになり矛盾する。 したがって、$\mathrm{t}>[\mathrm{N}/3]$

では$(0,0, \mathrm{o})$と 2 個以上の 1 を含む連

続した 3 個のセルからなるブロックとは共存できないことになる。 こうして閾値の密度分類が実現される。 (図$4(\mathrm{a}),(\mathrm{b})$$\mathrm{p}_{\mathrm{c}}=1/3$)

閾値が 2 個あるルールに対しても同様の解析ができる。 ただし、 この場合は初期条件において存在したパターン同士の競合ではなく、 いったん別のパターンを作り出す点が違っている。 (図 4(C)-(f))の場合、これらのルールでは、どんな初期条件からの時間発展も、シフトによる違いを除いて同–のパターンに収束する。このことは、 1 の個数以外の保存量が存在しないこ$\mathrm{p}=\mathrm{p}_{\mathrm{c}}$とを強力に示唆している。-方、密度分類を行わないルール 51448 には、$\sum_{i}(\rceil-\mathrm{x}_{i})\mathrm{x}i+\rceil\chi i+2$という別の保存量が存在しており、 このことが密度分類の実行を阻害していると考えられる。保存量条件を用いる方法では、$\alpha$というパラメータを与えて議論しなければならず、それより大きなパラメータ値を持つ保存量に関しては何も言うことができなかったが、密度分類を行うようなルールに対しては、任意の$\alpha$の加法的保存量および staggered invariantsの不在を証明できる可能性がある。

逆に加法的保存量が 1 個だけのルールであれば、それは 1 の個数に限定する必要はない。
論文 [6] の表にあるように、 $\alpha=6$ で加法的保存量および staggered invariants を 1 個しか持たない ECA は、 ルール垣、$14_{\text{、}}35_{\text{、}}43_{\text{、}}56_{\text{、}}14\mathit{2}_{\text{、}}184$の 7 個であるが、 これらはすべてそのルールに付随する保存量の密度を分類することがわかる。図 5 にルール垣の場合

124

(a)

(b)

(c)

(d)

(e)

(f)

図 4: 密度分類を行う$\mathrm{C}\mathrm{A}_{\mathrm{o}}(\mathrm{a})_{\text{、}}(\mathrm{b})$系の大きさはいずれも$1\mathit{2}4$。

$\mathrm{N}=180_{0}\rceil$

はルール$43944_{\text{、}}(\mathrm{c})-(\mathrm{f})$の数は (a)はノレ一ノレ 48268 の時間発展。

$57_{\text{、}}(\mathrm{b})63_{\text{、}}(\mathrm{c})87_{\text{、}}(\mathrm{d})93_{\text{、}}(\mathrm{e})11\mathit{6}_{\text{、}}(\mathrm{f})$125を示す。 このルールは$\Phi^{11}(\{\chi_{i}\})=\sum_{0i=}\chi_{i(}1\mathrm{N}-\rceil-\mathrm{X}_{i+1})(\rceil-\mathrm{x}_{i+2}+\mathrm{X}i+2\chi_{i+}3)$という保存量を 1 個だけ持ち、$\mathrm{p}^{11}=\Phi^{11}/\mathrm{N}$の値が$\mathrm{p}_{\mathrm{c}}^{11}=1/4$(64)より小さい場合と大きい場合で異なる終状態に達する。

(b)

(a)

図 5: ルール垣の時間発展。 $\mathrm{N}=180\circ$ 保存量の密度はそれぞれ (a)$\mathrm{p}^{\rceil\rceil}=4\mathit{2}/180_{\text{、}}(\mathrm{b})$$\mathrm{p}^{11}=46/180\circ$以上から、密度分類課題を解く$\mathrm{C}\mathrm{A}$と加法的保存量を 1 種類しか持たない不可逆な CAとの問に密接な関係があるということが分かった。 -般的な証明は無いが、調べた範囲内
では後者は常に前者になっている。必要条件なのか、 十分条件なのかといったことや、保存量の形に対して制限があるのかどうか、 閾値はどのようにして決まるか、保存量や閾値を与えてルールを設計する方法はあるか、 2 次元以上ではどうなるのか等の問題は今後の課題である。

参考文献[1] S. Wolfram, Cellular Automata and Complexity: Collected Papers (Addison-Wesley,1994).

126[2] T. Hattori and S. Takesue, Physica $D49$ (1991) 295-322.
[3] S. Takesue, Phys. Rev. Leit. 59 (1987) 2499-2502.
[4] S. Takesue, Phys. Rev. Lett. 64 (1990) 252-255.
[5] S. Takesue, Physica $D103$ (1997) 190-200.
[6] S. Takesue, Complex Systems 9(1995) 149-168.
[7] G. Zanetti, Phys. Rev. A40 (1989) 1539-1548.

[8] M. Creutz, Ann. Phys (N.
[9]$\mathrm{G}.\mathrm{Y}$$Y.$) $167$ (1986) 62.

. Vichniac, Physica $D10$ (1984) 96.

[10] Emergent Computation: Self-Organizing, Collective, and Cooperative Phenomena in

Natural and Artificial Computing Networks, edited by S. Forrest (MIT Press, Cambridge, 1991).
[11] P. Gacs, G. L. Kurdyumov, and L. A. Levin, Problemy Peredachi Informa tsii 14(1978) 92-98.

[12] M. Mitchell, J. P. Crutchfield, and P. T. Hraber, Physica $D75$ (1994) 361-391.
[13] M. Land and R. K. Belew, Phys. Rev. Lett. 74 (1995) 5148.
[14] M. S. Capcarrere, M. Sipper, and M. Tomassini, Phys. Rev. Lett. 77 (1996) 4969-

4971.
[15] H. Fuk\’{s}, Phys. Rev. E55 (1997)$\mathrm{R}2081-\mathrm{R}2084$.