2011/04/30 by Jérôme Chandesris, Alberto Dennunzio, Chandesris, Jérôme +5
Biochemistry, Genetics and Molecular Biology · Computer Science · Physics and Astronomy · #Cellular Automata and Applications #Cellular Automata and Lattice Gases (nlin.CG) #Computability, Logic, AI Algorithms #DNA and Biological Computing #FOS: Computer and information sciences #FOS: Physical sciences #Formal Languages and Automata Theory (cs.FL) #cs.FL #nlin.CG
paper · pdf · doi:10.48550/arxiv.1105.0065
arxiv created 2011/04/30 · openalex publication_date 2011/04/30 · arxiv updated 2011/05/03 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 TM on any input. We also consider the computational cost of such simulations.