Stochastic Cellular Automata: Correlations, Decidability and Simulations

Abstract

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 presen