Ivan Baburin's talk on March 17

[Nikolay Vereshchagin]

On March 17 we will have Ivan Baburin's talk on Universality in Asynchronous Cellular Automata. 

Abstract. Universality in Asynchronous Cellular Automata Ivan Baburin Kolmogorov Seminar Talk description 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.

Usual zoom link:
https://u-bordeaux-fr.zoom.us/j/88402787361?pwd=WktCdEhBT3pXN0pLUGg4Z3RuMlpsQT09

16.30 CET = 18.30 Moscow time