Laboratoire d'Informatique, Signaux et Systèmes de Sophia Antipolis (I3S), Université Côte d’Azur, UMR CNRS 7271, 2000 Route des Lucioles, BP 121, 06903 Sophia Antipolis Cedex, France
Prof. Dr. Enrico Formenti
Laboratoire d'Informatique, Signaux et Systèmes de Sophia Antipolis (I3S), Université Côte d’Azur, UMR CNRS 7271, 2000 Route des Lucioles, BP 121, 06903 Sophia Antipolis Cedex, France
Equicontinuity classification is a popular classification of cellular automata based on their dynamical behavior. In this paper we prove that most of its classes are undecidable.
This work studies some aspects of the computational power of fully asynchronous cellular automata (ACA). We deal with some notions of simulation between ACA and Turing Machines. In particular, we characterize the updating sequences specifying which are “universal”, i.e., allowing a (specific family of) ACA to simulate any Turing machine on any input. We also consider the computational cost of such simulations. Finally, we deal with ACA equipped with peculiar updating sequences, namely those generated by random walks.