On the classifiability of cellular automata (Q1978505)

Based on computer simulations Wolfram presented in several papers conjectured classifications of cellular automata into four types. We show a natural formalization of his rate of growth suggestion does not provide a classification (even probabilistically) of all cellular automata: For any rational \(p,q,0\), \(p,q\leq 1\) with \(p+q=1\), there is a cellular automata \(A_{p,q}\) which has probability p of being in class 3, probability q of being in class 4. We also construct an automata which grows monotonically at rate log \(t\), rather than at a constant rate.