数理解析研究所講究録 1244 巻 2002 年 69-74

69
Discrete Dynamics on Cellular Automata

永井喜則 (Yoshinori NAGAI) , and

Ted MADDESS *国士舘大学情報科学センター 及 政経学部 (Center for Information Science, md

Faculty of Political Science & Economy, Kokushikan University) and *VisualSciences, Research School of Biological Sciences, Australian National University.

Cellular automata (CA) have many applications and give aconvenientscheme of discretized modeling of asystem [1]. There are several type of rule. Theconstruction methods such as filteredor Wolfram type
difference these rule constructions seems to be the same when we see ageneral, namely, neighbors and states (or levels). However, filtered CA
class ofhas adifferent feature from CA with other rule construction methods, because
the filtered CA uses semi-infinite neighbors usually.
Here we develop Wolfram type CA to the CA of neighbors and levels
which denoted by CALn. We show amethod how organize rules for neighbor and,level. We recognized what kind of nature gives fractal feature ofthat is how comes self-similarity out on CA rule structures. We also know thatCA properly has the rule-dynamical property. Note that rule-dynamics wasproposed by Aizawa [4]. In this note, we briefly sketch these subjects and give ascope to see adiscrete world of celular automata.
$\mathrm{C}\mathrm{A}[1,3]$$\mathrm{C}\mathrm{A}[1,2]$$\mathrm{C}\mathrm{A}$$\mathrm{L}$$\mathrm{L}$$\mathrm{n}$$\mathrm{L}$$\mathrm{n}$$\mathrm{n}$$\mathrm{L}$$\mathrm{C}\mathrm{A}(\mathrm{C}\mathrm{A}_{\mathrm{n}}^{\mathrm{L}})$$\mathrm{C}\mathrm{A}$From TwO-Level CA to Multi-Level CAHere we explain wolfram type CA and show ageneral scheme of. asimple Wolfram type CA is aone-dimensional CA is consisting of cells each ofwhich has two states and three neighbor relation to determine the state of acellat next time step. An example is shown as foUow:$\mathrm{C}\mathrm{A}$$\mathrm{N}$ooooooooooooooooo
ooooooooooooooooo(cell states at time ),$\mathrm{t}$(cell states at time$\mathrm{t}+1$)

70
The temporal development of each cell state is governed by following equation,Si(t)$=\mathrm{F}$($\mathrm{S}\mathrm{i}\cdot 1(\mathrm{t})$, Si(t),$\mathrm{S}\mathrm{i}+1(\mathrm{t})$),where Si(t) denotes i-th cell state, takes one of two values such as {0,1}, at time t,and F(...) is amapping function called “mle”depicted as below.
ii-lo$\mathrm{i}+1$I

at time00$\mathrm{t}$$\mathrm{F}$at time$\mathrm{o}$$\mathrm{t}+1$I(two levels and threeknown [3], the number of rules (mappings) forAsneighbors) is $2^{8}=256$ .
The general class of CA can obtain simply by extending neighbors and levels.
The extended scheme is explained as foUows:$\mathrm{C}\mathrm{A}^{2}3$$\mathrm{w}\mathrm{e}\mathrm{U}$Si(t)$\mathrm{i}$$\ldots \mathrm{o}\circ\circ\circ\circ\ldots \mathrm{n}$Ineighbors$\mathrm{F}$

1oSi(t)S2,
where Si(t) takes one of L levels, namely,
development of Si(t) is given by the recurrence equation, i.e.,$\mathrm{S}\mathrm{i}(\mathrm{t})_{\in}\{\mathrm{s}1,$Si(t)$\mathrm{s}_{3},\ldots,\mathrm{s}_{\mathrm{L}}\}$$=\mathrm{F}(\mathrm{S}_{\mathrm{i}\cdot \mathrm{n}/2}(\mathrm{t}), \ldots,\mathrm{S}_{\mathrm{i}\cdot 1}(\mathrm{t}), \mathrm{S}_{\mathrm{i}}(\mathrm{t}), \mathrm{S}_{\mathrm{i}+1}(\mathrm{t}), \ldots, \mathrm{S}_{\mathrm{i}+\mathrm{n}l2}(\mathrm{t}))$and the temporal.

Notice that ... means rules (i.e., mapPings), and is assumed to be an oddinteger. We can know any case of temporal patterns of 1-D cell array if we get the.
manner to construct entire rules for
To apply for the celular automata modelng of agiven system, an importan$\mathrm{F}($$)$$\mathrm{n}$$\mathrm{C}\mathrm{A}_{\mathrm{n}}^{\mathrm{L}}$$\mathrm{t}$71matter is what kind of spatial relation between cells must be introduced. Leveland neighbor are also required to make an appropriate model on. Usually,
there are several rules that give the same temporal development of cell states$\mathrm{C}\mathrm{A}$which is called pattern dynamics.
class of rules on L-level and n-neighbor CA
exists to realize the same pattern dynamics.
Rule Description of CALn
Now we consider amethod to construct the rules for general type. Let
a CA system has L-levels and be denoted by {si, ,}. Here we show aconstruction method to use arecurrence relation. We start from one-variable
functions and organize arecurrence relation by use of point functions shown$\mathrm{C}\mathrm{A}$$\mathrm{s}2$$\mathrm{s}_{3},\ldots,\mathrm{s}_{\mathrm{L}}$below. There are numbers of one-variable functions {,,,,. We tabulate the Boolean like relation of levels (or states) for theseone-variable functions in Table I.
$\mathrm{L}^{\mathrm{L}}$$\mathrm{g}1(\mathrm{X})$$\mathrm{g}2(\mathrm{X})$$\mathrm{g}3(\mathrm{X})$$\ldots$$\mathrm{g}_{\mathrm{L}^{\mathrm{L}}}(\mathrm{X})\}$

