数理解析研究所講究録
第 1562 巻 2007 年 46-55

46

セルオートマトンの近傍系関数–近傍系を変える一Changing the Neighborhood of CA
西尾英之助 (元・京大理)Hidenosuke Nishio 1
ex. Kyoto University, Japanemail: YRA05762\copyright nifly.com

andトーマス・ヴォルシュ (カールスルーエ大学情報学部)
Thomas Worsch
University of Karlsruhe, Germany
email : worsch\copyright ira.uka.de
概要:セルオートマトンの伝統的な定義 $CA=(S,$ $Q,$ $N$ , のに代えて 変数の局所関数の各変数を異なる近傍に対応させる近傍系関数と呼ばれる単射 : $\{0,1, \ldots, n-1\}arrow S$ を導入して新しい
定義 $(S, Q, f_{n}, \nu)$ をする. これによりセルオートマトン研究に新たな境地を開くの値域 Imageは通常の意味の大きさ の近傍系と考えられる. 先ず初めに局所関数を一個固定しておき, 近傍関数を変えることにより, 無数の異なるセルオートマトンが作れることを証明する. 次いでこれらのセルオートマトンの同値関係が決定可能であることを示す. 解析問題の手始めとして可逆性を考える. 具体的に 3 変数関数ゐを考え, 近傍系関数の例として大きさが 3 の近傍系の置換全体を考える.
2 状態の場合は 次元 CA の可逆性が置換あるいは任意の近傍系を取っても保存されることを証明
し, 3 状態の場合は 1 次元 CA において置換により可逆性が保存されないことを反例により証明する. 付録に近傍系を変えた場合の計算機シミ
レーションを示す.
$n$

$\nu$

$\nu$

$(\nu)$

$n$

$n$

$=$

1

序訥

セルオートマトン (CA と略記する)

は空間的に一様な構造を持っ情報処理システムであり, 伝統
的に 4 項組 ( $S,$ $Q,$ $N$ , ので表す. ここで $S$ は (無限に) 多数のセルからなる離散的な空間,Q は各
セル共通の状態の有限集合,N は CA の近傍系と呼ばれる $S$ の有限集合,f は局所 (状態遷移) 関数$Q^{N}arrow Q$ である. 近傍系はセルオートマトンを特徴付ける基本的な要素である.
CA の研究の大半は 1 次元や 2 次元の格子空間で Neumann 近傍や Moore 近傍の様に標準的な近傍系を想定して, 与えられた特定の問題 (自己増殖, 計算万能性, 一斉射撃など) を満たす局所関数を探し求めたり,CA が定める写像の数学的性質や振る舞い (ダイナミカルシステム, カオス, 全単射,
可逆性など) を研究する. しかし 2003 年頃, HNishio とは近傍系それ自体の研究を始めた [4]. そこでは多次元離散ユークリッド空間や hyperbolic 空間において近傍系が全体を満たす (生成する) 条件が論じられた. この枠組みを踏まえて, ’.「近傍系は如何にセルオートマトンの$M.Ma_{\mathfrak{B}^{eIlStem}}$

振る舞いに影響するか ?’ を議論し, 近傍系の変化に依存しない性質とそうでない性質が例示された [3].
これに触発されて, T. Worsch は局所関数を 1 個定めておいて近傍系を変えることにより任意のセルオートマトンをシミュレートする方式を考えた [10]. この共同研究において H. Nishioはここで述べる近傍系関数の定式化に至った.

lcorr\infty wnding author

47

CA の新しい定義は 4 項組み $(S, Q, f_{n}, \nu)$ である. ここでは近傍系関数と呼ばれる単射 $\{0,1, \ldots, n-1\}arrow S$ である.\mbox{\boldmath $\nu$} は局所関数の各変数をそれぞれ異なるセル (近傍)におけるに結合するものである. の値域 range
は通常の近傍系 $N$ と考えられる. 例えば
Neumann 近傍は $\nu(0)=(0,0),$ $\nu(1)=(0,1),$ $\nu(2)=(0, -1),$ $\nu(3)=(1,0)$ and $\nu(4)=(-1,0)$ なる近傍系関数 で定義される.
$f_{n}$

は $n$ 変数の局所関数で$\nu$$\mathbb{Z}^{2}$$(\nu)$

$\nu$

$\nu$

次節で新しい CA の定義を与えた後,3 節で先ず基本的な定理として,n $=3$ の場合について任意の1 個の (定数でない) 局所関数から近傍系を変えることにより無限個の CA が作れることを証明する.4 節ではこのような CA の同値性が決定可能であることを示す. 後の節では近傍関数を変えることにより生ずる幾つかの問題を扱う. 特に 3 変数関数んを考え, 近傍系関数の例として大きさが 3の近傍系の置換全体を考え,2 状態の場合は置換によって可逆性が変わらないことを示し 3 状態の場合は変わる場合があることを複数の計算機プログラムによる反例により証明する. 付録に計算万能である R110 の近傍系を変えた場合の計算機シミュレーションの 2, 3 の結果を示す.

2 準備
2.1 定義理論は一般に高次元の CA に通用するが, ここでは 1 次元の場合に限り定義を与える.

1 次元 CA は 4 項組み

1.

で与えられる. ここでは整数全体の集合. 各セルはひとっの整数と同一視する.

$\mathbb{Z}$

2.

$Q$

3.

$f_{n}$

4.

$(\mathbb{Z}, Q, f_{n}, \nu)$

はセルの有限状態集合で有限体 $GF(q),$ $q=p^{k},p$ は素数,k は正整数である.

: $Q^{n}arrow Q$ は 変数の局所関数 $f_{n}(x_{0},x_{1}, \ldots,x_{n-1}),n\geq 1$ である.
$n$

を近
の変数
への単射で近傍系関数と呼ばれる. 近傍系関数は傍に対応させる. すなわち range $(\nu)=(\nu(O), \nu(1),$$\nu(n-1))$ は CA の近傍系を与える.
近傍系は単なる $S$ の部分集合ではなくて順列であることに注意. 例えば $(-1,0,1)\neq(-1,1,0)$が単射でない場合 (degenerate) も考えられるがここでは扱わない.
$\nu$

は $\{0,1, \ldots,n-1\}$ から$\mathbb{Z}$$f_{\mathfrak{n}}$$x_{t}$$\nu(i)$$\ldots,$

.

$\nu$

$f_{n}(x_{0},x_{1, )}x_{n-1})$

は $Q$ 上の $n$ 変数多項式で表されるが [5], 特に 3 変数の場合は以下のように書ける.
$f_{3}(x,y, z)=u_{0}+u_{1}x+u_{2}y+\cdots+u_{1}x^{h}\dot{\psi}z^{k}+\cdots$$+u_{q^{3}-2}x^{q-1}y^{q-1}z^{q-2}+u_{q^{3}-1}x^{q-1}y^{q-1}z^{q-1}$,

where $u_{i}\in Q,$ $0\leq i\leq q^{3}-1$ . (1)
更に $Q=GF(2)=\{0,1\}$ なら$f_{3}(x,y,z)=u_{0}+u_{1}x+u_{2}y+u_{S}z+u_{4}xy+u_{5}xz+u_{6}yz+u_{7}xyz$ ,where $u_{1}\in\{0,1\},$ $0\leq i\leq 7$ . (2)式 (2) で表される局所関数んを Elementary Local Function (ELF と略記) と呼ぶ. 式 (2) から $2^{8}=256$
あるいは $(-1,0,1)$ を Ele個の ELF があることが解る. irange $(\nu_{E})=(-1,0,1)$ なる近傍系関数$(\mathbb{Z},GF(2),$$ghBorh\inftyd$$(\mathbb{Z},GF(2),$
あるいは$(-1,0,1))$
mentary Nei)
fimction (ENB) と呼ぶ.
は通常 Elementary Cellular Automaton (ECA) と呼ばれ, その性質が多くの研究者によって調べられている, 例えば [91. ここで局所関数を多項式で定義したが, 以下では [9] に言及する関係でいわゆるWolffam number を用いる. なお多項式の係数から Wolffam number を計算することができる. 例:$\nu_{E}$$f_{3},$$\nu_{E}$$f_{3},$

48$Q=GF(2),f_{3}(x,y, z)=x+z$ の $Wol\theta amnumber$ は 90 である.
; $Q^{Z}arrow Q^{Z}$ を定義する: 任意の様相 $c\in Q^{Z}$ とセノ j $\in Z$ に対し
最後に局所関数から全域関数て $c(j)$ を におけるセル の状態として$F_{\nu}$

$j$

$c$

$F_{\nu}(c)(j)=f(c(j+\nu(0)),c(j+\nu(1)),$ $\ldots,c(j+\nu(n-1)))$と定義する. 通常 CA とその全域関数

2.2

$F$

.

(3)

を同一視する.

図示

伝統的な CA:..

Figl は 1 次元 CA で近傍系が ENB すなわち $N=(-1,0,1)$ の場合を示す.
$c$$d=F(c)$$.$.

$\cdot\cdot$$\cdot$.

Figurc 1: 伝統的な CA
新しい CA の定義 :Fig 2 は $(Z, Q, f_{3}, \nu)$ , ただし 3 変数関数ん (xOhの場合の図である.

$Figur\epsilon 2$$x_{1},x_{2}$) で range $(\nu)=(-2,0,1)$: 新しい定義の CA

これまでの考察から異なる近傍系関数が異なる CA を与えることは容易に理解できるであろう. このことを次節で証明する.

49

3 近傍系を変えて無限個の CA を作る
定理 1 近傍系を変えることにより, 任意の 1 個の定数でない 3 変数局所関数 $f_{3}(x,y, z)$ から無限個のセルオートマトンが作れる.
証明 :んが定数でないならば以下の三っの場合の少なくとも一つに該当することは明らかである.
1) $f_{3}(a,b, c)\neq f_{3}(a, b, d)$ for $a,$ $c\neq d\in Q$ の場合 : 同じ局所関数 $f_{3}(x, y, z)$ を持ち異なる近傍系$(-1,0,1+k)$ と $(-1,0,1+k’)(0\leq k<k’)$ を持つ CA と CA’ を考える. すると様相 $W=vab\delta d’dw$に対して, $F(W)(O)=f_{3}(a, b, c)\neq f_{3}(a,b, d)=F’(W)(O)$ となる. 但し $W(O)=b,$ とは長さ$k-1$ とと $-k-1$ の $Q$ 上の語で と $w$ は半無限の語である. すなわち $F(W)\neq F’(W)$ である. この様にして 1 個の関数たから加算無限個の $CA\{(Z, Q, f_{3}, (-1,0,1+k)), k\geq 1\}$ が作れる.
$b,$$\delta$$\delta^{j}$

$v$

$-1$
$W$

$0$

$k’$

$k$

$v$

$F(W)$

口囚$v’$$\zeta$口$\zeta’$口$w’$

2) $f_{3}(a,b,c)\neq f_{3}(a,b’,c)$ for $a,b\neq b’,c\in Q$ の場合 : 同じ局所関数ん $(x, y,z)$ を持ち具なる近傍
系 $(-1,2+k, 1)$ と $(-1,2+k’, 1)$$(0\leq k<k’)$ を持つ CA と CA’ を考える. すると様相 $W=$
$vadc\delta b\delta’b’w$に対して, $F(W)(O)=f_{3}(a, b, c)\neq fi(a,b^{j}, c)=F^{j}(W)(0)$ となる. 但し $W(O)=d,$とは長さた $-1$ と $k’-k-1$ の $Q$ 上の語で と $w$ は半無限の語である. すなわち $F(W)\neq F’(W)$である. この様にして 1 個の関数んから加算無限個の $CA\{\{(\mathbb{Z}, Q, f_{3}, (-1,2+k, 1)), k\geq 1\}$ が作$\delta$$\delta’$

$v$

れる.

$v$ ロロ$w$$F(W)$...

$v’$$1\delta$

口鴎$\ovalbox{\tt\small REJECT}\nu\square w$$\delta’$$\square$3) $f_{3}(a,b, c)\neq f_{3}(a’,b, c)$ for $a\neq a’,$ $c\in Q$ の場合 : 同じ局所関数ゐ (x, $y,$ ) を持ち具なる近傍系$(-k-1,0,1)$ と $(-k’-1,0,1)(0\leq k<k’)$ を持つ CA と CA’ を考える. すると様相 $W=va’\delta’a\delta w$
に対して, $F(W)(O)=f_{\theta}(a, b, c)\neq f_{S}(a’, b, c)=F’(W)(O)$ となる. 但し $W(O)=b,$ とは長さ$k-1$ とた’ $-k-1$ の $Q$ 上の語で と $w$ は半無限の語である. すなわち $F(W)\neq F’(W)$ である. この様にして 1 個の関数たから加算無限個の $CA\{(\mathbb{Z}, Q, f_{3}, (-1-k, 0,1)), k\geq 1)\}$ が作れる.
$b,$

