近傍系はセルオートマトンの大域行動にどう影響するか?(計算理論とアルゴリズムの新展開)

How

does

the

neighborhood

affect

the global behavior of cellular

automata?

1

近傍系はセルオートマトンの大域行動にどう影響するかウ

西尾英之助 (元京大理)

Hidenosuke Nishio

(Kyoto)

Iwakura Miyake-cho 204-1, Sakyo-ku,

606-0022

Kyoto, Japan

Email: YRA05762\copyright nifly.com

1

Introduction

Acellular automaton (CA forshort)

is

a uniformly structured information processing system defined

on a

regular discrete

space

$S$, which

is

typically presented by

a

Caylcy graph of

a

finitely generated

group.The

same

finiteautomaton(cell)isplaced at

cvery

pointof the

space.

Everycellsimultaneously

changesitsstatefollowing the local function defined

on

the neighboring cells. Theneighborhood$N$is

also spatiallyuniform.Moststudies

on

CA

assume

thestandardneighborhoods after John

von

Neumann and E. F. Moorc.

Changing theview point,however,

we

posed

an

algebraic theoryofneighborhoodsof CA forclarifying the signiflcance of the neighborhood itself,where theneighborhood$N$

can

be

an

arbitraryfinitesubset

of$S$,

see

Nishio&Margcnstcrn(2004)_{$[9, 8]$}

.

Based

on

suchasetting,

we

ask here

a

question ”How does (ordoesnot)the$\mathrm{n}\mathrm{e}\mathrm{i}\mathrm{g}\mathrm{b}\mathrm{o}\iota \mathrm{h}\infty \mathrm{d}$ affect the

globalbehavior of

a

$\mathrm{C}\mathrm{A}?$” Inthis

paper,

twoCAs

are

givensuchthatthe neighborhooddoesnot affect

the global behavior.

2

$\mathrm{C}\mathrm{e}\mathrm{U}\mathrm{p}\mathrm{l}\mathrm{a}\mathrm{r}$

Automaton

CA

A CAisdefined by

a

4-tuple$(\Gamma(S), N, Q, f)$

.

.

Cellularspace$\Gamma(S)$is

a

Cayley graph ofa flnitely generatedgroup$S=\langle G|R\rangle$withgenerators$G$ andrclators$R$

.

If$G=\{g_{1},g_{2}, \ldots,g_{f}\}$,everyelement of$S$ispresented byaword $x\in(G\cup G^{-1})^{*}$,

whcre$G^{-1}=\{g^{-1}|g\cdot g^{-1}=1, g\in G\}$

.

Thc_set$R$ofrclators iswrittcn

as

$R=\{w_{\dot{*}}=w_{*}’. |w_{i}, w_{*}’$

.

$\in(G\cup G^{-1}),i=1, \ldots, n\}$

.

(1)

For$x,y\in\Gamma(S)$,if_$y=xg$,where$g\in G\cup G^{-1}$,then

an

edgelabelled by$g$is drawn fromvcrtcx $x$tovertex$y$

.

Inthesequel$\Gamma(S)$ and$S$

are

notdistinguished.

$\circ$ Neighborhood$N=\{n_{1},n_{2}, \ldots,n_{*}\}$

is a

flnitesubset of$S$. The set ofall neighborhoods

is

denoted

byN. Thecardinality$\#(N)$is called the neighborhood

size

ofCA.Thesetofthe neighborhoods

ofsize$s$is denotedby$\mathrm{N}_{*}$

.

Foranycell$x\in S$,the information of cell_$xn$

:

reaches_$x$in

a

unit of

time.

$\bullet$ Set

ofcell

states$Q=GF(q)$ where $q=p^{n}$withprime

$p$and positive integer$n$

.

$Q=\mathrm{Z}/m\mathrm{Z}$is

alsoconsidered.

iApreliminaryvcrsionwasprcscntcd at thc 11thWor$cshoponCellular Automata at GdanskUniversity, September

_3-5.

.

Local map$f$ : $Q^{N}arrow Q$,where

an

elementof$Q^{N}$is called alocal configuration.

.

Global map$F$ : $Carrow C$, where

an

elementof$C=Q^{S}$ is called

a

_{global configuration.} $F$is

uniquelydefinedby$f$and$N$

