2011/02/04 by Pablo Arrighi, Renan Fargetton, Arrighi, Pablo +5 · 3 citations
Computer Science · Physics and Astronomy · #37A50 #37B15 #37L55 #68Q80 #81P45 #B.6.1 #Cellular Automata and Applications #Computability, Logic, AI Algorithms #Discrete Mathematics (cs.DM) #F.1.1 #F.1.2 #FOS: Computer and information sciences #FOS: Physical sciences #Formal Languages and Automata Theory (cs.FL) #J.2 #Mathematical Physics (math-ph) #Quantum Physics (quant-ph) #Theoretical and Computational Physics
paper · doi:10.48550/arxiv.1102.0860
openalex publication_date 2011/02/04 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/30
Cellular automata (CA) consist of an array of identical cells, each of which may take one of a finite number of possible states. The entire array evolves in discrete time steps by iterating a global evolution G. Further, this global evolution G is required to be shift-invariant (it acts the same everywhere) and causal (information cannot be transmitted faster than some fixed number of cells per time step). At least in the classical, reversible and quantum cases, these two top-down axiomatic conditions are sufficient to entail more bottom-up, operational descriptions of G. We investigate whether the same is true in the probabilistic case. Keywords: Characterization, noise, Markov process, stochastic Einstein locality, screening-off, common cause principle, non-signalling, Multi-party non-local box.