数理解析研究所講究録
第 1604 巻 2008 年 104-109

104

セルオートマトンの局所構造
Local Structures of CA:
Equivalence, Isomorphism and Similarity
西尾英之助 (元・京大理)Hidenosuke Nishio (ex. Kyoto Univ.) 1
email: YRA05762@nifty.com

andトーマス・ヴォルシュ (カールスルーエ大情報)
Thomas Worsch (Univ. of Karlsruhe)email: worsch@ira.uka.deAbstract
Of the definition of a cellular automaton, we focus on the local ffinction and the neighborhood
called the local structure and consider three kinds ofthe sameness ofCA: equivalence, isomorphism and similarity. After giving general descriptions of equivalence, isomorphism and similarity,
classification of CA is discussed in the context of changing the neighborhood.
$(f, \iota$ ノ $)$1

Definitions

1.1

Cellular Automaton CA $(S, Q,f, \nu)$.
.
.

A cellular automaton (CA for short) is defined by a 4-tuple $(S, Q, f, \nu)$ :.

$S$: a discrete cellular space such as$\mathbb{Z}^{(l}$, hyperbolic space...

$Q$: a finite set of the states of each cell.

$f$: $Q^{n}arrow Q$ : a local function in $n\geq 1$ variables.

$\nu$: an injective map fromvariable of$f$

to$\nu(i)$$\{1, \ldots, r\iota\}$. That is,

to$S$, called a neighborhoodfunction, which connects the i-th$(\nu(1), \ldots, \nu(n))$

becomes a neighborhood of size .
$n$In order to study effects of changing the neighborhood (function), we define the pair $(f, \nu)$ as a local
structure of CA and investigate its mathematical properties.

1.2

Local Structure $(f, \nu)$In this paper we assume that $S$ is a d-dimensional Euclidean grid$+$.

$\mathbb{Z}^{d}(d\geq 1)$

with the additive operator

Definition 1 [neighborhood]
For $n\in N$ , a neighborhood (function) is a mapping$|$

corresponding author

$\nu$

:

$\mathbb{N}_{n}arrow \mathbb{Z}^{d}$, where $N_{n}=\{1,2, \ldots, n\}$ .

105

$n$

This can equivalently be seen as a list.

The set of all neighborhoods ofsize

$n$

$\nu$

with$n$components;

will be denoted as$N_{n}$$(\nu_{1}, \ldots, \nu_{n})$, where $\nu_{i}=\nu(i),$ $1\leq i\leq$.

Definition 2 [local structure, reduced]
A pair $(f, \nu)$ of a localfunction $f$ : $Q^{n}arrow Q$ and a neighborhood $\nu\in N_{n}$ is called a local structure.
the arity ofthe local structure.

We call.
.

$n$

A local structure is called reduced, if and only if the following conditions are$f$

depends on all arguments.

$\nu$

is $injecti\nu e,$ $i.e$.

$\nu_{i}\neq\nu_{j}$forfulfilled.

$\cdot$in the list of neighborhood .

$i\neq j$$\nu$

Each local $s_{d}tructure$ induces the global function $F$ :or the dynamics of CA. Everyelement $c\in Q^{Z}$ is called a (global) configuration. For any global configuration
and,let $c(x)$ be the state of cell in . Then $F$ is given by $F(c)(x)=f(c(x+\nu_{1}), c(x+\nu_{2}), \ldots, c(x+\nu_{n}))$.
$Q^{Z^{d}}arrow Q^{Z^{d}}$$c\in Q^{Z^{d}}$

$x$

1.3

$x\in \mathbb{Z}^{d}$$c$

Equivalence

Definition 3 [equivalenceJ
TWo local structures $(f, \nu)$ and $(f’, \nu’)$ are called equivalent
if and only if they induce the sameglobalfunction. In that case we sometimes write $(f, \nu)\approx(f’, \nu‘)$ ,Lemma 1
For each local structure $(f, \nu)$ there is an equivalent reduced local structure $(f’, \nu‘)$ .
Note that for a local structure, the equivalent reduced local structure is not unique.
As a simple
example consider the local function $f(x_{1}, x_{2})$ over $GF(2)$ : $(x_{1}, x_{2})\mapsto x_{1}+X_{2}$ (mod.2).
Since theorder of the arguments
does not matter for the value $f(x_{1}, x_{2})$ , the local structures $(f, (0,1))$ and$(f, (1,0))$ are equivalent. At the same time both are
obviously reduced.
$x_{i}$

1.4

Permutation of Local Structure

Deflnition 4 [permutafion of local structure]
Let denote a permutation of the numbers in.

$\pi$.

For a neighborhood
For an n-tuple$\nu$, denote by$\ell\in Q^{7t}$, denote by$\nu^{\pi}$$\ell^{\pi}$$\mathbb{N}_{n}$.

the neighborhood defined by$p$$\ln$.

the permutation of such that $\ell^{\pi}(i)=\ell(\pi(i))$ for $1\leq i\leq n$.

For a local function: $Q^{n}arrow Q$ , denote by$f^{\pi}(P)=f(\ell^{\pi})$
all.
for
$f$

$\nu_{\pi(i)}^{\pi}=\nu_{i}$$\ell$$f^{\pi}$the local function$f^{\pi}$: $Q^{n}arrow Q$ such thatthe first part of the definition we have preferred the given specification to
the equally possible, because the former leads to a slightly simpler formulationof the following lemma.

$\nu_{i}^{\pi}=\nu_{\pi(i)}$1062Results

Some basic properties ofthe equivalence of local structures are given without proofs, for which we referto [1].

Lemma 2$(f, \nu)$ andare equivalent for any permutation .

$(f^{\pi}, \nu^{\pi})$$\pi$

We are now going to show that for reduced local structures, the relationship via a permutation is the
only possibility to get equivalence.

Lemma 3
If $(f, \nu)$ and $(f’, \nu’)$ are two reduced local structures which are equivalent, then there is a permutationsuch ihat.
$\nu^{\pi}=\nu’$$\pi$Lemma 4If $(f)\nu)$ and $(f’, \nu’)$ are two reduced local struciures which are equivalent, then there is a permutationsuch that $(f^{\pi}, \nu^{\pi})=(f^{l}, \nu’)$ .

$\pi$

By choosing different neighborhoods which are not permutations of each other, one immediately
gets the following corollary, which claims the same thing as Theorem 1 of H.Nishio, MCU2007 [2]:By changing the neighborhoodfunction
infinitely many different global $CA$ functions are induced byany single local function $f_{3}(x, y, z)$ which is not constant. Proof was given for l-dimensional CA byconcretely showing biinfinite words which correspond to different neighborhoods.
$\nu_{2}$Corollary 1
For each reduced non-constant localfunction , there are infinitely many reduced neighborhoods
that the local structures $(f, \nu)$ induce pairwise different global $CA$ functions.
$f$

3$\nu$, suchIsomorphism and similarity

There could be several definitions of the sameness of a certain mathematical object like the local structure. In the above sections, we defined and investigated the most naive notion of equivalence as such.
In the following, based upon those results on the equivalence, we will introduce two other notions of
isomorphism and similarity, which are weoker notions than equivalence.

3.1

Isomorphism

In the same space $S$ , consider two CA A and

where$f_{A}$

and$f_{fj}$$B$having different local structures:andare defined on possibly different domains;$f$$Q_{A}^{n}arrow Q_{\Lambda}$$(f_{4}, \nu_{A})$$f_{f3}$:and$(f_{B}, \nu_{B})$$Q_{B}^{n’}arrow Q_{B}$.

,Deflnition 5then we can consider a bijection : $Q_{A}arrow Q_{B}$ . Two $CA$ and are called isomorphic
denoied by, ifand only if the following diagram commutes
for all global configurations.

$If|Q_{A}|=|Q_{B}|$ ,under$\varphi$$A$$\varphi$$B$$A\sim\prime B$

Note that bijection$\varphi$naturally extends to$\varphi$:$Q_{A}^{Z^{d}}arrow Q_{B}^{Z^{d}}$$c_{A}$.

$\underline{\varphi}arrow c_{B}$$F_{A}\downarrow$(1)$\downarrow F_{B}$$c_{A}’arrow^{\varphi}c_{B}’$where$c_{A}^{l}(cB)$

is a global configuration of $A(B)$ and$\mathfrak{c}_{A}’(c_{B}’)$is the next configuration of $cA(cB)$ .

107

Both equivalence and isomorphism oflocal structures are evidently equivalence relations.

From the definitions of equivalence and isomorphism among local structures, we have

Lemma 5

If$(f_{A}, \nu_{A})\approx(f_{B}, \nu_{B})$, then $(f_{A}, \nu_{A})$or$(f_{B}, \nu_{B})$for any$\varphi$. The converse is not always true.

Example: We consider 6 Elementary CA which are show to be reversible in page 436 of [3]. Rules
15, 51 and 85 are equivalent (and isomorphic) each other. Rules 170, 204 and 240 are equivalent (andisomorphic). However, rules 15 and 240 (resp. 51 and 204, 85 and 170) are not $equi\nu alent$ but
isomorphic
under : $0\mapsto 1,1\mapsto 0$ . Summing up those 6 Elementary reversible CA are all isomorphic.
$\varphi$

For the isomorphism too, the following lemma is proved in the same manner as Lemma 3.
Lemma 6 (Lemma 3’)
andare two reduced local structures which areIf; $Q_{A}arrow Q_{B}$ , then there is a permutationsuch that.
$(f_{A}, \nu_{A})$$(f_{B}, \nu_{B})$$\varphi$$\pi$$\varphi$-isomorphic under a bijection$\nu_{\Lambda}^{\pi}=\nu_{B}$Proof

Assume that there is an which does not appear in
but does appear in, say at position . Since
is reduced,
does depend on its i-th argument and there are two configurations,
andwhich do only differ at cell , such that $F(c_{4})(0)\neq F(\overline{c_{A}})(0)$ .
$x$$(f_{A}, \nu_{A})$$\nu_{B}$$i$$\nu_{A}$$f_{A}$$c_{A}$$\overline{r_{A}}$

$x$

Since
does not contain , clearly
that $F_{A}(c_{A})(0)=F_{B}(\varphi(C_{A))(0)}$ and simultaneously
and $F_{A}\neq F_{B}$ .
$\nu B$$F_{B}(\varphi(c_{A}))(0)=F_{B}(\overline{\varphi(c_{4\sim})})(0)$

$x$

.

$1t$

is therefore impossible$F_{A}(\overline{c_{4}})(0)=F_{B}(\overline{\varphi(c_{A})})(0)$. Hence$F_{A}(c_{A})\neq$$F_{B}^{\backslash }(\varphi(cA))$

3.2
Let

$\blacksquare$

Similarity
be a finite subset ofsuch that $|\sigma|=n$ and $0\in\sigma$ , i.e. $\sigma=\{0,j_{2},.;_{3}, \ldots,j_{n}\},j_{i}\in$consists of the members from , then we say that is a support of andwrite support $(\nu)=\sigma$ . For instance, if $\nu=(-1,0,1)$ , then $\sigma(\nu)=\{0, -1,1\}$ .
Permutation of aneighborhood does not change the support. That is, if $\nu=(-1,0,1)$ , then $\sigma(\nu^{\pi_{i}})=\{0, -1,1\},$ $0\leq$$i\leq 5$ .
$S$$\sigma\subset S$. If a neighborhood

$S$

$\nu$

$\sigma$$\sigma$$\nu$

Deflnition 6 We say that and $f’$ are similar on , if and only if there are neighborhoods andandan isomorphism such that. If and $f’$ are similar on some support , then we calland $f’$ similar and write.
$f$$\sigma$$\nu$$\varphi$$(f_{7}\nu)\sim\varphi(f’, \nu’)$$f$$\sigma$$\nu’$$f$$f_{\wedge}\vee f’$

The relation$\wedge\vee$

is obviously an equivalence relation and the following lemma holds.

Lemma 7 If $(f, \nu)$ and $(f’, \nu’)$ are $equi\nu alent$ or isomorphic, then

4$f$

and $f’$ are similar

Classification of CA

Classification is a typical problem in the CA study and there are several stand points of classification.
For example, CA are classified by the complexity of dynamical behavior –fixed points,
limit cycles,
chaotic and so on, see Chapter 8 of [4] for old references and Wolfram’s classification of ECA
into fourclasses according the complexity ofglobal dynamics [3].

108

On the other hand, L. Chua et. al. [5] as well as uan et.al. [6] focuses on certain geometricalsymmetries ofthe unit cubes corresponding to local functions of ECA and defines the global $equi\nu alence$
which classifies 256 ECA into 88 classes. For instance, it classifies rule 15 and 85 as globally equivalent
but not 51. This is because our isomorphism considers all permutations of neighborhoods, while theirglobal equivalence does not.
$G$

Note that those past papers assume a standard neighborhood like von Neumann neighborhood andclassify the local functions. We will investigate, however, the classification problem from a different
point of view–by changing the neighborhood. As discussed above, without loss of generality we shallrestrict ourselves to the reduced local structures.

The decision problems of equivalence, isomorphism and similarity of local structures are evidently
decidable.

4.1

Classification by similarity

We will only state two unsolved problems conceming with similarity. Let denote the set of all local
functions of arity $n\geq 1$ by .
$\mathcal{F}_{n}$Problems 1: Classify
to$\wedge\vee$.

$S_{n}$

with respect to$\vee-\cdot$

How many classes are there?

Specifically, classify the set ofall (256) ELF with respect

Problems 2: Suppose that $f$ and $f’$ are similar on . Is there any subset
such that $f$ and $f’$? Are there local functions and $f’$ such that they are similar on every subset of ?
$\sigma’\neq\sigma$$\sigma$are similar on

4.2$\sigma’$

$f$

$S$

Classification of reversible, injective and surjective CAFirst we consider reversible 6 Elementary CA, see page 436 of [3].

000 001 010 011
R151111
R5111
$0$

$0$

100

101

110

$0$

$0$

$0$

$0$

1

1

$0$

$0$

111

$\frac{R8510101010}{R17001010101}$
R204
R240

$0$

$0$

1

1$0$

$0$

$0$

$0$

$0$

$0$

1

11
111

Rules 15, 51 and 85 are equivalent (and isomorphic) each other. Rules 170, 204 and 240 are equivalent (and isomorphic). However, rules 15 and 240 (resp. 51 and 204, 85 and 170) are not $equi\nu alent$ but
isomorphic under : $0\mapsto 1,1\mapsto 0$ . Summing up, all reversible ECA are isomorphic.
$\varphi$

If $|Q|=3$ , reversibility is not preserved from changing the neighborhood. See Proposition 9. in [2].

Characterization or classification of local structures which induce not injective and surjective CA isan interesting problem, but we have not yet obtained definite results. As a computational example, wecan tell something about rule 30 and 6 permutations of $\pi_{0}=(-1,0\rangle 1)$ , see below. By using a Java
program catest, we see that 6local strucrures $\{(30, \pi_{i}), i=0, ..:5\}$ are all not injective, while$(3O, \pi_{0})$and other 3 ones are surjective but 30,$($$\pi\ovalbox{\tt\small REJECT})$and 30,$($$\pi_{3})$are not.

109

6 permutations of $(-1,0,1)$$\pi_{0}=(-1,0_{7}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)$ .

5Concluding remarks

In this paper we considered three notions of the sameness oflocal structures of CA. Classification ofCA
was discussed from the point of view of changing the neighborhood. One of other possible definitionsof similarity will be strong similarity: If $f$ andare similar on every support, then we call $f$ and $f’$strongly similar. Strong similarity is stronger than equivalence, i.e. there could be equivalent functions$f$ and $f’$ onsome support, which are not equivalent on other supports. Then we have a problem: Are
there nontrivial strongly similar local structures?
$f^{l}$References[1] Nishio, H., Worsch, T.:

Local strucure of cellular automata. Technical Report (kokyuroku) vol.
1599, RIMS, Kyoto University (June 2008)[2] Nishio, H.: Changing the neighborhood of cellular automata. In:

Proceedings of MCU2007, eds. J.

Durand-Lose and M. Margenstem. Volume LNCS 4664. (2007) 255-266[3] Wolfram, S.: A New Kind of Science. Wolfram Media, Inc. (2002)[4] Garzon, M.: Models of Massive Parallelism, Analysis of
Cellular Automata and Neural Networks.
Springer (] 995)
[5] Chua, L., Sbitnev, V., Yoon, S.: A nonlinear dynmics perspectiveof Wolfram’s new kind of science.
Part IlI: Predicting the unpredictable. Int. Joumal of Bifurcation and Chaos 14 (2004)

3689-3820[6] Guan, J., Shen, S., Tang, C., Chen, F.: Extending Chua’s global

equivalence theorem on Wolfram’s
New Kind of Science. Int. Joumal of Bifurcation and Chaos 17 (2007)

4245-4259

manuscript for RIMS k\^oky\^uroku (May 19, 2008)