as

follows.

$F(c)(x)=f(c(xn_{1}), c(xn_{2}),$$\cdots,c(xn_{*}))$

,

(2)

where$c(x)$isthestate ofcell$x\in S$for any$c\in C$

.

When startingwith

a

configuration$c$, thebehavior(trajectory)ofCAisgiven by

$F^{t+1}(c)=F(F^{t}(c))$forany$t\geq 0$, where$F^{0}(c)=c$

.

(3)

3

Neighborhood and Neighbors

Given

a

neighborhoodN$=\{n_{1},n_{2}, \ldots,n_{s}\}\subset S$for

a

cellular

space

$S=\langle G|R\rangle$,

we

recursivelydeflne the neighbors of$\mathrm{C}\mathrm{A}$

.

Let$p\in S$

.

(1)The 1-neighborsof$p$, denoted

as

$pN^{1}$,isthe set

$pN^{1}=\{pn_{1},pn_{2}, \ldots,pn_{*}\}$

.

(4)

(2)The $m$-neighbors of$p$,denoted

as

$pN^{m}$,

are

given

as

$pN^{m}=pN^{m-1}\cdot N,$ $m\geq 1$, (5)

where $pN^{0}=\{p\}$

.

Note that the computation

of

$P^{n}$

:

has to comply with the relations $R$ defining

$S=(G|R\rangle$

.

We

may

saythat theinformation containcd intheceUs of$pN^{m}$reachesthecell$p$after$m$timesteps. (3)$\infty$-neighborsof_$p$,denoted

as

$pN^{\infty}$,is definedby

$\mathrm{p}N^{\infty}=\bigcup_{m\approx 0}^{\infty}pN^{m}$

.

(6)

Withoutloss ofgenerality,

we

canconcentrate

on

the$m$-neighbors

ofthe

identity element 1

of

$S$,which

is called$m$-neighborsof CA and denoted by$N^{m}$

.

Then

(4)$\infty$-neighbors$\mathrm{o}\mathrm{f}1$, denoted

as

$N^{\infty}$ andcalledthe neighbors

of

_$CA$,is givenby

$N^{\infty}= \bigcup_{m=0}^{\infty}N^{m}$

.

(7)

Theintrinsic$m$-neighbors $[N^{m}]=N^{m}\backslash N^{m-1}$

are

the cells whose information

can

reach theoriginin

exactly$m$steps. Obviously,$N^{\infty}= \bigcup_{m\approx 0}^{\infty}[N^{m}]$

.

Now

we

have

an

algebraicresult,which is provedby the fact that the procedure to generate

a

subsemi-group is the

same

as

theabovementionedrecursive definitionof$N^{\infty}$

.

Proposition1

$N^{\infty}=\langle N|R\rangle_{sg}$, (8)

where $\langle N|R\rangle_{\epsilon g}$ meansthe semigmupobtained byconcatenatingthe

wordsfrom

$N$withconstraints

of

$R$

.

We also have thefollowing easilyprovedproposition.

Proposition2

$\langle N|R\rangle_{\mathit{9}}=\langle N\cup N^{-1}|R\rangle_{\epsilon g}$, (9)

where$\langle N|R\rangle_{g}$ isthe smallest subgroup$ofS$which contains$N$

.

If$N=G$, then

we

have the followinglemma

as a

corollary to Proposition2.

Lemmm1

$\langle g_{1},g_{2}, \ldots, g_{\mathrm{r}}|R\rangle_{\mathit{9}}=\langle g_{1},g_{2}, \ldots,g_{f},g_{1}^{-1},g_{2}^{-1}, \ldots,g_{f}^{-1}|R\rangle_{*g}$

.

(10)

Example: $\mathrm{Z}^{2}=\langle a,$$b|$$ab=ba)_{g}=\langle a, b, a^{-1},b^{-1}| ab=ba\rangle_{\epsilon g}$

4

Two

CAs

where

the

neighborhood does

not

affects

the global behavior.

The neighborhood isusually crucialfor the globalbehavior of

a

$\mathrm{C}\mathrm{A}$

.

For example, the Game of Life

[?] hasbeenformulated assuming binary states and theMooreneighborhoodin$\mathrm{Z}^{2}$

.

The localrule is

