数理解析研究所講究録 1325 巻 2003 年 197-202

197
Information dyynnaammiics of cellular automata:
CA computation and information theory’
Hidenosuke Nishio ( 西尾英之助 元・京大・理 )$\dagger$

Iwakura Miyake cho 204, SakyO-ku, Kyoto

Takashi Saito (斉藤隆 大工大・情報)
Faculty of Information Science, Osaka Institute of Technology

April 9, 2003

1Intro function
Using polynomials over finite fields, we formulated the polynomial state cellular
automata based on the information vaiable $X$ for investigating informational
phenomena arising from celular dynamics[Nishi0&Sait003]. In our youngestpaper, we endowed $X$ with the probability distribution $\{p(x)\}$ and establishedthe information theory of $CA$ in Shannon’s sense. We showed that the entropy ofconfigurations generally decreases by the cellular computation[Nishi0&Sait002].
Here we are going to extend the theory to -information variables and also try
to utilize Kolmogorov complexity as another measure of information amountcontained by configurations. As for the information theory and its relation toKolmogorov complexity we refer to [COver&ThOmas91].
$n$2Preliminaries
2.1

CA defined by polynomials over finite fields

One dimensional CA is usually defined with the space $Z$ (the set of integers),
and the local function and denoted
the neighborhood $N$ , the state set
we assume the 1-D CA with $N=$paper. Throughout thisas.
$\{-1,0, +1\}$ and denote simply as
$f$

$Q$

$\mathrm{C}\mathrm{A}=(Z,N,Q,f)$$\mathrm{C}\mathrm{A}=(Q,f)$with prime, where q
State Set: Q is assumed to be afinite field$|Q|=q=p^{n}$.
Soas
Qofcardinality|Q|.
and positive integer n. Denote the$\mathrm{G}\mathrm{F}(\mathrm{g})$extended abstract\dagger corraeponding author.

$\mathrm{E}$-mail:YRA05762@nifty.ne.jp$=p^{n}$$p$

198
Local Function: The local function f : $Q\cross Q$ xQ
by the polynomial form:$arrow Q$

is uniquely expressed$f(x,y, z)=u_{0}+u_{1}x+u_{2}y+\cdots+u_{i}x^{h}y^{j}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)$ .
$x,y$

and$\mathrm{a}\mathrm{n}\mathrm{d}+1$$z$assume the state values of the neighboring,$\mathrm{c}\mathrm{e}\mathrm{l}\mathrm{l}\mathrm{s}-1(\mathrm{l}\mathrm{e}\mathrm{f}\mathrm{t})$(2.1)$\mathrm{O}(\mathrm{c}\mathrm{e}\mathrm{n}\mathrm{t}\mathrm{e}\mathrm{r})$(right), respectively.

Global Map: The set of configurations is $C=Q^{Z}$ . The global map or theCA map $F$ : $Carrow C$ is defined as usual. Let $c(i)$ be the state of cell $i\in Z$ ofconfiguration $c\in C$ . The configuration at time is denoted by . $F^{t}(c^{0})=c^{t}$ .
.
So, the state of cell at time is denoted by$d$

$t$

$i$

2.2$c^{t}(i)$$t$Information X and Extended$\mathrm{C}\mathrm{A}[X]$

Information $X$ :Let $X$ be symbol different from those used in the polynomial
form (2.1). It stands for an unknown state or the information of acell in CA
and will be called the info rmation variable. In order to investigate the dynamicsof information $X$ in CA space, we consider another polynomial form, which.
generaly defines the cell state of the dended$\mathrm{C}\mathrm{A}$$g(X)=a_{0}+a_{1}X+\cdots+a_{i}X^{:}+\cdots+a_{q-1}X^{q-1}$,

where $a_{i}\in Q(0\leq i\leq q-1)$ .

(2.2)

uniquely defines afunction $Qarrow Q$ and the set of such functions is denoted
by $Q[X]$ . Evidently $|Q[X]|=q^{q}$ .

$g$

we:Based uponor Polynomial State
Extended, where the set of cell states is apolyn0define its extension$Q[X]$mial ringas defined above. The local function $fx$ is defined on the sameneighborhood and expressed by the same polynomial form as was defined by(2.1). The variables
will
and , however, move in $Q[X]$ instead of .
be called the polyrgomial state.
$\mathrm{C}\mathrm{A}=(Q,f)$$\mathrm{C}\mathrm{A}$$\mathrm{C}\mathrm{A}[X]$$\mathrm{C}\mathrm{A}[X]=(Q[X], f_{X})$

$f$

$Q$

