2010/12/03 by Fabien Givors, Givors, Fabien, Grégory Lafitte +3
Computer Science · Physics and Astronomy · #Cellular Automata and Applications #Cellular Automata and Lattice Gases (nlin.CG) #Computability, Logic, AI Algorithms #Computational Complexity (cs.CC) #FOS: Computer and information sciences #FOS: Physical sciences #Logic in Computer Science (cs.LO) #cs.CC #cs.LO #nlin.CG #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.1012.1221
Journées Automates Cellulaires 2010, Turku : Finland (2010)
arxiv created 2010/12/03 · openalex publication_date 2010/12/03 · arxiv updated 2010/12/07 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We define a new transfinite time model of computation, infinite time cellular automata. The model is shown to be as powerful than infinite time Turing machines, both on finite and infinite inputs; thus inheriting many of its properties. We then show how to simulate the canonical real computation model, BSS machines, with infinite time cellular automata in exactly ωsteps.