cleverly chosen andmany interestingbehaviors like construction- and computation-universalityhave

been proved to emerge. It would not have been

so

successful, ifit

were

defined assuming the

von

Neumann neighborhood.

Contrary tothat, in this section,

we

give two

cases

wherethe neighborhooddoesnotaffect the global behaviorof$\mathrm{C}\mathrm{A}$

.

Abriefstudy

on

the growth function of$y\mathrm{o}\mathrm{u}\mathrm{p}\mathrm{s}/\mathrm{n}\mathrm{e}\mathrm{i}\mathrm{g}\mathrm{h}\mathrm{b}\mathrm{o}\mathrm{r}\mathrm{h}\mathrm{o}\mathrm{o}\mathrm{d}\mathrm{s}$and theGarden ofEden

theorem

are

also given.

(I)Parity functionpreservesthe parityof configurations foranyneighborhood.

(II) $\mathrm{S}\mathrm{u}\dot{\mathrm{q}}\epsilon \mathrm{c}\mathrm{t}\mathrm{i}\mathrm{v}\mathrm{i}\mathrm{t}\mathrm{y}$andinjectivityoflinear CAs

are

independent from the neighborhood.

4.1

Parity function

Let$Q=\{0,1, \ldots,p-1, \ldots\}=GF(p^{n})$withprime$p$andpositive integer$n$

.

Considcr

a

CA(called

a

parity$\mathrm{C}\mathrm{A}$),whichhas

an

_$s$-arylocal fhnction calleda(generalized)parityfunction_{$f_{P,N}$}definedby

$f_{P,N}(n_{1},n_{2}, \ldots,n_{*})=\sum_{:=1}^{*}c(n:)$ mod$p$, (11)

whcre $c(n:)$ isthe stateofcell$n_{i}$

.

Notethat if$Q=\{0,1\}$then $f_{P,N}$ isthe ordinary(binary)parity

function.

The globalmap$F_{P,N}$ofaparity CA

is

defined

as

usual andalsocalled

a

(global)parity function.

Since $f_{P,N}(0, , , , 0)=0$, $0\in Q$ is a _quiescent state. A configuration $c\in Q^{S}$ is $\mathrm{c}\mathrm{a}\mathrm{U}\mathrm{e}\mathrm{d}$

fnite

if $\#\{i|c(i)\neq 0, i\in S\}<\infty$

.

For

a

finite configuration$c$,afinitesubset$\{i|c(i)\neq 0, i\in S\}$of$S$is

Sincethe finiteness ofconfigurations ispreservedby$F_{P,N}$,in thesequel

we

treat onlyfinite configura-tions.

The(generalized)parity$P(c)$of

a

configuration$c$is definedby

$P(c)= \sum_{x\in S}c(x)$ modp. (12)

Then

we

havethe following theorem.

Theorem1

$P(F_{P,N}(c))=P(c),$ $c\in Q^{S}$, ₍₁₃₎

fand

only$ifN\in \mathrm{N}_{s}$, where$s=kp+1,$$k\geq 0$

.

Proof.

$P(F_{P,N}(c))$ $=$

