  This paper introduces a simple formalism for dealing with deterministic, non-
deterministic and stochastic cellular automata in an unified and composable
manner. This formalism allows for local probabilistic correlations, a feature
which is not present in usual definitions. We show that this feature allows for
strictly more behaviors (for instance, number conserving stochastic cellular
automata require these local probabilistic correlations). We also show that
several problems which are deceptively simple in the usual definitions, become
undecidable when we allow for local probabilistic correlations, even in
dimension one. Armed with this formalism, we extend the notion of intrinsic
simulation between deterministic cellular automata, to the non-deterministic
and stochas- tic settings. Although the intrinsic simulation relation is shown
to become undecidable in dimension two and higher, we provide explicit tools to
prove or disprove the existence of such a simulation between any two given
stochastic cellular automata. Those tools rely upon a characterization of
equality of stochastic global maps, shown to be equivalent to the existence of
a stochastic coupling between the random sources. We apply them to prove that
there is no universal stochastic cellular automaton. Yet we provide stochastic
cellular automata achieving optimal partial universality, as well as a
universal non-deterministic cellular automaton.