Whenever we introduce afunction for every level sj defined by
1for$\mathrm{I}\mathrm{s}_{\mathrm{j}}(\mathrm{X})=$$\mathrm{X}=\mathrm{s}_{\mathrm{j}}$$\{$0Otherwise

72
we can construct any rule for any neighbors. We call the above function “point, namely, {Isi, Is2, Iss,,function”. There exist point functions for L-level
ISL}. We can concrete the form of point functions by atypical description forlevel sj as below.
$\mathrm{C}\mathrm{A}$$\mathrm{L}$$\ldots$Isj(X)$=\mathrm{X}/\mathrm{S}\mathrm{j}$$(1\cdot \mathrm{X}/\mathrm{S}\mathrm{j}+1)/(1\cdot \mathrm{s}\mathrm{j}/\mathrm{S}\mathrm{j}+1)\ldots(1- \mathrm{X}/\mathrm{s}\iota)/(1\cdot \mathrm{s}\mathrm{j}/\mathrm{S}\mathrm{L})$$.(1\cdot \mathrm{X}/\mathrm{s}\mathrm{l})/(1\cdot \mathrm{s}\mathrm{j}/\mathrm{s}\mathrm{l})\ldots(1\cdot \mathrm{X}/\mathrm{s}\mathrm{j}- 1)/(1- \mathrm{s}\mathrm{j}/\mathrm{S}\mathrm{j}\cdot 1)\cdot$

At the usage of above form, the definition for singular cases
and(l-X/0)/(1-s/0)=1 should be followed.
Using the point functions, we can construct the rules for any neighbors CAof levels. The n-neighbor rules are identical to n-variable discrete functions.
Two variable discrete functions can be obtain from one-variable discrete functions
through point finctions by the following recurrence equation:$\mathrm{X}/0=1$$\mathrm{L}$$\mathrm{F}_{\mathrm{j}1\mathrm{j}2\ldots \mathrm{j}\mathrm{L}}(\mathrm{X}, \mathrm{Y})=\mathrm{I}\mathrm{s}1(\mathrm{X})\mathrm{g}.1(\mathrm{Y})+\mathrm{I}\mathrm{s}2(\mathrm{X})\mathrm{g}.2(\mathrm{Y})+\ldots+\mathrm{I}\mathrm{s}\mathrm{L}(\mathrm{X})\mathrm{g}\mathrm{i}\mathrm{L}(\mathrm{Y})$$(\mathrm{j}_{1}, \mathrm{j}_{2}, \mathrm{j}_{3},$$\mathrm{j}_{\mathrm{L}}=1,$\ldots ,2,3,$\mathrm{L}^{\mathrm{L}})$\ldots ,,.

As known from above expression, there are-variable discrete
functions. We can establish the same type recurrence relation between andvariable discrete functions. The result is$\mathrm{L}^{\mathrm{W}}(\mathrm{W}=\mathrm{L}^{2})$$\mathrm{n}$$\mathrm{n}$$\mathrm{n}+1$$\mathrm{F}_{\mathrm{j}1\mathrm{j}2\ldots \mathrm{j}\mathrm{L}}(\mathrm{X}_{\mathrm{n}+1}, \mathrm{X}_{\mathrm{n}},$,$\mathrm{X}_{1})=\mathrm{I}\mathrm{s}1(\mathrm{X}_{\mathrm{n}+1})\mathrm{f}\mathrm{j}1(\mathrm{X}_{\mathrm{n}},\ldots,\mathrm{X}_{1})+\ldots+\mathrm{I}\mathrm{s}\mathrm{L}(\mathrm{X}_{\mathrm{n}+1})\mathrm{f}\mathrm{j}\mathrm{L}(\mathrm{X}_{\mathrm{n}},\ldots,\mathrm{X}_{1})$\ldots ,$(\mathrm{j}_{1}, \mathrm{j}_{2}, \mathrm{j}_{3},$$\mathrm{j}_{\mathrm{L}}=1,$\ldots ,2,3,$\mathrm{L}^{\mathrm{W}}\mathrm{t}\mathrm{W}=\mathrm{L}^{\mathrm{n}})$\ldots ,),are n variable discrete functions
generated by n time iterations started fiom two and one variable relation.

