On the classifiability of cellular automata

Based on computer simulations Wolfram presented in several papers conjectur ed classifications of cellular automata into four types. We show a natural formalization of his rate of growth suggestion does not provide a classific ation (even probabilistically) of all cellular automata: For any rational p ,q, 0 less than or equal to p, q with p + q = 1, there is a cellular automa ta A(p,q) which has probability p of being in class 3, probability q of bei ng in class 4. We also construct an automata which grows monotonically at r ate log t, rather than at a constant rate. (C) 2000 Elsevier Science B.V. A ll rights reserved.