$z$

$\delta$$\delta’$

$v$

$W$

$F(W)$

$v$

...

$v’$

$k’$
$\square$$\delta’$$\zeta’$$k$$\square$$\delta$$0$ $1$$w$$\zeta$$\blacksquare$

系 12 状態 3 近傍の $CA$ は近傍系を変えることにより (256 個の $ECA$ 以外に) 無限個存在する.

50

4 CA の同値問題$\mathbb{Z}$と $Q$ が解っている時は$(\mathbb{Z}, Q, f_{n}, \nu)$

定義 12 個の $CA(f_{n}, \nu)$ とと表す.

$(f_{n}’,, \nu’)$を $(f_{n}, \nu)$ と書く.

はその全域関数が同じ場合に限り同値であると定義し$(f_{\mathfrak{n}}, \nu)\cong(f_{n}’,, \nu’)$

一般的に同じ局所関数と具なる近傍系を持つ CA が同値であったり, 異なる局所関数でも近傍系を変えることにより同値な CA を与えることがある.
ここで同値問題が決定可能であることを証明する. この証明方法はセル空間の次元に関係しない.
定理 2 $CA$ の同値問題は決定可能である.

証明 : 同じ状態集合 $Q$ を持つ 2 個の CA
おき, $\ell:Narrow Q$ なる” 部分様相” を考える.