$\sum_{x\in S}F_{P,N}(c)(x_{\text{ノ}^{}1}=\sum_{x\in S}f_{P,N}(xn_{1}, \ldots, xn_{*})$ (14)

$=$ $\sum_{x\in S}\sum_{1=1}^{l}c(xn:)=\sum_{i=1}^{*}\sum_{x\in S}c(xn_{i})$

.

(15)

We notehere, sincethe neighborhoodisspatiallyuniform,

$\sum_{x\epsilon S}c(xn:)=\sum_{x\in S}c(x)$

,

forany$1\leq i\leq s$

.

(16)

Then,if$s=kp+1$, from(15)

we

have

$P(F_{P,N}(c))= \sum_{1=1}^{*}a\sum_{e\in S}c(xn_{j})=\sum_{x\in S}c(x)=P(c)$

.

(17)

For the necessity of condition $s=kp+1$,

we

can

consider

a

binary parity CA $(p=2)$ having

a

neighborhood ofsize $s=2$

.

Such

a

CAmaps all configurations into those of parity$0$ anddoes not

preservethe Parity. $\blacksquare$

Note that

a

binaryparityfunctionis notnumber conserving.

Example1 Consider binaryparityCAs in $\mathrm{Z}=\langle a|\emptyset\rangle$ with a neighborhood

of

size 3 such as _{$N_{3}=$}

$\{a^{-1},1, a\},$ $N_{3}’=\{a^{-2},1, a^{2}\}$ and$N_{3}’’=\{0, a, a^{2}\}$

.

$n_{\varphi preserves}$ theparity. but a $CA$ with a

neighborhood

_ofsize

2$N_{2}=\{1, a\}$doesnot. The theorem

holdsforfinite

spaceslike$\mathrm{Z}_{m}=\langle a|a^{m}=1\rangle$

.

4.2 Linear

$\mathrm{C}\mathrm{A}$

over

$\mathrm{Z}_{m}$

Weconsiderthelinearlocalfunction$f$of arity$s$

over

$\mathrm{Z}_{m}=\mathbb{Z}/m\mathrm{Z}$;

$f(n_{1}, n_{2}, \ldots, n_{*})=\sum_{:=1}^{*}$aini, $a_{\dot{*}}\in \mathrm{Z}_{m}$

,

mod_$m$

.

(18)

Then

we

have the following theorem.

Theorem2

_Ifthe

growthfunction

_of

$S$is$amenable^{2}$,then thesurjectivityand theinjectivity_$ofa$ linear

$C\Lambda$

are

independentfrom the neighborhood.

2Agrowthfunctioniscalledamenableifit isless than cxponential.$\mathrm{C}\mathrm{o}\mathrm{n}\alpha \mathrm{a}\mathrm{r}\mathrm{y}$,aCAcould be calledamenable,wheneverthe

Proof.

For such

a

CAthat theGarden of Eden theoremholds, the theorem is proved owing to the fol-lowingtwotheorems given for$\mathbb{Z}^{2}(\mathbb{Z}^{d})$ by Ito&Osato&Nasu (1983) [3],which completelycharacterize

the $\mathrm{s}\dot{\mathrm{r}}\mathrm{e}\mathrm{c}\mathrm{t}\mathrm{i}\mathrm{v}\mathrm{i}\mathrm{t}\mathrm{y}$ and the injectivity of

a

linearCA

over

$\mathbb{Z}_{m}$, rcspectively, interms of the coefficients

$a_{1},$ $a_{2},$$\cdots,$$a_{s}$and the prime factors of$m$. Note thattheir proofs

assune

theresults of Richardson$(1972)$

[11],which

are

based

on

the Garden ofEden theorem for$\mathbb{Z}^{d}$

.

Obviously, the characterization is

inde-pendentfrom the neighborhood. Forotherspaceswhere the Garden ofEdentheoremdoesnothold, $\mathrm{s}\mathrm{e}\mathrm{e}-$

adiscussion below.

Theorem3(Theorem1of[3]) A linear$CA$ over$\mathbb{Z}_{m}$ is surjective

ifand

only ifanyprime

factor of

$m$

doesnotdivide all

_of

the

_coefficients

$a_{1},$ $a_{2},$$\cdots,$$a_{s}$

.

Theorem4(Theorem2of[3]) A linear$CA$

over

$\mathrm{Z}_{m}$ is injective

if

andonly

iffor

eachprime

factor

_$p$ $ofm$thereexists

a

unique

coefficient

$a_{g’}$ such that$p$

I

$a_{j}$ and$p|a$

:

for

$i\neq j$.

4.3

Growth

Function

of Groups

and

Netghborhoods

The growth

_function

$\gamma_{S}$ of

a

finitelygenerated discretegroup$S=\langle G|R\rangle$ is deflnedby

means

of the

cardinalityofthe ball ofradius$n$

.

Thatis

$\gamma_{S}(n)=\#\{w||w|\leq n, w\in S\}$

.

(19) Similarly

we

define the growthfinction$\delta_{(N,S)}$of neighborhood$N$in$S$ofaCA by

$\delta_{(N,S)}(m)=\#\{w|w\in N^{m}\}$, (20)

where$N^{m}$isthesetof_$m$-neighbors. Obviously, if$N$happensto be equal to$G\cup G^{-1}$, then_{$\delta_{(N,S)}(m)=$} $\gamma s(m)$

.

The following definition of the growth rate ofintegerfunctions (groups)isduetoL.Babai(1997) [1].

Two monotone non-decreasing functions$f_{1},$$f_{2}$ : $\mathrm{N}arrow \mathrm{N}$

are

said tobe equivalent

$(f_{1}\sim f_{2})$,if thereexistconstants$c_{1},$ $c_{2}$, Ci,$C_{2},$$n_{0}>0$such that for all$n\geq n_{0}$,

Ci

$f_{1}$(ci$n$) $\leq f_{2}(n)\leq C_{2}f_{1}(c_{2}n)$

.

(21)

The$\mathrm{r}\mathrm{e}\mathrm{l}\mathrm{a}\mathrm{t}\mathrm{i}\mathrm{o}\mathrm{n}\sim \mathrm{i}\mathrm{s}$ anequivalence relation.

An$\mathrm{o}\mathrm{r}\mathrm{d}\mathrm{e}\mathrm{r}_{\sim}\prec$ isintroducedamongtheequivalenceclasses;Let

$[f_{1}]$ and$[f_{2}]$be the equivalenceclassestowhich$f_{1}$ and$f_{2}$belong,respectively. Then define$[f_{1}]\prec\sim[f_{2}]$

if$Cf_{1}(cn)\leq f_{2}(n)$forconstants$C,$$c,$$n_{0}\geq 0$and forall$n\geq n_{0}$

.

Examples;$n^{2}\# n^{3}([n^{2}1_{\theta}^{\prec}[n^{3}]),$$n^{a}\# b^{n}([a^{n}]_{\alpha\prime}\prec[n^{b}])$ and$a^{n}\sim b^{n}$ for any_{$n,$ $a,$} $b\geq 1$

.

The growth rate$[\gamma_{S}]$of

a

group$S$is

an

equivalenceclasstowhich$\gamma_{S}$belongs.Notethatin the

$\mathrm{l}\mathrm{i}\mathrm{t}\alpha \mathrm{a}\mathrm{t}\mathrm{u}\mathrm{r}\mathrm{e}$

thegrowthfunction often

means

the growth rate.

The growth rate $[\delta_{(N,S)}]$ of

a

neighborhood$N\subset S$is similarlydeflned. Then

we

have the following

thcorem.

Theorem5 Foracellularspace$S=\langle G|R\rangle_{g}$ and any neighborhood$N\subset S$,

$[\delta_{(N,S)}]\prec[\sim\gamma s]$, (22)

4.4

Garden of Eden theorem

TheGarden

_ofEden

$(GOE)$theorem isoriginallyprovedfor$\mathbb{Z}^{2}$by

E.Moore(1962) [6]andJ.Myhi11(1963)[7].

Itisthe earliestmathematicalresultproved about$\mathrm{C}\mathrm{A}$.

Deflnition 1 $\Lambda$

finite

configuration$\Phi anern$) iscalled