$\mathrm{z}$$\mathrm{x},\mathrm{y}$$\mathrm{C}\mathrm{A}[X]$$\mathrm{C}\mathrm{A}$

2.3$n$-Information Variables, ...,
to be int
Consider indeterminates (information variables)$c^{0}=wX_{1}X_{2}\ldots
X_{n}w’$. As is in the preceding
duced into the initial configuration:is considered to be. Thus $c^{0}(i-1)=X_{i}$ for
section the cell state$1\leq i\leq n$ and the other cells have constants. At timeeffects of information, ,variables
in possibly appear at cells $\{c(i)|-t\leq i\leq t+n-1\}$of configuration . In order to discuss such acellular development, we need toextend the basic CA to -variable polynomial state.
$X_{1},X_{2}$$n$$c^{0}(0)$$X_{n}$$0$$X_{1}$$t$$X_{1},X_{2}$$\ldots$$c^{0}$$X_{n}$$c^{t}$$\mathrm{C}\mathrm{A}$$\mathrm{n}$is made similarly as
set $Q[X_{1}, X_{2}, \ldots, X_{n}]$ constitutes of polynomials of the form

Extension of CA to$\mathrm{C}\mathrm{A}[X_{1}, X_{2}, \ldots, X_{n}]$$\mathrm{C}\mathrm{A}[\mathrm{X}]$,The state199$g(X_{1}, X_{2},$\ldots ,$X_{n})=a_{0}+a_{1}X_{1}+a_{2}X_{2}+\cdots+a_{h}X_{1}^{i_{1}}X_{2}^{i_{2}}\cdots X_{n^{n}}^{i}+\cdots+$$a_{q^{n}-1}X_{1}^{q-1}X_{2}^{q-1}\cdots X_{n}^{q-1}$,

where ah $\in Q(0\leq h\leq q^{n}-1)$ .
The local function

2.4

$f$

(2.3)

is the same as Equation(2.1).

Substitution

and an -tuple ofDefinition 1Substitution: For a polynomial
as, we define the substitution, wheresymbols
the state which is obtained by substituting for , $1\leq i\leq n$ . Substitution foris defined, as in one variable case, by
a global configuration
substituting the polynomial state of each cell with .
$g\in Q[\mathrm{X}^{\mathrm{n}}]$$\mathrm{a}^{\mathrm{n}}=$$(a_{1}, a_{2}, \ldots, a_{n})$$n$$\psi_{\mathrm{a}^{\mathrm{n}}}(g)$$*\cdot\in Q$$a_{i}$$X_{:}$$c\{\psi_{\mathrm{a}^{\mathrm{n}}}(c)|\mathrm{a}^{\mathrm{n}}\in Q^{n}\}$$\mathrm{a}^{\mathrm{n}}$Evidently we have, for any$c\in Q\mathrm{K}^{\mathrm{n}}]^{Z}$,$1\leq|\{\psi_{\mathrm{a}^{\mathrm{n}}}(c)|\mathrm{a}^{\mathrm{n}}\in Q^{n}\}|\leq|Q|^{n}$.

We need the following commutative properties which are easily proved.
Proposition 2.1 (1) Substitution
mute each other. That is, let and,
we have, for any

and ring operations of polynomials combe polynomials in indeterminates, then$\psi_{\mathrm{a}^{\mathrm{n}}}$

$g$

$h$

$n$

$\mathrm{a}^{\mathrm{n}}\in Q^{n}$and$\psi_{\mathrm{a}^{\mathrm{n}}}(g+h)=\psi_{\mathrm{a}^{\mathrm{n}}}(g)+\psi_{\mathrm{a}^{\mathrm{n}}}(h)$$\psi_{\mathrm{a}^{\mathrm{n}}}(g\cdot h)=\psi_{\mathrm{a}^{\mathrm{n}}}(g)\cdot\psi_{\mathrm{a}^{\mathrm{n}}}(h)$

.

(2.4)

(2) The global map and the substitution commute each other.
$\psi_{\mathrm{a}^{\mathrm{n}}}(F_{X}(c))=F(\psi_{\mathrm{a}^{\mathrm{n}}}(c)),\forall \mathrm{a}^{\mathrm{n}}\in Q^{n}$

2.5.

(2.5)

Degeneracy, a configuration is called m-degeneratebe, wheoe $0\leq m\leq|Q|^{n}-1$ . Suchcalled the degree of degeneracy of and denoted as $m(c)$ . A configuration is
simply called degenerate if $m(c)\neq 0$ .

Definition 2(Degeneracy) In$CA[\mathrm{X}^{\mathrm{n}}]$$c$$\dot{\iota}f|\{\psi_{\mathrm{a}^{\mathrm{n}}}(c)|\mathrm{a}^{\mathrm{n}}\in Q^{n}\}|=|Q|^{n}-m$$c$Theorem 2.2$m(c)\leq m(F(c))$$mw\cdot.ll$

