数理解析研究所講究録 1263 巻 2002 年 35-50

35セルオートマトンが定めるダイナミクスと時空間パターンについて名古屋工業大学 大鋳 史男 ( Fumio Ohi)
Nagoya Institute of Technology
Email : ohi@system.nitech.ac.jp

1. 序との組 $(S, g)$ を基本セノレオートマトン (Elementary Cellular
こ [よ次のよ
Automata, ECA) と呼ぶ. $2^{8}=256$ 通りの ECA $(S, g)$ が存在し, それぞれの ECA $(S, g)\}$$S=\{0,1\}$ とうにして定まる)から $S$ への写像

$S^{3}$$\triangleright-$)$\triangleright$

番号$\mathrm{R}\mathrm{N}(S, g)$$g$が与えられている.

$\mathrm{R}\mathrm{N}(S, g)=\sum_{a,b,c}g(a, b, c)2^{a2^{2}+b2+c}$

ECA $(S,g)$ が与えられたとき, 次のようにして
Vx$S^{\mathrm{Z}}$$\in S^{\mathrm{Z}},$$\forall i\in \mathrm{Z},$$\mathrm{g}$:$s^{\mathrm{Z}}arrow s^{\mathrm{Z}}$.

を定義すること力 Г任 る.

$(\mathrm{g}(\mathrm{x}))_{i}=g(x_{j-1}, x_{i}, x_{j+1})$の要素を configuration と呼ぶ.

ECA $(S, g)$ の$g$

を local rule,で書き表すことにする.

$\mathrm{g}$

は,

$g$

$S^{\mathrm{Z}}$から定まる$\mathrm{g}$:$S^{\mathrm{Z}}arrow S^{\mathrm{Z}}$,$\mathrm{g}^{t+1}(\mathrm{x})=\mathrm{g}(\mathrm{g}^{t}(\mathrm{x})),$$\mathrm{g}^{0}(\mathrm{x})=\mathrm{x}$を initial configuration としたとき, dyna 而$\{(t, \mathrm{g}^{t}(\mathrm{x})), t\geq 0\},$$\mathrm{x}\in S^{\mathrm{Z}}$$t\geq 0$,.

$\mathrm{c}\mathrm{s}$$\mathrm{g}$が定める時空間/ くターンとは,

ECA $(S, g)$ が定めるのことである. 一般的に我々が問題にするのは,

時空間パターン$\mathrm{g}$上の dynamics を定める.

$\mathrm{x}\in S^{\mathrm{Z}}$$\mathrm{x}\in S^{\mathrm{Z}}$を global rule と呼び, その bold face$S^{\mathrm{Z}}$$\{(t, \mathrm{g}^{t}(\mathrm{x})), t\geq 0\}$上の dynamics$\mathrm{g}$の解析及びの特性である.

そS.Wolfram(1983) は, 詳細な計算機シュミレーションによって基本セルオートマトンを分類した力 ,$\dot{\mathrm{a}}$れらは必ずしも厳密なものではない. これに対して G.Braga, G.Cattaneo, P.Flocchni and C.Quaranta
Vogliotti(1995) は, 明確な判定基準による分類を行い, 0-quiescent local rule (定義はこの後で提示すの三つのクラスに分類した. また, それる) を持つ基本セルオートマトンを以下のような$C_{2},$$C_{1},$$C_{3}$

ぞれのセルオー. トマトンがどのクラスに属するかの判定を行うアルゴリズム的な手法を提示して本稿で問題にするのは$C_{3}$$\forall \mathrm{x}\in \mathcal{F}$,$C_{2}$$\forall \mathrm{x}\in \mathcal{F}$,$\sup_{t\in \mathrm{N}}l(\mathrm{g}^{t}(\mathrm{x}))<\infty$,$C_{3}$$\exists \mathrm{x}\in \mathcal{F}$,$\sup_{t\in \mathrm{N}}l(\mathrm{g}^{t}(\mathrm{x}))=\infty$.

クラスに属する local rule

$g$

る.

,

$C_{1}$$\lim_{t\cdotarrow\infty}l(\mathrm{g}^{t}(\mathrm{x}))=0$$\mathrm{A}\mathrm{a}$によって定まる$\mathcal{F}$上の dynamics$\mathrm{g}$がどのような growth of time-space pattern を示すかについて議論することである.
$S$$S^{\mathrm{Z}},$

上には離散位相が定義されていて, その直積位相が$\sigma_{R}$:$S^{\mathrm{Z}}arrow S^{\mathrm{Z}}$を次のように定義する$j\mathrm{X}\in S^{\mathrm{Z}}$$(\sigma_{L}(\mathrm{x}))_{j}=x_{i+1}$,$S^{\mathrm{Z}}$上に定義されているとする. またに対して$(\sigma_{R}(\mathrm{x}))_{i}=x_{i-1}$,$\mathrm{x}\in \mathrm{Z}$.

$\sigma_{L}$:$S^{\mathrm{Z}}arrow$

36
ECA $(S,g)$ は, $g(0,0,0)=0$ であるとき 0–quiescent であると呼ばれる.
$\mathcal{F}=\{\mathrm{x}\in S^{\mathrm{Z}}|\exists i\in \mathrm{Z}, \exists j\in \mathrm{Z}, i\leq j, \mathrm{x}= (\ldots, 0, 0, x:, \ldots, x_{j}, 0,0, \ldots)\}$

と書き,
$g$

の要素を 0-finite configuration と呼ぶ. 特に $(..., 0, 0, 0, ..)\in \mathcal{F}$ であると約束する.
が O-quiescent であれば,である. よって
は,上での dynamics を定める.
$\mathcal{F}$$\mathrm{g}(\mathcal{F})\subseteq \mathcal{F}$$\mathcal{F}$$\mathrm{g}$$\mathrm{x}\in \mathcal{F}$に対して$\mathrm{x}=(\ldots, 0,0,1^{\cdot}.\ldots,1,0,0\ldots)\vee,\vee \mathrm{j}$であるとき,$l(\mathrm{x})=j-i+1$と定め,$\mathrm{x}$の length of patternと呼ぶ.

以降では, ルール番号を明記する必要がある時. ルール番号とそれから決まる global rule をそれぞれ$g_{n}$

及ひ$\mathrm{g}_{n}$$n$を持っセルオートマトンの local ruleと書く.

Notations 1 の block とは, 1 が 2 個以上並んだもので, 例えば $(1, 1)$ や (1, 1, 1) などを指し, 長
さの 1 の block とは,
個の 1 が並んだものであり,と書く. 同様に長さ
の 0 の
$n$

$n$

$n$

