Cellular Automata/Information Dynamics

From Wikibooks, open books for an open world
Jump to: navigation, search
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


  • 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).