$c$

(2.6)

3Information Theory of CA Dynamics
For defining the quantitative measure of information amount transmitted orlost through the CA space-time development, we are going to exploit Shannon’s
information theory, in particular the mutual entropy and the channel capacity
for the deterministic channel

200
3.1

Deterministic Channel

We shortly recall Shannon’s information theory, so that it may fit in with ourformalism. Let $X$ be arandom variable of the information source, which takes
avalue $x\in Q$ with probability $\{px(x), x\in Q\}$ . $px(x)$ will be abbreviated as$p(x)$ . Shannon’s entropy $H(X)$ is defined by,(3.1)$H(X)=- \sum_{x\in Q}p(x)\log p(x)$, where : $Qarrow$Let us consider adeterministic communication channel
is function from to . That is source symbol in is sent by the senderand the receiver receives the symbol $y=g(x)\in Q$ with conditional probability$p(y|x)=1$ . $\mathrm{Y}=g(X)$ is naturally arandom variable and its probability
distribution is calculated by the following formula.
$(X,g, \mathrm{Y})$

$Q$

$Q$

$Q$

$p(y)= \sum_{x\in g^{-1}(y)}p(x)$The mutual information$H(\mathrm{Y})-H(\mathrm{Y}|X)$$I(X\cdot \mathrm{Y})|$.

$g$

$Q$

$x$

.

(3.2)

is defined by $I(X;\mathrm{Y})=H(X)-H(X|\mathrm{Y})=$

Since the channel is deterministic we see that $p(y|x)$ is equal to 1or 0. Therefore
we have the fallowings; $H(\mathrm{Y}|X)=0$ and $I(X;\mathrm{Y})=H(\mathrm{Y})$ .
The channel capacity is defined as follows:(3.3)$C= \max_{p(X)}I(X;\mathrm{Y})=\max_{p(X)}H(\mathrm{Y})$3.2

Entropy of Configurations

and areHere we assume the information varibale $X$ to be arandom
going to investigate how much information of the initial state is transmitted orlost during CA computation.
$var\dot{\mathrm{v}}able$

We interpret the correspondence between the CA dynamics and the communication theory as follows; the initial configuration containing an unknown
state $X$ at cell 0corresponds to the information source, while the configu$+1$ polynomial states does the received message.
which contains
rationWe begin with one variable case. Let’s take the portion of aconfiguration, where $c(i)$ is the polynomial, $c(t-1)$ ,$c=(c(-t), c(-t+1)$ , ,state (random variable) of cell . The other cells contain constant states andcan be ignored. The probability $p(c)=\{p(c_{a})|a\in Q\}$ is calculated by thefollowing equation.
$\sum$$p(x)$ ,(3.4)$p(c_{a})=$$2t$$c^{t}$$\mathrm{c}(\mathrm{i})$$\mathrm{c}(\mathrm{i})$$\ldots$$\ldots$$i$$x\in g^{-1}(c_{\mathrm{Q}})$

where 9is function $Xarrow c$ such that $g(x)=(c(-t)(x), c(-t+1)(x),$l)(x), $c(t)(x))$ . The entropy of is given by$\ldots$, $c(0)(x)$ ,$\ldots$$d$$H(c^{t})=- \sum_{a\in Q}p(c_{a}^{t})\log p(c_{a}^{t})$

.

(3.5)

