Cellular Automata/Information Dynamics

Information speed

$v={\frac {\Delta x}{\Delta t}}$

It is defined as the number

Speed of light

Is the maximum speed information can travel inside CA.It depends on the size and shape of the neighborhood and it may depend on the direction.

For asymmetric 1D CA (left and right direction)

$c_{L}=k_{0}$ $c_{R}=k-k_{0}-1$

For symmetric 1D CA (radious $r$)

$c=r$

References

• Kolmogorov Complexity
• Shanon communication theory
• Hidenosuke Nishio , Takashi Saito, Information dynamics of cellular automata I: an algebraic study, Fundamenta Informaticae, v.58 n.3-4, p.399-420, December 2003
• Hidenosuke Nishio, Takashi Saito, Information Dynamics of Cellular Automata II: Completeness, Degeneracy and Entropy, September 4, 2002
• Hideyuki Takahashi, The Maximum Invariant Set of an Automaton System, Information and Control 32, 307-354 (1976)
• Hideyuki Takahashi, Undecidable Questions about the Maximum Invariant Set, Information and Control 33, 1-34 (1977)
• Hideyuki Takahashi, Information Transmission in One-Dimensional Cellular Space and the Maximum Invariant Set, Information and Control 33, 35-55 (1977)
• E. Banks. Information Processing and Transmission in Cellular Automata. Ph.D. Thesis, MIT (1971).