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

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

Date: Dec 2, 2024. Time: 18:30 (MSK), 16:30 (CET)
Speaker: Ivan Baburin
Title: Orphans in Cellular Automata

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. Every non-surjective cellular automaton A has so-called Garden-of-Eden configurations, i.e. configurations which can never naturally appear in the evolution of A because they don’t have a preimage. It turns out that it is possible to characterize all Garden-of-Eden configurations in a cellular automaton using only finite patterns and regular languages. In this talk we discuss the following results, based on the presentation in [1]:
1. The duality between Garden-of-Eden configurations and orphans (finite patterns without a preimage). Every Garden-of-Eden configuration needs to contain an orphan, and every configuration containing an orphan is Garden-of-Eden.
2. For any one-dimensional cellular automaton the set of all orphans forms a regular language, and this language can be recognized using a finite-state machine constructed from a de Brujin graph.

Further Reading
The presented algorithms and dualities with de Brujin graphs were originally discovered in [2], and they can be further generalized to test for injectivity and surjectivity of one-dimensional cellular automata. A generalization to higher dimensions is impossible, since these properties are known to be undecidable [3].

References
1. J. Kari, Cellular automata. University of Turku, 2022.
2. K. Sutner, “De bruijn graphs and linear cellular automata,” Complex Systems, vol. 5, no. 1, pp. 19–30, 1991.
3. J. Kari, “Theory of cellular autom

➰ ВК