There is a growing body of evidence that the phenomenology of computation is related to phenomenology of phase transitions. In particular, if a system is to be capable of universal computation, it must be capable of exhibiting arbitrarily extended transient behavior - that is, transients may diverge to infinity, and yet they still must be considered to be transients - they may, at some arbitrary time (in an infinite system), lead to periodic dynamics. Thus, the suggestion [Lan90] that there is a correspondence between the unboundability of transients in Turing's Halting Problem and the divergence of transients in the phenomenon of critical slowing down is intuitive.
In fact, as pointed in [Lan90], rather than attempting to explain the phenomenology of computation as being due to an underlying phase-transition, in many ways it makes more sense to explain the phenomenology of phase-transitions as being due to fundamental limits on physical system's abilities to effectively "compute" their own dynamics.
Physical systems are the most direct "computers" for computing their own dynamics - and therefore, if there are in-principle intractable computational problems associated with their dynamics from certain initial conditions, and if the Church-Turing hypothesis is true for physical systems (or an extension of the Church-Turing hypothesis if a higher computational class is found), then the physical computer that is the system itself will be bound by these same in-principle computational limitations on working out its own behavior, leading to a divergence of transients - possibly to infinity - before the system arrives at "the answer" for its own physical state.
These intuitions motivate the criterion we use to measure the complexity of a cellular automaton: the time it takes the (generalized) mean field approximation to converge to a fixed point or limit cycle. Simple rules converge rapidly in generalized mean-field approximation. Chaotic rules converge rapidly as well: these rules have quickly decaying spatial correlations, and are thus well-approximated by the mean field theory which assumes the absence of correlation beyond a given distance.