Sensitivity of Elementary Cellular Automata to Their Inputs

rule

100


Classification of this elementary CA according to S. Wolfram: Class 2

The sensitivity of an elementary cellular automaton (CA) to its inputs is defined as the space-averaged proportion of the cells

c

j

in the neighborhoods of the CA's cells

c

i

, that is,

N(

c

i

), that affect the state of

c

i

during the subsequent time step. This proportion can be expressed as

μ=

1

3n

∑

c

i

1

∑

j=-1

J

i,i+j

,

where

n

denotes the number of cells upon which the CA is built and

J

i,i+j

represents the

i

,

(i+j)

th

entry in an

n×n

Jacobian matrix that can be one if a modification of the state of

c

i+j

at the

th

t

time step implies a perturbation of

c

i

's state during the subsequent time step and is zero otherwise. Since for an elementary CA,

N(

c

i

)=(

c

i-1

,

c

i

,

c

i+1

)

,

J

constitutes a tridiagonal matrix and

μ=1

if and only if

J

i,i+j

=1

for every neighbor

c

j

of

c

i

, and this holds for every

c

i

of the CA. It has been shown that

μ

can be employed to find an upper bound on the maximum Lyapunov exponent of elementary CA.