  This paper studies three classes of cellular automata from a computational
point of view: freezing cellular automata where the state of a cell can only
decrease according to some order on states, cellular automata where each cell
only makes a bounded number of state changes in any orbit, and finally cellular
automata where each orbit converges to some fixed point. Many examples studied
in the literature fit into these definitions, in particular the works on
cristal growth started by S. Ulam in the 60s. The central question addressed
here is how the computational power and computational hardness of basic
properties is affected by the constraints of convergence, bounded number of
change, or local decreasing of states in each cell. By studying various
benchmark problems (short-term prediction, long term reachability, limits) and
considering various complexity measures and scales (LOGSPACE vs. PTIME,
communication complexity, Turing computability and arithmetical hierarchy) we
give a rich and nuanced answer: the overall computational complexity of such
cellular automata depends on the class considered (among the three above), the
dimension, and the precise problem studied. In particular, we show that all
settings can achieve universality in the sense of Blondel-Delvenne-K\r{u}rka,
although short term predictability varies from NLOGSPACE to P-complete.
Besides, the computability of limit configurations starting from computable
initial configurations separates bounded-change from convergent cellular
automata in dimension~1, but also dimension~1 versus higher dimensions for
freezing cellular automata. Another surprising dimension-sensitive result
obtained is that nilpotency becomes decidable in dimension~ 1 for all the three
classes, while it stays undecidable even for freezing cellular automata in
higher dimension.