a

Garden

ofuen

$(GOE)$,

if

itisnot intheimage

of

$F$ (A$GOE$has not an_ancestor). Twodistinctpatterns$p_{1}andp_{2}$are calledmutually erasable

iftwo

configurations$c_{1},$ $c_{2}$, whichcontain$P1$ and$p_{2}$

.

respectively andcoincide outside

of

thesupports

of

$p_{1}$

$andp_{2}$,

are

mappedtothe

same

configuration

Theorem 6(Moore)

Ifthere

aremutuallyerasable patterns, then thereareGOEpattems. Theorem

7

(MyhlU)

_If

thereare$GOE$patterns, thenthere

are

mutuallyerasablepatterns.

If thereis

no

GOEpattems then$F$issurjectiveand ifthereis

no

mutually erasablepattems then$F$is

injectivewhenit is restrictedto the$\mathrm{f}\mathrm{i}\dot{\mathrm{a}}\mathrm{t}\mathrm{e}$configurations. Therefore these theoremstogetherclaim the

following.

Theorem8(GOE theorem) $F$issurjective

ifand

only

ifF

isinjectivewhenitisrestrictedtothe

finite

configurations.

Idea of proof ofTheorem6: Let$\#(c(N^{m}))$bethecardinality ofdifferentpattemscontainedby cells

in $m$-neighbors $N^{m}$

