2015/12/11 by Martin Delacourt, Delacourt, Martin, Benjamin Hellouin de Ménibus +1
Computer Science · Mathematics · #37B15 #68Q80 #68Q87 #Cellular Automata and Applications #Cellular Automata and Lattice Gases (nlin.CG) #Dynamical Systems (math.DS) #F.1.1 #F.1.2 #FOS: Computer and information sciences #FOS: Mathematics #FOS: Physical sciences #Formal Languages and Automata Theory (cs.FL) #Mathematical Dynamics and Fractals #Stochastic processes and statistical mechanics
paper · pdf · doi:10.48550/arxiv.1512.03696
openalex publication_date 2015/12/11 · openalex created_date 2022/10/02 · openalex updated_date 2026/07/28
We consider the typical asymptotic behaviour of cellular automata of higher\ndimension (greater than 2). That is, we take an initial configuration at random\naccording to a Bernoulli (i.i.d) probability measure, iterate some cellular\nautomaton, and consider the (set of) limit probability measure(s) as time tends\nto infinity. In this paper, we prove that limit measures that can be reached by\nhigher-dimensional cellular automata are completely characterised by\ncomputability conditions, as in the one-dimensional case. This implies that\ncellular automata have the same variety and complexity of typical asymptotic\nbehaviours as Turing machines, and that any nontrivial property in this regard\nis undecidable (Rice-type theorem). These results extend to connected sets of\nlimit measures and Ces `aro mean convergence. The main tool is the\nimplementation of arbitrary computation in the time evolution of a cellular\nautomata in such a way that it emerges and self-organises from a random\nconfiguration.\n