Kolmogorov complexity and cellular automata classification

We present a new approach to cellular automata (CA) classification based on algorithmic complexity. We construct a parameter ii which is based only on the transition table of CA and measures the 'randomness'" of evolutions; k is better, in a certain sense, than any other parameter recursively defina ble on CA tables. We investigate the relations between the classical topolo gical approach and ours. Our parameter is compared with Langton's lambda pa rameter: k turns out to be theoretically better and also agrees with some p ractical evidences reported in literature. Finally, we propose a protocol t o approximate k and make experiments on CA dynamical behavior. (C) 2001 Pub lished by Elsevier Science B.V.