, $c(t-$201
Theorem 3.1$H(c^{t})\geq H(c^{t+1}),\forall t\geq 0$

3.3

(3.6)

.

Channel Capacity

Though it is generally not easy to compute the channel capacity for arbitrary
bechannels, we can present aformula for the deterministic ones. Letchannel, where $\mathrm{Y}=g(X),g:Qarrow Q$ . The channel capacity is given by (3.3)
and therefore our task is to compute $\max H(\mathrm{Y})$ over $\{p(X)\}$ . Using (3.2) we$(X, \mathrm{Y})$$\mathrm{a}$

$C$

have,
$H( \mathrm{Y})=-\sum_{y\in Q}(\sum_{oe\in g^{-1}(y)}p(x))\log(\sum_{x\in g^{-1}(y)}p(x))$

.

(3.7)

The entropy function $H$ with components generally takae the mnimum value
Note that the maximum is attained$\log n$ , where the distribution is uniform.
has the same probability and thedefined bywhen each partition ofdistribution within apartition block is arbitrary.
$n$$g^{-1}$

$Q$

(3.8)

$p(g^{-1}(y))= \frac{1}{|g(Q)|}$

If $g^{-1}(y)$ is vacant, then $p(y)=0$ . Consequently we have,
Theorem 3.2$C= \max H(\mathrm{Y})=\log|g(Q)|$

.

(3.9)

$p(X)$

Theorem 3.3$C^{t}= \max H(c^{t})=\log(|Q|-m(c^{t}))$(3.10)$\mathrm{p}(X)$Theorem 3.4$C^{t}\geq C^{t+1}$3.4$n$for any$t\geq 0$.

(3.11)-Information Variables

We generalize the idea of one variable case to variable CAs. Let
are identically distributed independent random vari(Xi,, , ) whereablae with distribution $\{p(x)\}$ . If the initial configuration is assumed to be, then its entropy is given by$H(c^{t})$$nH(X)$ . For -variable CA the similar monotone decreasing properties of. Particularly we have,hold as one-variable
and$\mathrm{X}^{\mathrm{n}}=$$n$$X_{2}$$\ldots$$X_{n}$$\mathrm{X}\mathrm{i}\mathrm{S}$$c^{0}=wX_{1}X_{2}\ldots X_{n}w’=\mathrm{w}\mathrm{X}\mathrm{n}\mathrm{w}’$$H(c^{0})=H(\mathrm{X}^{\mathrm{n}})=$$\mathrm{n}$$C^{t}$$\mathrm{C}\mathrm{A}$Theorem 3.5$C^{t}= \max_{p(X)}H(c^{t})=\log(|Q|^{n}-m(c^{t}))$(3.12)

202
4

Kolmogorov complexity of configurations

We are utilizing the following theorem about the conditioned Kolmogorov combe identically distributed
plexity and entropy. Let
independent random variables which take the value in afinite alphabet
with probability $p(x)$ .
$\mathrm{X}^{\mathrm{n}}=\{X_{i}, 1\leq i\leq n\}$

$Q$

$x$

Theorem 4.1 (Kolmogorov) Let
there eists a constant such that$p( \mathrm{x}^{\mathrm{n}})=p(x_{1},x_{2}, \ldots, x_{n})=\prod_{i=1}^{n}p(x_{i})$. Then$c$$\mathrm{H}(\mathrm{X})\leq\frac{1}{n}\sum_{\mathrm{x}^{\mathrm{n}}}p(x^{n})K(P|n)$

for all . Therefore,$n$$\leq H(X)+\frac{|Q|\log n}{n}+\frac{c}{n}$$E \frac{1}{n}K(\mathrm{X}^{\mathrm{n}}|n)arrow H(X)$(4.1).

We recall here the monotone decreasing property of the entropy of configurations
as stated in Theorem (3.1). Prom this theorem and the above theorem by
Kolmogorov we havebe the conditional Kolmogorov complexity of theTheorem 4.2 Let,stringcontained by S. The we have, for$K^{t}(\mathrm{X}^{\mathrm{n}}|n)$$narrow \mathrm{o}\mathrm{o}$$\mathrm{x}^{\mathrm{n}}$(4.2)$E \frac{1}{n}K^{t}(\mathrm{X}^{\mathrm{n}}|n)\geq E\frac{1}{n}K^{t+1}(\mathrm{X}^{\mathrm{n}}|n)$The equality holds$\dot{l}f$and only if$I(\mathrm{X}^{\mathrm{n}}; c^{t}|c^{t+1})=0$.

5Concluding Remarks
be to find anew information measure for individual
Afurther research topics
configurations and investigate its behavior during CA dynamics.
$\mathrm{w}\mathrm{i}\mathrm{U}$Aconjecture: Let be any consecutive finite portion of any configuration. Then $K_{\mathrm{c}}(x)+constant$and denote its Kolmogorov complexity by$K_{F(c)}(x’)$ , where $d$ is the corresponding finite portion ofin $F(c):x’=F(x)$ .

$c$

$x$

$\geq$$K_{\mathrm{c}}(x)$$x$References[COver&ThOmas91] Elements of Information Thecyry, by Thomas M.Cover andJoy A.Thomas,1991,John Wiley&Sons, 542pp.
[NishiO&Sait002] H. Nishio and T. Saito, Information Dyn amics of Cellular Automata ILCompleteness, Degeneracy and Entropy, presented at 8th IFIP WG1.5
Conference, Prague, Chech Rep.. September 12. 2002.(manuscript available in$122\mathrm{K}\mathrm{B}$pdf)[NishiO&Sait003] H. Nishio and T. Saito, Information Dynamics of Cellular Automata :An Algebraic Study, submitted for publication to Fundamenta Infor$\mathrm{I}$