today's talk
Alexander Shen
Universality in Asynchronous Cellular Automata. A cellular automaton is a dynamical system consisting of an infinite array ofcells, such that each cell uses a local neighborhood to perform a transition. Anasynchronous cellular automaton (ACA) is a modification of cellular automatawhere every cell can update at is own tempo, without the need for global synchronization. In this talk we survey computational abilities of asynchronous cellularautomata and show that—despite their fundamental differences—most asynchronous automata can invariantly “simulate” their synchronous counterparts[1]. To achieve that, we present two characterizations of invariance in asynchronous automata:– An algebraic approach using the notion of commutativity, as introduced byG´acs [2].– A novel computational approach using flip automata networks, which additionally allows for simpler simulations and can be used to construct some ofthe smallest universal ACAs [3].Finally, we discuss the limits of asynchronous computation by demonstratingthat for certain automata neither universality nor reliable simulation can beachieved.Further ReadingMore details can be found in the corresponding paper [3]. References 1. T. Worsch, “Towards intrinsically universal asynchronous ca,” Natural Computing,vol. 12, no. 4, pp. 539–550, 2013. 2. P. Gacs, “Deterministic computations whose history is independent of the order ofasynchronous updating,” 2001. 3. I. Baburin, M. Cook, F. Gr¨otschla, A. Plesner, and R. Wattenhofer, “Universality frontier for asynchronous cellular automata,” 2025.
See also https://arxiv.org/abs/2502.05989
Laurent Bienvenu HDR (video made from the room, sorry for the quality)