$(f_{\mathfrak{n}}, \nu)$と$(f_{n}’,, \swarrow)$を考える. $N=range(\nu)$ Urange(’) と様相 において有限部分 $N$ の外側を変えても $F(c)(O)$ あるいは $F’(c)(O)$ の計算は変わらない. 従って任意の部分様相 が状態 $F(c)(O)$ あるいは $F’(c)(O)$ を決める. それを $G(\ell)$ および $G’(\ell)$ と書く.
$c$$\ell$$\bullet$

ここで 2 個の CA が同値でないと仮定する:, すなわち対応する全域関数 $F$と $F’$ は異なる. すると $F(c)\neq F’(c)$ となる様相 が存在する. 全域関数とシフトは可換なので, 一般性を失うことなく $F(c)(O)\neq F’(c)(0)$ と仮定する. この場合は G(\ell )\neq G’(のとなる$\ell=c|_{N}$ が存在する.
$(f_{n}, \nu)\not\cong(f_{n}’,, \nu’)$$c$$\bullet$

他方 $G(\ell)\neq G’(\ell)$ なる が存在する場合には, 明らかに $c|_{N}=\ell$ を満たす
$F(c)\neq F’(c)$ である.
従って 2 個の CA は異なる.
$\ell$$c$に対して同値関係を決定するためには任意の $\ell:Narrow Q$ について G(P)=G’(のを (有限の手数で) 調べれ
ぱ良い. もしそうなら CA は同値だし, そうでなければ同値でない.

$\blacksquare$

以下, この論文では局所関数は同じ数の変数を持っ場合を扱うが,n $\neq n’$ の例として次の命題 1 を示す.

次の命題は容易に証明できるが, 近傍系関数によって定義される CA が通常の scope $2r+1$ の近傍系を持つ A と同値になることを示す.
命題 1に対して $r= \max\{|\nu(i)||0\leq i\leq n-1\}$ とする. すると同値な $CA(f_{2r+1}’, \nu’)$ があと同じ値を取る一方, ’(i) $\not\in range(v)$ となる変数 : は考えなくても良い (don care).
$(f_{n}, \nu)$る. 但し nmge(’) $=(-r, -r+1, \ldots,0, \ldots., r-1,r)$ であり, $f_{2r+1}’$ は range $(\nu)$ では$x$$f_{n}$$\prime t$

5 Neighborhood Family と Permutation Family
近傍系を変えたり置換することで得られる CA の 2 つの family を定義して, それらに関する幾っかの性質を示す.

定義 2$f_{n}$の neighborhoodfamily$\mathcal{F}(f_{n})$とは次で定義される全域関数の無限集合である.

$P(f_{\mathfrak{n}})= \bigcup_{\nu\in N_{n}}\{(f_{n},\nu)\}$但し$N_{n}$.

は $\nu:\{0, \ldots,n-1\}arrow Z$ なる全ての単射の集合である.

(4)

51

定義 3range

familyと表し,\mbox{\boldmath $\nu$} が解っている場合は単にの置換 をを以下で定義する.

$(\nu)$$\prime y(f_{n}, \nu)$$\pi$$\pi(\nu)$$\varphi(f_{n},\nu)=\bigcup_{i=0}^{n!-1}\{(f_{\mathfrak{n}},\pi_{i}(\nu))\}$$\pi$と表す. $(f_{n}, \nu)$ の pemutation

.

$(S)$

例: $n=3$ の場合,ENB の 6 個の置換は次の通りである.
$\pi_{0}=(-1,0,1),\pi_{1}=(-1,1,0),\pi_{2}=(0, -1,1)$ ,.

$\pi_{3}=(0,1, -1),\pi_{4}=(1, -1,0),\pi_{5}=(1,0, -1)$

愈題 2 ある近傍系
$\nu$

$\nu$

に対して $n$ 変数の局所関数を持つ $CA$ の集合 { $(f_{n},$: n-a’yfmction} は$\nu)|f_{\mathfrak{n}}$の置換で閉じている. すなわち$\bigcup_{f_{n}}\varphi(f_{n}, \nu)=\bigcup_{1=0}^{n1-1}\{(f_{n},\pi_{i}(\nu))\}=\bigcup_{fu}\{(f_{n},\nu)\}$.

(6)

証明 : 近傍系の置換は近傍系を固定しておいて局所関数の変数を置換することと同じである. すなわ$1\leq\exists i\leq n!-1$ があって, $(f_{n}, \nu)\cong(g_{n}, \pi_{i}(\nu))$と近傍系の置換
ち, 任意の関数あに対して関数となる.
$\pi_{i},$$g_{\mathfrak{n}}$$\blacksquare$

以下に近傍系を変えることによって影響されない CA を 3 例挙げる.
命題 3
意の$f_{\mathfrak{n}}(x_{1}, \ldots,x_{n})$$(f_{n}, \nu)\in \mathcal{F}(f_{n})$の関数である時,totalistic と呼ばれる. もしは totalistic である.
が$\sum_{|=1}^{\mathfrak{n}}x_{i}$命題 4 以下のように局所関数が噸 ne(linear) であるとき$f_{n}(x_{1},x_{2}, \ldots,x_{n})=u_{0}+u_{1}x_{1}+\cdots+u_{\mathfrak{n}}x_{n}$もし $(f_{n}, \nu)$ がの卿 ea 惚 a かなら, 近傍系

である.

$\nu$

$CA(f_{\mathfrak{n}}, \nu)$$f_{n}$が如 talbtk なら, 任を \Phi ne(linea りと言う.

, where $u_{i}\in Q,$ $0\leq i\leq n$ .

の任意の置換により得られる $(f_{n},\pi(\nu))$ も ffine $(hnear)$の時加 lanced と呼ばれる. $CA$ は任意
命題 5 局所関数 $f$ : $Q^{n}arrow Q$ は $|f^{-1}(a)|=|Q|^{n-1},$の有限様相が同じ数の $p\kappa images$ を持っ時 balanced と呼ばれる. 有限な加 elanced $CA$ の場合そのも balanced である.
局所関数は balanced である. $CA(f_{n}, \nu)$ が balanced なら,(fn’),$\forall a\in Q$$\pi(\nu)$$\forall\pi$

最後に近傍系の変化が性質に影響する場合をひとつ示す.

命題 6Number-conserving $ECA$ は近傍系の置換によって $number- conser\nu ing$ でなくなることがある.
証明 : 唯一の number-conserving ECA は (R184, ) とその conjugate (R226, ) である [1]. 次節で示すように (R184, ) $\cong(R172,\pi 0)$ であり,(R172, ) は numbcr$<ons\epsilon rving$ でない. 同様のことがR226 にも言える.
$\pi_{0}$$\pi_{0}$$\pi_{2}$$\pi_{0}$$\blacksquare$

52

6 CA の可逆性
この節では 3 近傍の 2 状態および 3 状態の CA について, 近傍系を変えた場合その可逆性が如何に変化するかを論ずる.
命題 76 個の可逆な $ECA$ の集合は近傍系の置換によって閉じている.
証明 :6 個の可逆な ECA が存在する :Wolffam numbers で表すと R15, R51, R85, R170, R204, R240である ([91 の 436 ページ参照). それらの局所関数を Table 1 に示す. 以下それらの 6 個の関数
を elementa’y $\kappa versiblefinctions(ERF)$ と言う. Table 1 から判るように R204 とと R15,
R170 と R85 は互いに conjugate である.

Table 1. Reversible CA with 2 states 3 neighbors$\ovalbox{\tt\small REJECT} 1ocalconfigura_{Rl511110000}tion000001010011100101110111$

R51
R85

1
1

1

$0$

$0$

$0$

1

$0$

1
1

1

$0$

$0$

$0$

1

$0$

.
1
1 R17001$
1$\ovalbox{\tt\small
REJECT}
$0$

R204
R240

$0$

$0$

$0$

$0$

1

1

$0$

$0$

$0$

$0$

$0$

$0$

1

1

1
1

1
1

さて例えば R51 の近傍系を置換すると R15 および R85 が得られる. 同様にして以下のことが判る.
$(R51,\pi_{1})\cong(R85,\pi_{0}),$$(R51,\pi_{2})\cong(R15,\pi_{0}),$$(R51,\pi_{4})\cong(R15,\pi_{0}),$$(R51,\pi_{5})\cong(R51,\pi_{0})$.

$(R51,\pi_{3})\cong(R15,\pi_{0})$同じく近傍系の置換により R204 から R170 と R240 を得る. しかしながら R170 は R51 の近傍系の置換では得られず conjugate を取って得られる$\blacksquare$

命題 8 $f_{ERF}$ を乃 ble 1 にある 2 状態 3 変数の局所関数とすると, ( $ENB$ の置換以外の) 任意の近傍系 を取っても $(f_{ERF}, \nu)$ は可逆である.
$\nu$

証明 :R15 $=x+1$ なので CA $(R15, ENB)$ は本質的に右 1 セルシフトである. 任意のゐ, $m$ について, $(R15, (-k, l, m))$ は右 セルシフトでこれらは可逆 CA である. R51 $=y+1$ および R85 $=z+1$
なので同様の理由で任意の近傍系の CA が可逆であることを証明できる R170 $=z$ , R204 $=y$ および R240 $=x$ について, 同様の結論を得る.
$l,$

$k$

$\blacksquare$

次元空間においても 2 状態 3 変数の $f_{ERF}$ は 1 セルシフトなので, 同様の命題が成り立っ. 上記の命題を纏めて次の定理を得る.

$n$$\mathbb{Z}^{n}$定理 3 任意の近傍$\nu:\{0,1,2\}arrow \mathbb{Z}^{\mathfrak{n}}$に対して $CA(Z^{\mathfrak{n}}, GF(2),$ $f_{ERF},$ ) は可逆である.
$\nu$

問題 1 この近傍系を変えた場合の可逆性保存の問題は 3 変数の場合どうなるか ?
状態で近傍系が ENB の可逆な $CA$ は I800 個存在する, page436qf[卑参考までに,3

問題 2 非可逆な $ECA$ で近傍系を変えることにより可逆になるものがあるか ?

大きさ 3 の近傍系を持つ 2 状態 CA の可逆性が近傍系の変化に耐える (定理 3) のと違って,3 状態の場合は一般に近傍系を変えると可逆性は保たれない. 次に例で示す.

53

命題 93 状態の ENB で可逆な $CA$ R270361043509 in Page 436 $of[9J$ は一般に近傍系を変えると可逆でなくなる.
証明 :R270361043509
in p.436 of [9] の局所関数を持っ CA が近傍系を $(-1,0,2)$ に変えると可逆でなくなることを証明する. ここでは 1 次元 CA の全射性 (単射性) を判定するアルゴリズムを使い ENB 以外の近傍系が扱える計算機プログラムを書いて貰ってそれを利用した.

単射性: 計算機プログラム以外に簡単な手計算で, R270361043509, $(-1,0,2))$ が異なる
様相と $Ul1\circ$ をへ写像することが判る. 従って単射でない.
$(\mathbb{Z}^{2}, GF(3)$$\overline{0}1\overline{0}$$\overline{1}0\overline{1}$全射性: チェコのブルノ大学生 David Sehnal は Mathemafica を使って R270361043509 が $(-1,0,2)$
で全射でないことを確かめた [7]. 広島大学大学院生 Naonori Tanimoto は 言語のプログラムを作
り同じことを確かめた [8]. 更に最近ドイツ・カールスルーエ大学生 Clemens Lode は 1 次元で任意の近傍系を持づ CA の全射性・単射性を判定する Java プログラムを作った [2]. これは大きさが 8以下の近傍系の全ての置換を調べることが出来る. このプログラムにより R270361043509 は近傍
系 $(-1,0,2)$ で全射でないと判定された. さらに ENB の 6 個の置換についての全射を判定したとこ
ろ,ENB $=(-1,0,1)$ と $(1, 0, -1)$ で全射でそれ以外の近傍系で全射でないと判定された.
$C$$\blacksquare$

問題 3 上記の CLode のプログラムを使って 3 状態で ENB で可逆な仰の別の $CA$ R277206003607
を ENB 以外の近傍系について判定したところ,El 留の全ての置換および $(-1,0,2),$ $(-1,0,3),$ $(-2,0,1)$など試した全ての近傍系で可逆であった. このことから R277206003607 は大きさが 3 の任意の近傍系で可逆であると予想される. 2 状態の定理 3 と同様の問題であるが異なる証明が必要であろう.

7 結言
近傍系関数による CA の新しい定義は, ” 近傍系を変える’ と言うこれまでになかった視点を明示
し,CA 研究の新しい境地を開いた. この論文で得られた結果は定理 1, 2 の様に基本的なものと 6
節の様に典型の例示に限られるが, 今後更に興味ある研究課題と結果が生まれると期待される. 幾
っかの未解決の問題を指摘したが, 付録で述べる計算機シミュレーションも示唆を与えるものである. 例えば ENB で計算万能と証明されている RI IO は ENB 以外でも計算万能か ?
逆に ENB 以
外の近傍系を許せば,R110 以外に 2 状態 3 近傍で計算万能になる CA が存在するのではないか ?
など等.

References[1] Boccara, N.: Randomized Cellular Automata, $arX/v.nljn/\theta 7\theta 2\theta 46\nu 1,2\mathfrak{w}7$.

[2] Lode, C.: Private communication, February 2007.

[3] Nishio, H.: How does the Neighborhood Affect the Global Behavior of Cellular Automata?, Pro-

ceedings $ofACRI2006,$ $eds$. $El$ Yacouybi, B. Chopard and S. Bandini, LNCS 4173, 2006.

[4] Nishio, H., Margenstem, M., von Haeseler, F.: On Algebraic Structure ofNeighborhoods of Cellu-

lar Automata-Horse Power Problem-, To appear in Fundamenta Informaticae, 2006.

[5] Nishio, H., Saito, T.: Information Dynamics ofCellular Automata I: An Algebraic Study, Funda-

menta Informaticae, 58, 2003, $399A20$ .

[6] Scheben, C.: $ht\phi://www.stud.uni- karlsmhe.de/uoz3/cgi/ma\dot{m}.cgi/$

menu$=submenuPrams\ view\neg iew/ca$.html.

54[7] Sehnal, D.: Private communication, June 2006.

[8] Tanimoto, N.: Private communication, November 2006.
[9] Wolfram, S.: A New Kind ofScience, Wolfram Media, Inc., 2002.

[10] Worsch, T., Nishio, H.: Variations on neighborhoods in CA–How to simulate different CA using
only one local rule., Eurocast2007, Workshop on CA, February 2007.

付録: Java Applet Simulator for l-Dimensional CA
我々はカールスルーエ大学情報学部学生 Christoph Scheben が作った Java Applct simulator of 1[61. これは任意の局所関数, 状態数, 近傍系, ランダムを含む任意の初期様相についてセル数が 1,000 までの cyclic boundary を持った 1 次元 CA の動きをシミュレー
トできる. この種の 任意の近傍系- シミュレーターとして初めてのものである. 大変良く出来ていて我々の研究に役立っている.

dimensional CA を利用している

以下 Rule 110 の近傍系を変えてシミュレートした 3 ケースを示す. セル数 100 で時間は 100 まで.
初期様相はランダム $Cp(0)=p(1)=0.5)$ で全てのケースに共通である.

Figure 3: Rule 110 with neighborhood $(-1,0,1)=ENB$

55

Figure 4: Rule 110 with neighborhood $(-2,0,1)$

Figure 5: Rule 110 with neighborhood $(0, -1,1)$

manuscript for’ koburoku’ of RIMS Workshop, February 19-21, 2007
(submitted May 23, 2007)