Simulating Noisy Systems With Unified Cellular Automata Formalism.pdf

Key Contributions:

1. Unified Formalism: The authors introduce a novel formalism to handle deterministic, non-deterministic, and stochastic CA in a consistent manner. This allows for a unified approach to studying their simulation properties.

2. Intrinsic Simulations Extended: Building on previous work on intrinsic simulations (exact simulations between deterministic CAs), the paper extends this concept to include non-deterministic and stochastic CAs.

3. Equality of Stochastic Maps: A crucial result establishes that two stochastic CA are equal in terms of their global behavior if and only if there exists a coupling between their random sources. This provides a tool for proving or disproving equality of such maps.

4. No Universal Stochastic CA: The authors demonstrate that, unlike deterministic CAs, there is no universal (simulating all other) stochastic CA. However, they construct specific stochastic CAs achieving optimal partial universality within their class.

Challenges and Findings:

- Limited Study of Stochastic CAs: The paper highlights the relative lack of attention given to stochastic CAs in theoretical research compared to deterministic and probabilistic CAs.

- Undecidability: Determining whether two stochastic CAs simulate the same distribution is shown to be undecidable in dimensions greater than one.

- No-Go Results: The authors prove that a stochastic CA can only simulate another if they share a compatible random source, emphasizing the importance of the specific type of randomness involved.