Journal of Stat&tical Physics, Vol. 45, Nos. 5/6, 1986. p. 875-883.
A probabilistic one-dimensional cellular automaton model by Domany and Kinzel is mapped into an inhomogeneous cellular automaton with the Boolean functions XOR and AND as transition rules. Wolfram's classification is recovered by varying the frequency of these two simple rules and by quenching or annealing the inhomogeneity. In particular, "class 4" is related to critical behavior in directed percolation. Also, the critical slowing down of second-order phase transitions is related to a stochastic version of the classical "halting problem" of computation theory.