.

For $S=\mathrm{Z}^{2}$ and Moore neighborhood, if there

are

mutuallycrasable patterns,

then$\#(c(N^{m-1}))$ becomesgreaterthan$\#(c(N^{m}))$when$m$becomes large enough, which implies the

existenceof GOE patterns. This proof is based onthefact that the growth

_of

the boundary(intrinsic

neighbors) is not too fast. Onthe otherhand, in

case

of

a

Cayleygraph offree

group

$\langle a, b|\emptyset\rangle$ the

boundarygrowsexponentially.

Takinginto account such

an

observation,

group

theorists reveal that theGOEtheoremholdsfor

groups

of

polynomialandsubexponcntial$y\mathrm{o}\mathrm{w}\mathrm{t}\mathrm{h}^{3}$,butdoesnotforexponential growth,

see

Machi&Mignosi(1993)

[5] and Gromov(1999) [2]. Note that

group

theoristsusuallydiscuss the GOE theorem assuming the

generatorsofthegroup

as

the neighborhood. This factis

one

ofthe

reasons

why

we

are

interested in the

growthfunctionofneighborhoodsingeneral.

The dualhyperbolic plane

{4,

5}

of the pentagrid

{5,

4}

allows

a

Cayleygraph presentationof

a

group

of exponential growth [10] and therefore the above discussion

on

linear CAs does not apply

as

it is.

However,therecould be another proof for Theorem2whichdoes not

assume

theGOEtheorcm.

Many thanks

arc

due to MauriceMargenstem and Friedrich

von

Haeseler for their discussion

on

the

growthfmction ofgroups and the hyperbolic planeconcerningthejoint work[10]andtoThomas Worsch

for his cooperation.

References

[1] Babai,L.: The growthrateofvertex-tansitiveplaner graphs, 8th Annual ACM-SuMSymposium

on

Discrete Algorithm,

1997.

[2] Gromov,M.:

_EndomoPhisms

ofsymbolic algebraic varieties,J. Eur.Math.Soc.,1, 1999,

109-197.

[3] Ito,M., Osato, N., Nasu,M.: LinearCellular Automata

over

$\mathrm{Z}(\mathrm{m})$, J. Comput. Syst. Sci.,27(1),

1983, 125-140.

$\overline{\mathrm{A}\mathrm{o}\mathrm{u}\mathrm{b}\alpha \mathrm{p}\mathrm{o}\mathrm{n}\epsilon \mathrm{n}\mathrm{t}\mathrm{i}\mathrm{a}\mathrm{l}g\mathrm{o}\mathrm{w}\mathrm{t}\mathrm{h}\mathrm{i}\S \mathrm{f}\mathrm{a}\mathrm{s}\mathrm{t}\mathrm{e}\mathrm{r}},$

[4] Knuth,D. E.: Bigomicronand bigomegaand bigtheta, SIGACTNews,April-June 1976, 1976,

18-24.

[5] Machi, A.,Mignosi, F.: Garden of Eden Configurations forCellularAutomata

on

Cayley Graphs

of Groups., SIAMJ. DiscreteMath.,6(1), 1993,44-56.

[6] Moore, E. F.: Machine models of self-reproducution, Proc. SymposiuminAppliedMathematics,

14, 1962.

[7] Myhill, J.: The

converse

toMoore’s Garden-of-Edentheorem, Proc.Amer.Math. Soc., 14, 1963,

685-686.

[8] Nishio,H.,Margenstern, M.: An algebraic AnalysisofNeighborhoodsofCellularAutomata,

Sub-mittedtoJUCS,2004.

[9] Nishio,H.,Margenstern, M.: An algebraic AnalysisofNeighborhoodsofCellularAutomata,

Tech-nicalReport (kokyuroku) vol. 1375, RIMS, Kyoto University, May 2004, Proceedings of LA

Symposium, Feb.2004.

[10] Nishio, H.,Margenstem,M.,

von

Haeseler,F.: On Algebraic Structure ofNeigborhoodsof

Cellu-larAutomata-Horse PowerProblem-, Submitted to FundamentaInformaticae,2005.

[11] Richardson,D.: Tcssellations withLocalTransformations.,J. Comput. Syst.Sci.,6(5), 1972,