where$\mathrm{f}_{\mathrm{j}1}(\mathrm{X}_{\mathrm{n}},\ldots \mathrm{X}_{1})$,$\mathrm{f}_{\mathrm{j}2}(\mathrm{X}_{\mathrm{n}},\ldots,\mathrm{X}_{1})$,$\mathrm{f}_{\mathrm{j}\mathrm{L}}(\mathrm{X}_{\mathrm{n}},\ldots,\mathrm{X}_{1})$\ldots ,Self-Similarity and Rule Dynamical Property of CA
Here, we consider self-similarity of CA which leads us to arecognition thatCA has the rule-dynamical property (concise explanation is seen in [4]). A
higher level CA is produced by dividing cell array to neighbor size blocks. In
this dividing, each cel block can be described by usinglevels. Every cell
block is affected by both neighbored blocks and itself in its temporal statechanges. Ahalf of cels in aneighbored block contribute to another neighbored$\mathrm{I}P$

73
blocks to each other. The situation is illustrated below.

We note that is the system size (i.e., number of cells in the system), as alreadystated above. On these blocking, we conclude that three-neighboy CA gives ageneral picture on Wolfram typeribe above CA of block cells by. We canthe same type difference equation of temporal development of every block cels byusing block level variable , i.e.,$\mathrm{N}$$\mathrm{C}\mathrm{A}$$\mathrm{d}\mathrm{e}\mathrm{s}_{\mathrm{t}}\mathrm{c}$$\xi$$\zeta_{\mathrm{k}}(\mathrm{t}+1)=\mathrm{F}(\xi_{\mathrm{k}\cdot 1}(\mathrm{t}), \xi_{\mathrm{k}}(\mathrm{t}),$$\zeta_{\mathrm{k}+1}(\mathrm{t}))$,wheredenotes i-th block clustered together with neighbor size at time . We
can completely recognize states for each block cells with preparing IF levels for ablock. Then the original CA reaches to the CA of leveland neighborhood$\xi_{\mathrm{i}}(\mathrm{t})$$\mathrm{t}$$\mathrm{L}^{\mathrm{n}}$three.
It is possible such blocking for the cell block automata. We therefore know
, and that cellular automata
that neighborhood three may be fundamental inhave the self-similarity feature by above blocking. If we introduce acoarse
graining of block state by use of original number of levels, and if the rule isinvariant for this coarse graining, the fractal property of spati0-temporal patternof cell states in CA is realzed.
Now we discuss rule-dynamical property of. As seen from above block
making, it is an interesting aspect that CA is consisting of blocks each of whichdevelops its states temporally by its own manner. The temporal development ofablock cells can be described by amapping from the block levelat time tothe block levelat time. This mapping actually depends on neighbored
blocks. They yield boundary conditions for this mapping because cells in ablocknear the boundary require extra-cells to determine the state at next time step.
These extra cels are supplied from two neighbored blocks. Taking these points
into account, we can describe the temporal development of k-th block state (or$\mathrm{C}\mathrm{A}$$\mathrm{C}\mathrm{A}$$\Psi$$\xi(\mathrm{t}+1)$$\mathrm{t}+1$$\xi(\mathrm{t})$$\mathrm{t}$74level) by folowing equation:$\mathrm{a}(\mathrm{t}+1)=\Sigma_{(\mathrm{a}.\mathrm{b})}\mathrm{I}_{(\mathrm{a},\mathrm{b})}(\mathrm{a}\cdot 1(\mathrm{t})=\mathrm{a}, \mathrm{a}_{+1}(\mathrm{t})=\mathrm{b})\Psi \mathrm{a}.\mathrm{b}( \xi_{\mathrm{k}\cdot 1}(\mathrm{t}), \mathrm{a}(\mathrm{t})$,$\mathrm{a}_{+1}(\mathrm{t}))$,signifies the function which takes the value 1if and only if
wheretake the specified cell levels of boundary effect cels, or takes the value
and0for other cases . The above equation implies that the rule to determine thelevel at next time step in k-th block is temporaly changed by the both side ofneighbored blocks. In other words, every block undergoes rule-dynamics in thepossible
sense of temporal changing of rule (or mapping). Each block has
denotes the integer part of .
rules. Notice that$\mathrm{a}\cdot 1(\mathrm{t})$$\mathrm{I}(\mathrm{a}.\mathrm{b})(\ldots)$$\mathrm{E}+1(\mathrm{t})$$\mathrm{L}^{2[\mathrm{n}l2]}$$[\mathrm{x}]$$\mathrm{x}$References[1] A. Ilachinski, Celular Automata. World Scientific, Singapore 2001.
[2] A. Ankiewicz, Y. Nagai, “Solitons in multi-level celular automata”.

to beappeared in Chaos Solitons&Fractals.
[3] S. Wolfram, Theory and Application of Celular Automata. World Scientific,

Singapore 1986.
[4] Y. Nagai, Y. Aizawa, “Rule-dynamical generalzation of McCulloch-Pitts
neuron networks”. BioSystems. 58 (2000) 177- 185.