Affiliations: Università degli Studi di Milano–Bicocca, Dipartimento di Informatica, Sistemistica e Comunicazione, Viale Sarca 336, 20126 Milano, Italy, dennunzio@disco.unimib.it | Université Nice-Sophia Antipolis, Laboratoire I3S, 2000 Route des Colles, 06903 Sophia Antipolis, France, enrico.formenti@unice.fr | Università degli Studi di Milano–Bicocca, Dipartimento di Informatica, Sistemistica e Comunicazione, Viale Sarca 336, 20126 Milano, Italy, luca.manzoni@disco.unimib.it
Note: [] Address for correspondence: Università degli Studi di Milano–Bicocca, Dipartimento di Informatica, Sistemistica e Comunicazione, Viale Sarca 336, 20126 Milano, Italy
Abstract: 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.
