#матлог #учёба #спецсеминар

Kolmogorov seminar on complexity (for receive the zoom link, please email nikolay.vereshchagin@gmail.com)

21 April 2025, 17.30 CET = 18.30 Moscow time

Speaker: Ivan Baburin
Title: Universality in Asynchronous Cellular Automata

Abstract:
A cellular automaton is a dynamical system consisting of an infinite array of cells, such that each cell uses a local neighborhood to perform a transition. An asynchronous cellular automaton (ACA) is a modification of cellular automata where every cell can update at is own tempo, without the need for global synchronization. In this talk we survey computational abilities of asynchronous cellular automata 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 by G´acs [2]. – A novel computational approach using flip automata networks, which additionally allows for simpler simulations and can be used to construct some of the smallest universal ACAs [3]. Finally, we discuss the limits of asynchronous computation by demonstrating that for certain automata neither universality nor reliable simulation can be achieved. Further Reading More 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 of asynchronous updating,” 2001.
3. I. Baburin, M. Cook, F. Gr¨otschla, A. Plesner, and R. Wattenhofer, “Universality frontier for asynchronous cellular automata,” 2025.

➰ ВК