$1_{n}=(1,\cdots 1\tilde{n\mathrm{f}\mathrm{f}\mathrm{l}}’$block とは,

$0_{n}=(\sim^{0,\cdots,0}$$n$

すものとして使うが,同様である.
$\mathrm{a}_{\dot{*}}=(a_{1}^{*}.

である. 特に断ることなく

0 を (..., 0, 0), $(0, 0, \ldots)$ , (..., 0, 0, 0, .. ) 等を表

個いずれを意味するかは前後関係から容易に読みとることができる. 1 に関しても, \ldots, a_{m}^{i}):\in S^{m:},$$i=1,$$\ldots,$

に対して

$n$

,

$(\mathrm{a}_{1}, \cdots,\mathrm{a}_{n})$$=$$(a_{1}^{1}, \ldots,a_{m_{1}}^{1}, \ldots, a_{1}^{n}, \ldots, a_{m_{n}}^{n})$$(0, \mathrm{a}_{1})$$=$$(..., 0, 0, 0, a_{1}^{1}, \ldots, a_{m_{1}}^{1})$,$(\mathrm{a}_{1},0)$$=$$(a_{1}^{1}, \ldots, a_{m_{1}}^{1},0,0,0, \ldots)$,$(0, \mathrm{a}_{1},0)$$=$$(..., 0, 0, 0, a_{1}^{1}, \ldots, a_{m}^{1},0,0,0, \ldots)$と約束する. 0 の代わりに 1 を入れ替えた場合も同様である.
$\mathrm{C}\subseteq\bigcup_{n\geq 1}S^{n},$$D \subseteq\bigcup_{n\geq 1}S^{n}$のとき,$k\geq 0$$\mathrm{C}^{k}\oplus D$

$=$

に対して

$\{ (\mathrm{c}, 0_{k}, \mathrm{d})|\mathrm{c}\in \mathrm{C}, \mathrm{d}\in \mathcal{D}\}$,$c_{\Phi}^{k<}v$$=$と約束する. また$A \subset\bigcup_{n\geq 1}S^{n}$$l\geq k\cup^{c\oplus^{l}D}$に対して$\tilde{A}=\{(0, \mathrm{a}, 0)|\mathrm{a}\in A\}$

とする.
さらに

$\mathrm{x}=$$(\ldots, x_{-1}, x_{0}, x_{1}, \ldots)\in S^{\mathrm{Z}}$$\mathrm{x}:,j=(x_{1}., \ldots, x_{j}),$$i\leq j$に対して,$\mathrm{x}_{-\infty,\dot{\iota}}=(\ldots, x:-1, x:)$,$\mathrm{x}_{i,\infty}=(X_{1}., X_{\dot{*}+1}, \ldots)$37
以下のような一定のパターンを持ったブロツクの集合を定義しておく.
$B$$\mathcal{U}$$=$$\{1_{n}|n\geq‘ 2\}$$=$$\{(1,0_{m_{1}},1,0_{m_{2}},1, \ldots, 1,0_{m_{n-1}},1)|m_{1}\geq 2, \ldots, m_{n-1}\geq 2, n\geq 1\}$$=$$\{((0,1)_{i_{1}},0_{m_{1}}, (0,1)_{i_{2}},0_{m_{2}}, \ldots, 0_{m_{n-1}}, (0,1)_{i_{n}})|i_{1}\geq 1, m_{1}\geq 1, \ldots, m_{n-1}\geq 1, i_{n}\geq 1, n\geq 1\}$$\mathcal{V}$$\mathcal{W}$$=$$\mathcal{X}$$=$$(\mathcal{U}\oplus B)\cup^{\beta}2<$,$\mathcal{X}_{1}$$=(\mathcal{V}\oplus B)\cup B1$,$\mathcal{X}_{2}=(\mathcal{V}\oplus B)\cup^{\beta}2<$,,$n \geq 1n\geq\cup\underline{(\mathcal{X}_{1}\cup \mathcal{X}_{2})\oplus\cdots\oplus(\mathcal{X}_{1}\cup \mathcal{X}_{2})}\bigcup_{1}\underline{(\mathcal{X}_{1}\cup \mathcal{X}_{2})\oplus\cdots\oplus(\mathcal{X}_{1}\cup \mathcal{X}_{2})}\oplus \mathcal{V}0<0<0<0<0<$$n\ovalbox{\tt\small REJECT}$$n\ovalbox{\tt\small REJECT}$$\mathcal{W}B$

$=$

ここで,

$n\geq 0\cup \mathcal{W}\oplus B\oplus\cdots\oplus^{1}B11\check{n}$,$(0, 1)_{k}=(\underline{0,1,0,1,\ldots,0,1})$$k$である. 明らかに次のことが成立する.

組の $(0,1)$,$\tilde{\mathcal{V}}\cup\tilde{\mathcal{X}}=\mathcal{F}$$\tilde{\mathcal{V}}\cap\tilde{\mathcal{X}}=\phi$Definition 11 基本セルオートマトンの local rules$\mathrm{g}$

と

$g,$

$h$

が次の条件を満たすとき,

$g$

と

$h$

,

また [ま

は対称であると呼ぶ.

$\mathrm{h}$$g(a, b, c)=h(c, b, a)$ ,

次のように定義される$\mathrm{s}$:$\mathcal{F}arrow \mathcal{F}$を対称変換と呼ぶ.

$a,$ $b,$ $c\inS$$\mathrm{x}=(\ldots, 0,0, x.\cdot i, xi+1, \ldots, xj-1,\check{xj}, 0,0, \ldots)\mathrm{j}\in \mathcal{F}$に対して$\mathrm{s}(\mathrm{x})=(..

Proposition 12., 0,0,\check{x_{j}}., x_{j-1}, \ldots, x_{j+1},\check{x_{i}}, 0,0, \ldots)\in \mathcal{F}\mathrm{J}$

基本セルオートマトンの local rules $g,$$\forall t\in \mathrm{N},$$h$.

が互いに対称ならば,$\mathrm{g}^{t}=\mathrm{s}\mathrm{o}\mathrm{h}^{t}\circ \mathrm{s}$である.

証明は容易であるから省略する.

$g,$

$h$

が互いに対称であれば,$\mathrm{g}$が生成する time-space pattern ?よ,$\mathrm{h}$力\prec 生成する time-space patternの左右を入れ替えたものになる. 従って, 一方の time-space pattern の特徴を解明すれば, 他方の time-

space pattern も同時に解明されたことになる.
2.

$C_{3}$

クラスに属するルール全体を, 対称性の観点から整理したものが以 T の表である. 第 3 群と第 6 群, 第4 群と第 7 群, 第 5 群と第 8 群は互いに対称である. 今後, 主に第 1, 2, 3, 4, 5 群のノレーノレにつ (‘て考$C_{3}$

38

Proposition 23$\forall \mathrm{g}\in C_{3}\backslash \{106,202,234,120,216,248\},$$tarrow.\infty \mathrm{h}\mathrm{m}l(\mathrm{g}^{t}(\mathrm{x}))=\infty$である.

より詳細には ;$\forall \mathrm{x}\in \mathcal{F}\backslash \{0\}$,39$\mathrm{g}$が第 1,2,3,6 群のいずれかに属すれば$l(\mathrm{g}^{t}(\mathrm{x}))=l(\mathrm{x})+2t$$\mathrm{g}$,,$\forall \mathrm{x}\in \mathcal{F}\backslash \{0\}$が第 4,5,7,8 群のいずれかに属すれば$l(\mathrm{g}^{t}(\mathrm{x}))=l(\mathrm{x})+t$,$\forall \mathrm{x}\in \mathcal{F}\backslash \{0\}$

,

である.

Proof:$g$が第 1,2,3,6 群のいずれかに属すれば$g(0,0,1)=1,$ $g(1,0,0)=1$
であり, 第 4,5,7,8 群のいずれかに属すれば$g(0,0,1)=1,$ $g(1,0,0)=0,$ $g(\star, 1,0)=1$であることに注意すれば, Proposition は明らかである.

$g(\star, 1,0)=1[X\star$ [こ0, 1 の ‘ずれ力 代入さ$\dot{\mathrm{a}}$$\mathrm{A}$れても成立することを意味する.

3. ルール 202 と 216
ルール 202 との216 は互いに対称である. この第 3 節ではルーノレ 202 を考える. ノレーノレ番号 202

うになるかについて調べる.

3.1. ルール 202 の$\mathcal{F}$上での dynamics

Proposition 311$\mathrm{x}=(0,1_{n}, 0)=(..

., 0,0,0, \underline{\check{1},1,\ldots,1,1}, 0,0,0, \ldots)\in\tilde{B}i\mathrm{j}\vee$$n\geq 2$に対して$\mathrm{g}^{t}(\mathrm{x})=(0,1_{n+t)}0)=(\ldots, 0,0,0, \sim^{j}i-\vee t1, 1, \ldots, 1,10,0,0, \ldots)\vee,\in\tilde{B}$,$t\geq 0$

.

$n+t$

つまり

$\mathrm{x}\in\tilde{B}$の$\mathrm{g}$による時間発展は, 次の図のようで, 時間が進むにつれて configuration 中の 1 のブロックの左端がーづつ延びていく. 状態 1 は,$\blacksquare$で表現されている.
$\vee j$$\vee i$$\mathrm{x}=$$\mathrm{g}(\mathrm{x})=$$\mathrm{g}^{2}(\mathrm{x})=$$\mathrm{g}^{3}(\mathrm{x})=$$\mathrm{g}^{4}(\mathrm{x})=$$\cdots$

0
0
0
0
0

0
0
0
0
$\blacksquare$0$\blacksquare$$\blacksquare$$\blacksquare$$\blacksquare$$\blacksquare$$\blacksquare$$\blacksquare$$\blacksquare$$\blacksquare$$\blacksquare$$\blacksquare$$\blacksquare$$\blacksquare$$\blacksquare$$\blacksquare$$\blacksquare$$\blacksquare$$\blacksquare$$\blacksquare$

0
0
0

0
0

$\cdots$$\blacksquare$$\blacksquare$$\blacksquare$$\blacksquare$$\blacksquare$$\blacksquare$$\blacksquare$$\blacksquare$$\blacksquare$$\blacksquare$

0
0
0
0
0

0
0
0
0
0

$\cdots$40
次のことに注意すればよい.

Proof-$g(0,0,1)=1,$ $g(0,1,1)=1,$ $g(1,1,1)=1,$ $g(1,1,0)=1,$ $g(1,0,0)=0,$ $g(0,0,0)=0$ .

Proposition 312(1)(2)$\mathrm{g}(\tilde{\mathcal{V}})\subseteq\tilde{\mathcal{U}}$$\forall \mathrm{x}\in\tilde{\mathcal{U}}$,$\forall t\geq 0$,.

$\mathrm{g}^{t}(\mathrm{x})=\sigma_{L}^{t}(\mathrm{x})\in\tilde{\mathcal{U}}$であり, 従って$\forall \mathrm{x}\in\tilde{\mathcal{V}}$,,$\mathrm{g}(\mathrm{x})\in\tilde{\mathcal{U}}$$\mathrm{g}^{t}(\mathrm{x})=\sigma_{L}^{t-1}(\mathrm{g}(\mathrm{x})),$$\forall\geq 2$.

より詳細には, 次の通りである.

$\mathrm{x}=(0\check{0}\tilde{010}.\ldots 01\hat{0\cdots 0}\tilde{010\cdots 01}\hat{0\cdots 0}\cdots\hat{0\cdots 0}\tilde{010\cdots 01}0)\in\tilde{\mathcal{V}}0|1\mathrm{f}\mathrm{f}\mathrm{l}m_{1}i_{2}\mathrm{f}\mathrm{f}\mathrm{l}_{m_{2}m_{n-11_{*}}}\cdot \mathrm{f}\mathrm{f}\mathrm{l}$

に対して

.

$\mathrm{g}(\mathrm{x})=(0\check{0}0100\cdots 000\cdots 0100.\cdots 000\cdots 0\cdots 0\cdots 0100\cdots 000)\tilde{2j_{1}-1}\check{m_{1}}2|2-1\check{m_{2}}\check{m_{n-1\check{2-_{\hslash}-1}}}\in\tilde{\mathcal{U}}$Proof-(1)$\mathrm{x}\in\tilde{\mathcal{U}}$中の 0 のブロックの長さが 2 以上であることと次のことに注意すればよい.

$g(0,0,1)=1,$ $g(0,1,0)=0,$ $g(1,0,0)=0$ .

(2).

$m_{1}$$\geq 1$であることと次のことに注意すればよい.
$g(0,0,1)=1,$ $g(0,1,0)=0,$ $g(1,0,1)=0,$ $g(1,0,0)=0$ .

Example 313$\mathrm{x}=(0,0,1,0,1,0,1,0,0,1,0,1,0)$

pattern は次の図のようになる. 状態 1 は$\mathrm{x}=$$\cdots$$\mathrm{g}(\mathrm{x})=$$\mathrm{g}^{2}(\mathrm{x})=$$\mathrm{g}^{3}(\mathrm{x})=$$\mathrm{g}^{4}(\mathrm{x})=$

.

. ...
$\cdot$

0
0
0
0
0
.
.

$\cdot$0000$\blacksquare$.
.

$\cdot$000$\blacksquare$0.
.

$\cdot$00$\blacksquare$

0
0
.

.

$\cdot$0$\blacksquare$

0
0
0
.
.

$\cdot$を初期 configuration としたときの$\mathrm{t}\mathrm{i}\mathrm{m}$-spaceで表現されてぃる.

$\blacksquare$

0
0 0 0
0 0 0
0 0 0
0 0 0
. . .
. . .

$\blacksquare$$\cdot$$\blacksquare$$\cdot$$\cdot$0000$\blacksquare$.

.

$\cdot$$\blacksquare$00$\blacksquare$0.

.

$\cdot$00$\blacksquare$

0
0
.
.

$\cdot$0$\blacksquare$

0
0
0
.
.

$\blacksquare$

0
0
0
0

$\cdot$.
.

$\cdot$

0
0 0
0 0
0 0
0 0
. .
. .

$\blacksquare$$\cdot$$\cdot$

0
0
0
0
0
.
.

$\cdot$

0
0
0
0
0
.
. ...

$\cdots$$\cdot$Proposition 314$\mathrm{x}=(0,\cdot\check{1},0_{m_{1}},\cdot\check{1},0_{m_{2}}12, \cdots, \mathrm{o}_{m_{n-1}},\cdot.\mathrm{i}\vee, 0_{m_{\mathrm{n}}}, 1_{l}, 0)\in\overline{\mathcal{W}}$,$n\geq 0$に対して,$\mathrm{g}(\mathrm{x})=(0,1,0_{m_{1}},1,0_{m_{2}}i-1_{\vee}1:2_{\vee}-1, \cdots, 0_{m}., \cdot 1-1, 0_{m_{n}}, 1_{l+1},0)n_{\vee}^{-1}\in\overline{\mathcal{W}}$である.

$m_{1}\geq 2,$$m_{2}\geq 2$, ..., $m_{n}\geq 2,$ $l\geq 2$ であることに注意せよ. また $n=0$ のとき,ある.

Proof 次のことに注意すればよい.
$g(0,0,0)=0,$ $g(0,0,1)=1,$ $g(0,1,0)=0,$ $g(0,1,1)=1$ ,$g(1,0,0)=0,$ $g(1,1,0)=1,$ $g(1,1,1)=1$ .

$\mathrm{x}\in\tilde{B}$で41
Example 3.15 $\mathrm{x}=(0,1,0,0,1,0,0,0,1,1,0)$ を初期 configuration としたときの time-space Patで表現されている.
tern は次の図のようになる. 状態 1 は$\blacksquare$. . .

$\mathrm{g}(\mathrm{x})=$$\mathrm{g}^{2}(\mathrm{x})=$$\mathrm{g}^{3}(\mathrm{x})=$

.
. ...

0
.

$\tilde{\mathcal{X}}_{2}$$\blacksquare$$\blacksquare$

0

0

0
0

$\blacksquare$$\blacksquare$0$\cdot$$\cdot$

0
0

0
0
.
.

0

..

.

$\cdot$0$\blacksquare$$\blacksquare$.

.

$\cdot$$\cdot$0I00$\blacksquare$$\cdots$

Proposition 316(1)

0
0

0
0
0

$\cdots$$\mathrm{x}=$$\blacksquare$$\blacksquare$$\blacksquare$$\blacksquare$$\blacksquare$$\blacksquare$$\blacksquare$$\blacksquare$$\blacksquare$$\blacksquare$$\blacksquare$$\blacksquare$$\blacksquare$$\blacksquare$

.

.
.

.

.

.

$\cdot$$\cdot$$\cdot$

0

0
0

0
0
0

.
.

..

$\cdots$$\cdots$...

$\cdot$$\cdot$$\cdot$$\cdot$$\cdot$

0
0
0
0
..

の要素について次のことが言える.

$(0, \check{0}, 1, \ldots, 0,1,0, \ldots, 0k, \ldots, 0, \ldots, 0,0,1, ..., 0,1,0,0, ..., 0,1, ..., 1, 0)\in\tilde{\mathcal{X}}_{2}$$\mathrm{x}=$,$n\geq 0$$\check{m_{n-1}\geq 1}\tilde{j_{n}\ovalbox{\tt\small REJECT}_{\geq 1}}\check{m_{n}\geq 2}\check{l\geq 2}$$\check{j_{1}\#.\mathrm{B}\geq 1}\check{m_{1}\geq 1}$

に対して

,

$\mathrm{g}(\mathrm{x})=(0,1,0, \ldots, 0,0,0, \ldots, 0\vee k, \ldots, 0, \ldots, 0,1,0, \ldots, 0,0,0, \ldots, 0,1,1, \ldots, 1,0)\in\overline{\mathcal{W}}$$\tilde{2i_{1}-1}\check{m_{1}\geq 1}$

ここで $n=0$ の時,(2)$\tilde{\mathcal{X}}_{1}$$\mathrm{x}\in\tilde{B}$$\check{2i_{n}-1}\check{m_{n}-1}\tilde{l+1}$$\check{m_{n-1}\geq 1}$

である.

の要素について次のことが言える.

,$n\geq 1$$\mathrm{x}=(0,,\mathrm{o}, \ldots,\mathrm{o}, \ldots,\mathrm{o}, \ldots,\mathrm{o}_{1},0,1,\ldots, 0,1,0,1,\ldots,1,0)\in\tilde{\mathcal{X}}_{1}\frac{\dot{0},1,\ldots,0,1}{\dot{\iota}_{1}\Phi\geq 1}k\check{m_{1}\geq 1}\check{m_{n-1}\geq}\tilde{j_{n}\ovalbox{\tt\small REJECT}_{\geq 1}}\check{l\geq 2}$

に対して

.

$\mathrm{g}(\mathrm{x})=(0,1,0, \ldots, 0,0,0, \ldots, 0\vee k, \ldots, 0, \ldots, 0,1, 0, \ldots, 0, 0, 0, 1, \ldots, 1, 0)\in\overline{\mathcal{W}}$$\check{2i_{1}-1}\check{m_{1}\geq 1}$

Proof:$\check{m_{n-1}\geq 1}$$\check{2j_{h}-1}$$g(0,0,1)=1,$ $g(1,0,1)=0$ であることに注意すれば, (1)(2) いずれも容易に分かる.

Proposition 317$\mathrm{x}\in\tilde{\mathcal{X}}$とする. つまり$.\vee n$$.\vee 2$$.\vee 1$

(0,

$=$

$\mathrm{x}$.

$\mathrm{a}_{1},0_{m_{1}}$

, a2,

.1

$0_{m_{2)}}\ldots,$$0_{m_{n-1}},$$\mathrm{a}_{n},$

$0$

or

(0,

$m_{1}\geq 0,$

各$\mathrm{a}_{k}$の上に書かれているに関しても同様である. このような$i_{k}$$\mathrm{x}$

or

, a2,

$m_{2}\geq 0,$は,$\mathrm{g}^{t}(\mathrm{x})=$($\mathrm{g}^{t}(0,$$0_{m_{2}},$$\mathrm{v}\in \mathcal{V}$$\mathcal{X}_{2},$$\mathrm{a}_{k}$$\ldots,$$\ldots,$$0_{m_{n-1}},$$\mathrm{a}_{n},$$\vee \mathrm{j}$$0_{m_{n}},$$\mathrm{v},$

$0$

),

,
$m_{n-1}\geq 0,$の最後の要素が$m_{n}\geq 0$$\mathrm{x}$.

中に占める場所の座標番号を表す.

$j$

に対して,
$.\cdot\vee n$$.\cdot\vee 1$$\forall t\geq 0,$.

$\cdot$$\dot{.}.2$$\mathrm{a}_{1},0_{m_{1}}$$\mathrm{a}_{j}\in \mathcal{X}_{1}$),.n$\cdot$

ここで,$\check{l}$$\mathrm{a}_{1},0)_{-\infty,i_{1}},0,$$\vee\prime 2$$\mathrm{g}^{t}(0$, a2, $0):_{1}+2,i_{2},0,$$0,$ $\mathrm{g}^{t}(0,$$\ldots,$$\mathrm{a}_{n},$$0)j_{n-1}+2,j_{h},$ $0$),

または$\mathrm{g}^{t}(\mathrm{x})=(\mathrm{g}^{t}(0,\check{\mathrm{a}_{1}}.,0)_{-\infty,:_{1}},0, \mathrm{g}^{t}(0, \mathrm{a}_{2}..,0)_{*_{1}+2,i_{2}}.,0, \ldots, 0, \mathrm{g}^{t}(0,\check{\mathrm{a}_{n}}., 0)_{*_{n-1}+2,\dot{*}_{n}}., 0, \mathrm{g}^{t}(0, \check{\mathrm{v}}, 0):_{n}+2,\infty 12n\mathrm{j})$$\forall t\geq 0,$

42
である.

また

$2\leq\forall j\leq n,$$\forall t\geq T_{j}$$\exists T_{j},$,$\mathrm{g}^{t}(0,\check{\mathrm{a}_{j}}., 0)_{i_{\mathrm{j}-1}+2,i_{j}}\mathrm{j}=1:_{\mathrm{j}}-*_{j-1}\cdot-1$,$\vee \mathrm{j}$,$\forall t\geq T$$\exists T,$$\mathrm{g}^{t}(0, \mathrm{v}, 0)_{\dot{\iota}_{n}+2,\infty}=0$

であるから$\forall t\geq\max\{\max T_{j}2\leq j\leq n’ T\}$,,$\mathrm{g}^{t}(\mathrm{x})=(\mathrm{g}^{t}(0,\check{\mathrm{a}_{1}}.,0)_{-\infty,\dot{*}_{1}},0,1:_{2}-:_{1}-1,0, \ldots, 0,1_{\dot{*}_{n}-:_{n-1}-1},0)1$$\mathrm{g}^{t}(0, \mathrm{a}_{1},0)\in\overline{\mathcal{W}}$となる.

Proof-$g(1,0,\star)=0,$$g(0,1,0)=0,$ $g(0,1,1)=1$ に注意し, Propositions 314and 316 を用いればよい.

Example 318 $\mathrm{x}=(0,1,0,1,0,1,1,0,0,1,0,1,0,0,1,1,0)$ を初期 configuration としたときのtime-space pattern は次の図のようになる. 状態 1 は で表現されてぃる.
$\blacksquare$$\mathrm{x}=$

...

000
0 0
0
0
0
0
0
0 0
0 0
0

$\mathrm{g}(\mathrm{x})=$$\blacksquare$$\mathrm{g}^{2}(\mathrm{x})=$$\blacksquare$$\mathrm{g}^{3}(\mathrm{x})=$$\blacksquare$$\mathrm{g}^{4}(\mathrm{x})=$$\blacksquare$$\mathrm{g}^{5}(\mathrm{x})=$$\blacksquare$$\mathrm{g}^{6}(\mathrm{x})=$$\blacksquare$$\mathrm{g}^{7}(\mathrm{x})=$.
.
$\cdot$$\blacksquare$$\blacksquare$

.
.

...

$\cdot$.
.

$\cdot$$\blacksquare$.
.

0$\blacksquare$000$\blacksquare$$\blacksquare$$\blacksquare$00$\blacksquare$$\blacksquare$$\blacksquare$$\blacksquare$$\blacksquare$$\blacksquare$$\blacksquare$$\blacksquare$$\blacksquare$$\blacksquare$$\blacksquare$$\blacksquare$$\blacksquare$$\blacksquare$$\blacksquare$$\blacksquare$$\blacksquare$$\blacksquare$$\blacksquare$$\blacksquare$$\blacksquare$$\blacksquare$$\blacksquare$$\blacksquare$$\blacksquare$.
.

.

$\cdot$$\blacksquare$$\blacksquare$.

.
.

$\cdot$00$\blacksquare$$\blacksquare$00$\blacksquare$$\cdot$.

.

$\cdot$$\cdot$$\blacksquare$$\blacksquare$$\blacksquare$$\blacksquare$.

.

$\cdot$$\cdot$

.

.

0
0
0
0
0
0
0
0
.
.

0

$\blacksquare$0$\blacksquare$0$\blacksquare$0$\blacksquare$$\blacksquare$

0
0

0
0
$\blacksquare$0$\blacksquare$$\blacksquare$$\blacksquare$$\blacksquare$$\blacksquare$$\blacksquare$$\blacksquare$$\blacksquare$$\blacksquare$$\blacksquare$$\blacksquare$$\blacksquare$$\blacksquare$$\blacksquare$00$\blacksquare$$\blacksquare$$\blacksquare$$\blacksquare$$\blacksquare$$\blacksquare$$\blacksquare$$\blacksquare$$\blacksquare$$\blacksquare$$\blacksquare$$\blacksquare$$\blacksquare$$\blacksquare$$\blacksquare$$\blacksquare$$\blacksquare$$\blacksquare$$\blacksquare$$\blacksquare$$\blacksquare$$\blacksquare$$\blacksquare$$\blacksquare$$\blacksquare$$\blacksquare$$\blacksquare$$\blacksquare$

.

.

.
.

.
.

.

.
.

.
.

$\cdot$0000$\blacksquare$$\cdot$.

.

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

$\cdot$$\cdot$.
.

$\cdot$

0
0

...

0
0
0
0
0
0
.

.

$\cdot$...

以上の Propositions から次の Theorem 319 が成立する.

Theorem 319$\tilde{\mathcal{V}}\cap\tilde{\mathcal{X}}=\phi$

202 の

ルール

$\mathcal{F}$上の dyna 而$\mathrm{c}\mathrm{s}$に関して次のことが成立する.

$\mathcal{F}=\tilde{\mathcal{V}}\cup\tilde{\mathcal{X}}$,が成立していたことに注意せよ.
$\forall \mathrm{x}\in\tilde{\mathcal{V}},$$\forall t\geq 1$$\forall \mathrm{x}\in\tilde{\mathcal{X}},$,$\exists T,$$\mathrm{g}^{t}(\mathrm{x})=\sigma_{L}^{t-1}(\mathrm{g}(\mathrm{x}))\in\tilde{\mathcal{U}}$$\forall t\geq T$,$\mathrm{g}^{t}(\mathrm{x})\in\overline{\mathcal{W}B}$,.

に入ってからの動きは, Proposition 31.2(1) で述べられてぃて,に入ってがらの動きは, PropOsition 3.1.4 で述べられている. 以上でノレーノレ番号 202 を持つセノレオートマトンが 0-finite configurations$\tilde{\mathcal{U}}$$\overline{\mathcal{W}B}$全体の集合である$\mathcal{F}$

上でどのような dynamics を描くがにつぃては完全に解明できたことになり, またその time-space pattern も明らかにされたことになる.
$\tilde{\mathcal{U}}$上では \sigma 。と同等であり,$\overline{\mathcal{W}B}$

いく. 次の図を参照すること.

$\mathcal{F}$

上では 0 以外不動点も周期点も存在せず,

上では次の 3.2.1 節で述べられてぃる ft $p6$ の型の不動点に収束して

43
Dynamics of Rule 202 on$\mathcal{F}$$\mathcal{F}$

ルール番号 202 の length of pattern については次の Corollary が成立する.

Corollary to Theorem 319$\forall \mathrm{x}\in\tilde{\mathcal{V}},$$\forall \mathrm{x}\in\tilde{\mathcal{X}},$

32. ルール 202 と 216 の$S^{\mathrm{Z}}$$\forall t\geq T$,,$l(\mathrm{g}^{t}(\mathrm{x}))=l((\mathrm{g}(\mathrm{x})))$,.

$l(\mathrm{g}^{t}(\mathrm{x}))=l(\dot{\mathrm{g}}^{T}(\mathrm{x}))+(t-T)$

上での dynamics

216 は対称である. 本節ではルール 202 を考える. Theorem 3.19 よりノレーノレ 202

ルール 202 と$\mathcal{F}$$\exists T,$$\forall t\geq 2$(ま中には 0 以外不動点も周期点も持たず, 生成される time-space pattern はすでに述べた通りである.
であれば, 周期点でも不動点でもな . このような configurationは,$\mathrm{A}\mathrm{a}$$\mathrm{x}_{-\infty,k}=0,$$\mathrm{x}\in S^{\mathrm{Z}}\backslash \{0\}$$\exists k\in \mathrm{Z}$を左 0-finite であると呼ぶ. 同様にして右 0-finite configuration も定義できる.

321. 不動点
不動点の型は次の通りである.

fptl

:

$(..., 0, 1_{m_{-k}}, 0,1_{m_{-k+1}}, \ldots, 0,1_{m_{k-1})}0,1_{m_{k}}, 0, \ldots)$

fpt2

:

$(1, 0, 1_{m_{1}},0,1_{m_{2}}, \ldots, 0,1_{m_{k}}, \ldots)$,$(.. ., 0, 1_{m-k}, 0,1_{m-k+1}, \ldots, 0,1_{m-1},0,1)$ ,fpt4$(..., 0, 1_{m-k}, 0,1_{m-k+1}, \ldots, 0,1_{m-1},0)$:$(1, 0, 1_{m_{1}},0,1_{m_{2}}, \ldots, 0,1_{m_{k}}, 0,1)$

fpt6

:

$(1, 0, 1_{m_{1}},0,1_{m_{2}}, \ldots, 0,1_{m_{k}}, 0)$

,

,

,

$m_{i}\geq 2,$$m_{i}\geq 2,$$-\infty<i<\infty$$m_{i}\geq 2,$$m_{i}\geq 2,1\leq i<\infty$

fpt3
fpt5

,

,

,

$-\infty<i\leq-1$ ,$-\infty<i\leq-1$ ,$m_{i}\geq 2,1\leq i\leq k,$$m_{i}\geq 2,1\leq i\leq k,$$k\geq 0$$k\geq 0$,,

つまり, 長さ 2 以上の 1 のブロックが一つの 0 をはさんで隣り合っているような configuration

0-finite でないようなものが不動点である.
$\mathrm{x}\in S^{\mathrm{Z}}$が長さ 2 以上の 1 のブロックを右側に可算個持つ,$\exists k\in \mathrm{Z}$,$\mathrm{x}_{k,\infty}=1$

で左44
長さ 2 以上の 1 のブロックを少なくともーっ持ち右 0-finite である,のいずれかであれば$\mathrm{g}^{t}(\mathrm{x})$は,を参照すれば明らかである.

上記のいずれかの不動点に収束してぃく. このことは Proposition 317

また, Proposition 312 の証明に注意すれば,$\geq 2$となることが分かる. っまりこのような合成関数である.

$\mathrm{x}$,$\mathrm{x}\in S^{\mathrm{Z}}$が長さ 2 以上の 1 のブロックを持たなければ,$\mathrm{g}^{t}(\mathrm{x})=\sigma_{L}^{t-1}(\mathrm{g}(\mathrm{x}))$は,$\sigma_{R}\circ \mathrm{g}$の不動点である. ここで,$\sigma_{R}\circ \mathrm{g}$は$\sigma_{R}$と$\mathrm{g}$の322. 周期点(1) 長さ 2 以上の 1 のブロックを含まない場合. 1 が孤立してぃて, 1 と 1 との間の 0 の個数が2 以上であるような configuration の中に周期点が存在し得るが, 左 0-finite 及ひ finite configuration
は, 周期点になり得ない.
$\mathrm{x}=$従って次のような型の configuration を考える.

,$(\ldots, 0_{m_{-k}}, 1,0_{m_{-k+1}},1, \ldots, 1,0_{m_{k-1}},1,0_{m_{k}}, 1, \ldots)$

Proposition 312(1) の証明に注意すれば, このような$\geq 0$である. 従って,,$\mathrm{x}$$m:\geq 2,$(3.2.1)$-\infty<i<\infty$に対して(3.2.2)$\mathrm{g}^{t}(\mathrm{x})=\sigma_{L}^{t}(\mathrm{x})$このことから, 次の定理が成立する.

Proposition 3221
(3.2.1) の型の$\exists i\in \mathrm{Z},$$\mathrm{x}\in S^{\mathrm{Z}}$$\exists k\geq 1$

が $p$ 周期点になるための必要十分条件は, 次の条件を満たすことである ;,$m_{*+1}.+1+\cdots+m_{i+k}+1=p$ ,.
. . . $=m_{1-2k}$...

$=m:-k$$=\cdots$,$=m_{*+k-1}.=m_{\dot{*}+2k-1}=\cdots$,$=m:+k$$=m_{i}$$=m:-2k-1=m:-k-1=m:-1$$\ldots=m_{-2k-2}.=m_{-k-2}.=m_{i-2}$$=m:+2k$$=m:+k-2=m:+2k-2=\cdots$ ,. $..=m:-3k+1=m:_{-2k+1}=m_{*-k+1}.=m:+1$

Proofi$=m:+k+1=\cdots$ ,十分牲は明らかである. 必要性を示す.
$j:-k-1$
$=$

$($

...,

$\cdot.1-k$$j:-k+1\mathrm{j}.-1\mathrm{j}$$\mathrm{j}\check{1},0_{m}.-k$ $\cdot.\check{1},$,$\mathrm{o}_{m}-k+1^{\cdot}:’$\mathrm{j}\vee+1\vee+1,$\mathrm{i}:,$$\mathrm{o}_{m}.\cdot$,$\ldots$,$1:\dashv!-1,\mathrm{j}.\cdot+k$$\mathrm{j}0_{m_{j+k}},\check{1},$$0_{m}$

とおき,

この$\mathrm{x}$が $p$ 周期であるとする.

(3.2.2) がら$\exists i\in \mathrm{Z},$となる. このことから$\forall m\in \mathrm{Z},$$\exists k\geq 1$,$\sigma_{L}^{p}(\mathrm{x})=\mathrm{x}$,$\cdot.\check{1}:+k+1’\ldots)+k+1$

であるがら,$j_{i+k}-p=j_{\dot{\iota}}$.-p=l-。となり, Proposition が成立する.

$j_{1+k-m}$,

45
周期 3 以上の任意の周期点が存在することが分かり,$(..., 0_{p}, 1,0_{p)}1, , \ldots, 1, \mathrm{O}_{\mathrm{p}}, 1, \mathrm{O}_{\mathrm{p}}, 1, \ldots)$

が一つの $p+1$ 周期点である.

長さ 2 以上の 1 のブロツクのみから成るような(2) 長さ 2 以上の 1 のブロックを含む場合.
configuration で周期になるものは, fpt1. fpt2, fpt3, f
f$pt5$ のいずれかの型であり, これらは不動点である.
長さ 2 以上のブロックと孤立した 1 とが混在する configuration の場合, あるところから左側に長さ2 以上のブロックが, 右側に可算個の孤立した 1 が二つ以上の 0 をはさみながら存在しなければ周期点.

$tp\mathit{4}$[こなり得ない.

そこで次のような型の configuration を考える,$(..., 0, 1_{m_{-}}.\cdot, 0,1_{m_{-\cdot+1}}, \ldots, 0,1_{m_{-1}},0_{n_{1}}, \check{1}, \ldots,\check{1},0_{n.-1}.,\cdot\check{1}, \mathrm{o}_{n}.,\mathrm{i}\mathrm{j}_{1}\mathrm{j}_{i-2}\mathrm{j}\cdot-1j)\vee,$$\ldots$$-\infty<i\leq-1$ ,$m_{j}\geq 2,$(1, 0,$1_{m_{-\mathrm{I}}},$$0,1_{m_{-\iota+1}},$ $\ldots,$ $0,1_{m-1}$,$\check{1}j_{1},$$0_{n_{1}},$$m_{j}\geq 2,1\leq i\leq l,$$l\geq 0$$\ldots$,,. $\geq 2,2\leq i<\infty$$n_{1}$$\mathrm{j}_{-2}.\dot{1},0_{n.-1},\cdot\check{1}j\cdot-1$$n_{1}\geq 1,$,$0_{n:}$, ),,乙$\ldots$(3.2.4)$n_{i}\geq 2,2\leq i<\infty$, ... の間の関係で決まる. $g(1,0,1)=$$g(0,1,0)=0$ であることに注意すると, 次の Proposition が容易に得られる.

このような configurations が周期になるかどうかは,$0,$$n_{1}\geq 1,$(3.2.3)$n_{1},$$n_{2}$

Proposition 3222(2.4.3) または (2.4.4) の型の configuration が $p\geq 3$ 周期点になるための必要十分条件は, 次の条件を満たすことである ;$\exists i\in \mathrm{Z},$$\exists k\geq 1$,$i\leq k$,$n_{1}+n_{2}+1+\cdots+n_{j}+1\leq p$ ,$n_{i+1}+1+\cdots+n_{i+k}+1=p$ ,$n:+1=n:+k+1=n_{j+2k+1}=\cdots$ ,$n_{i+2}=n_{i+k+2}=n_{i+2k+2}=\cdots$ ,$n_{1}-1\leq n_{k+1}=n_{2k+1}=n_{3k+1}$$=\cdots$,$n_{2}$$=n_{k+2}=n_{2k+1}=n_{3k+2}$$=\cdots$,:$=n_{i+k}=n_{j+2k}=n:+3k$$=\cdots$,$n$(3.2.1), (3.2.3) または (3.2.4) の型以外に存在しない. また,
周期 2 の周期点は存在しない. これは $g(1,0,1)=0,$ $g(0,1,0)=0$ であることから言えるが, このことから次の Corollary も成立する.
ルール 202 の周期 3 以上の周期点は,Corollary(1)3 周期点は,(..., 1,0, 0, 1,0, 0, 1, 0, 0, 1, ...),$(..., 0, 1_{m-}., 0,1_{m_{-\cdot+1}}, \ldots, 0,1_{m-1},0_{n_{1}},1,0,0,1,0,0,1,0,0,1, \ldots)$$m_{j}\geq 2,$$-\infty<i\leq-1$ ,$1\leq n_{1}\leq 3$$(1, 0, 1_{m-\iota}, 0,1_{m-l+1}, \ldots, 0,1_{m-1},0_{n_{1}},1,0,0,1,0,0,1,0,0,1, \ldots)$$m_{i}\geq 2,1\leq i\leq l,$$l\geq 0$,$1\leq n_{1}\leq 3$

,

,

46
の型に限る.

(2)

4 周期点は,$(_{\sim}.., 1,0,0,0,1,0,0,0,1,0,0,0,1, \ldots)$,$(..., 0, 1_{m_{-:}}, 0,1_{m_{-:+1}}, \ldots, 0,1_{m_{-1}},0_{n_{1}},1,0,0,0,1,0,0,0,1,0,0,0,1, \ldots)$$m:\geq 2,$$-\infty<i\leq-1$ ,$1\leq n_{1}\leq 4$$(1, 0, 1_{m_{-l}}, 0,1_{m_{-l+1}}, \ldots, 0,1_{m_{-1}},0_{n_{1}},1,0,0,0,1,0,0,0,1,0,0,0,1, \ldots)$$m:\geq 2,1\leq i\leq l,$$l\geq 0$,,,$1\leq n_{1}\leq 4$の型に限る.

3.2.3 ルール 202 の少し変わった動き
ルール 202 は,ウルフラムの分類にょるとクラス に属し, configuration の時間発展はいずれ安定した動きになるとされている. しかしながら, 以上の考察から次の例で示されるような動きをするものが存在し, ウルフラムの主張は必ずしも成立しないと予想され得る.
$\mathrm{I}\mathrm{I}$

次のような configuration$\mathrm{x}$を考える.

この configuration

はさんだ孤立した 1 が可算個存在する.
$\mathrm{x}=(1,0_{m_{1}},1,0_{m_{2}},1, \ldots, 1,0_{m}., 1, \ldots),$の右側には, 少なくとも二っ以上の 0 を. $\geq 2$ , l<i<0 科$m_{*}$

このような configuration の時間発展は, 例えば次の図のようになる. 状態 はで表されてぃる.
1
左側にある 1 のブロックが壁のようになり, 右側から押し寄せてくる が壁の1
T 度一っ手前で消え去$\blacksquare$

るといった現象が時間発展と共に無限に生じることになる. まるで高速道路を走行中の自動車のフロン
トガラスに次々と向かってくる ラブバックのようではないか. 1 と 1 の間の 0 の個数がランダムに与えられていれば, このような動きは安定してぃるとは考えにく , もちろん周期的ではないし,不動点にも収束しない.
ウルフラムの分類は, 一概には成立せず, 初期 configuration にょって, 描がれる時空間パターンが$\langle$

大きく異なるであろうことが予想され得る.

4. ルール 234 と 248

47
第 4 節でルール 234 が生成する時空間’ くターン [こつルール 234 と 248 は対称である.

ルール番号 234 の local rule

この第 4 節では

$g_{234}$を簡単にうになるかについて調べる.
り,$g_{234}$は,$g_{202}$て述べる.

次の表のように与えられる.

と書くことにし,$g$$\mathrm{A}\mathrm{a}$$\mathrm{x}\in S^{\mathrm{Z}}$に対して dynamics$\{\mathrm{g}^{t}(\mathrm{x})\}_{t\geq 0}$

力{どのよとの違いは, $g_{202}(101)=0$ に対して $g_{234}(101)=1$ であることであ

その他の対応関係は同じであることに注意する.

4.1. ルール 234 の$\mathcal{F}$上での dynamics$g(0,0,1)=1,$ $g(0,1,1)=1,$ $g(1,1,1)=1,$ $g(1,1,0)=1,$ $g(1,0,0)=0,$ $g(0,0,0)=0$に注意すれば,$\mathrm{x}=(0,1_{n}, 0)=(\ldots, 0, 0,0, \frac{\vee 1,1,\ldots,1,1i\mathrm{j}\vee}{n\geq 2}, 0,0,0, \ldots)\in\tilde{B}$に対して$\forall t\geq 0$,,$\mathrm{g}^{t}(\mathrm{x})=(0,1_{n+t}, 0)=(\ldots, 0,0,0, \cdot.\vee-t11, \ldots, 1,1\mathrm{j}.,0,0,0, \ldots)\in\tilde{B}$

,–
$n+t$

である. つまり,$\forall \mathrm{x}\in\tilde{B},$であり,$\tilde{B}$上では$\mathrm{g}202$と$\mathrm{g}_{234}$$\mathrm{g}_{202}(\mathrm{x})=\mathrm{g}_{234}(\mathrm{x})$とは同じ dyna 而を描く.

$\mathrm{c}\mathrm{s}$また,$g(0,0,1)=1,$ $g(0,1,0)=0,$ $g(1,0,1)=1,$ $g(1,0,0)=0$
であることに注意すれば,$\forall \mathrm{x}\in\tilde{\mathcal{V}},$$\forall t\geq 0$,$\mathrm{g}^{t}(\mathrm{x})=\sigma_{L}(\mathrm{x})$となる. ルール番号 202 の場合は,$\forall \mathrm{x}\in\tilde{\mathcal{U}},$$\forall t\geq 0$,$\mathrm{g}_{202}^{t}(\mathrm{x})=\sigma_{L}^{t}(\mathrm{x})$,$\mathrm{g}_{202}(\tilde{\mathcal{V}}\backslash \tilde{\mathcal{U}})\subset\tilde{\mathcal{U}}$であったが,

ルール番号 234 の場合は,$\tilde{\mathcal{V}}$上で$\mathrm{g}_{234}=\sigma_{L}$となる.

以上ことから次の Proposition 4.1.1 が得られる.

Proposition 411$\mathrm{x}=(0,0,1, \ldots, 0,1,0, \ldots, 0, \ldots, 0, \ldots, 0,0,1, \ldots, 0, \check{1}, 0,0, \ldots, 0,1, \ldots, \check{1}, 0)\in\tilde{\mathcal{X}}_{1}\cup\tilde{\mathcal{X}}_{2}pq$

組$\check{m_{n}\geq 1}\overline{l\geq 2}$$\check{m_{n-1}\geq 1}$$\check{m_{1}\geq 1}$$i_{1}$$i_{n}$$\geq 1$組$\geq 1$に対して$\vee q$$\forall t\geq 0$,$\mathrm{g}^{t}(\mathrm{x})=\sigma_{L}^{t}(\mathrm{x}_{-\infty,p}, 0)\oplus(0,1, \ldots, 10)\vee$’$\mathrm{t}+t$,$n\geq 0$

48
である.

$n\ovalbox{\tt\small REJECT} 0$の時は,$\epsilon\ovalbox{\tt\small REJECT}$$\mathrm{x}\ovalbox{\tt\small REJECT}$$(0, \mathrm{I}_{\mathrm{I}}, 0)$であり, すでに述べたように$\forall t\ovalbox{\tt\small REJECT} 0,$$\in\ovalbox{\tt\small REJECT}$$\ovalbox{\tt\small REJECT}(\mathrm{x})\ovalbox{\tt\small REJECT}(0,1\ovalbox{\tt\small REJECT} t, 0)$である.
$g_{234}(1,0,1)=1$ であることに注意すると,$\mathcal{F}$

得られる.

上の g2 あの dynamics に M する次の Theorem 412 がTheorem 412$\forall \mathrm{x}\in\tilde{\mathcal{V}},$$\forall t\geq 0$$\forall \mathrm{x}\in\tilde{\mathcal{X}},$,,$\mathrm{g}^{t}(\mathrm{x})=\sigma_{L}^{t}(\mathrm{x})\in\tilde{\mathcal{V}}$$\forall t\geq T$$\exists T,$,$\mathrm{g}^{t}(\mathrm{x})\in\tilde{\mathcal{X}}_{1}\cup\tilde{\mathcal{X}}_{2}$である.

$\tilde{\mathcal{X}}_{1}\cup\tilde{\mathcal{X}}_{2}$

上でのルール 234 の動きは.

Proposition 4 垣で述べられてぃる.

動きに比べ単純に成ってぃることが分かるが.

ルール 202 の$\mathcal{F}$上でのこれは g2 あ $(1, 0, 1)=1$ と $g202(1,0,1)=0$ の違いにょるものである. 次の図を参照せよ.

Dynamics of Rule 234 on$\mathcal{F}$$\mathcal{F}$

ルール番号 234 の length of pattern については次の Corollary が成立する.

CoroUary to Theorem 412$\forall \mathrm{x}\in\tilde{\mathcal{V}},$$\forall \mathrm{x}\in\overline{\mathcal{X}},$

42. ルール 234 と 248 のノレーノレ 234 の$S^{\mathrm{Z}}$$\exists T,$$S^{\mathrm{Z}}$$\forall t\geq 0$$\forall t\geq T$,,$(1, 0)$ ,$\mathrm{x}$(1),$\mathrm{x}$,$l(\mathrm{g}^{t}(\mathrm{x}))=l(\mathrm{g}^{T}(\mathrm{x}))+(t-T)$

上での dynamics

上での dynamics は simple で,$\lim_{tarrow\infty}\mathrm{g}^{t}(\mathrm{x})=\{$$l(\mathrm{g}^{t}(\mathrm{x}))=l(\mathrm{x})$$\forall \mathrm{x}\in S^{\mathrm{Z}}\backslash \{0\}$に対しては右 0-finite で長さ 2 以上の 1 のブロックを少なくともーっ持っ,は右 O-finite でなく長さ 2 以上の 1 のブロックを少なくともーっ持っ,

または$\forall t\geq 0$,$\mathrm{g}^{t}(\mathrm{x})=\sigma_{L}^{t}(\mathrm{x})$,$\mathrm{x}$は長さ 2 以上の 1 ブロックを持たない

49(0) は不動点であるから, ルール 234 においては, 不動点の型は (0), $(1, 0)$ , (1) 以外に存在
せず, 任意のは長さ 2 以上のブロックを少なくとも 1 つ持てば, 不動点もしは究極的不動点でとなる.

$\mathrm{x}\in S^{\mathrm{Z}}$

ある.

これは,

ルール 202 との大きな違いであり,このことが $g_{234}(1,0,1)=1$ と $g_{202}(1,0,1)=0$ との違いによってのみ引き起こされていることに注意すべきである.
周期点は, 右 0-finite でも左 0-finite でもなく,

1 が可算個存在するような configuration でなければならず, 次のような型でなければならない.
$\mathrm{x}=$$(\ldots, 0_{m_{-k}}, 1,0_{m_{-k+1}},1, \ldots, 1,0_{m_{k-1}},1,0_{m_{k}}, 1, \ldots)$,$m_{j}\geq 1,$(4.2.1)$-\infty<i<\infty$

Proposition 32.2.1 の証明と同様にして次の Proposition が成立する.
Proposition 421$\mathrm{x}\in s^{\mathrm{Z}}$が $p\geq 2$ 周期点になるための必要十分条件は,$\mathrm{x}$が (4.2.1) の型でありかつ次の条件を満たすことである ;$\exists i\in \mathrm{Z},$$\exists k\geq 1$,$m_{i+1}+1+\cdots+m_{i+k}+1=p$ ,$\ldots=m_{i-2k}$$=mj-k$$=m_{i}$$=m_{i+k}$$=m_{j+2k}$$=\cdots$,$\ldots=m_{i-2k-1}=m_{i-k-1}=m_{j-1}$$=m_{i+k-1}=m_{j+2k-1}=\cdots$ ,. . . $=m_{j-2k-2}=m_{i-k-2}=m_{i-2}$$=m:+k-2=m\dot{*}+2k-2=\cdots$. . . $=m_{i-3k+1}=m_{i-2k+1}=m_{i-k+1}=m_{i+1}$$=m_{i+k+1}=\cdots$,,

Corollary to Proposition 421(1)2 周期点は, (..., 1, 0, 1, 0, 1, 0, 1, .. ) の型以外に存在しない.
(2) 3 周期点は (..., 1, 0, 0, 1, 0, 0, 1,0, 0, 1, .. ) 以外に存在しない.
ルール 234 では,

全ての周期点が存在する. 周期点に関するルール 204 との違いは, 2 周期点が存在するかどうかである.

REFERENCES[1] G.Braga, G.Cattaneo, P.Flocchini and C.Quaranta Vogliotti, Pattern growth in elementary
cellular automata, Theoretical Computer Science, 145(1995), 1-26.
[2] G. Cattaneo and L. Margara, Generalized sub-shifts in elementary cellular automata: the“strange case” of chaotic rule 180 Theoretical Computer Science, 201(1998), 171-187.
[3] C. G. Langton, STUDYING ARTIFICIAL LIFE WITH CELLULAR AUTOMATA, Physica$22\mathrm{D}(1986)$ , 120-149.
PROCEEDINGS OF THE[4] C. G. Langton, Life at the Edge of Chaos, ARTIFICIAL LIFE
WORKSHOP ON ARTIFICIAL LIFE HELD FEBRUARY, 1990 IN SANTAFE, NEW MEXICO,
edited by Christopher G.Langton, Charles Taylor, J.Doyne Farmer and Steen Rasmussen, AddisonWesley Publishing Company, 41-91.
[5] F. Ohi and Y. Takamatsu, Time-Space Pattern and Periodic Property of Elementary Cellular
Automata -Sierpinski Gasket and Partially Sierpinski Gasket -, Journal of Industrial and Applied$\mathrm{I}\mathrm{I},$Mathematics, 18(2001), 59-73.
[6] S. Wolfram, Statistical mechanics of cellular automata, Review of Modern Physics, 55(1983),

50[7] S. Wolfram, UNIVERSALITY AND COMPLEXITY IN CELLULAR AUTOMATA,$10\mathrm{D}(1984),1- 35$.