Пятница, 12 сентября, ауд. 203. Начало в 17:00.
Докладчик: Jarkko Kari (University of Turku).
Тема: Universal Pattern Generation by Cellular Automata.
Abstract
We call a cellular automaton a universal pattern generator if from some finite initial seed it generates all finite patterns over its state set. A stronger variant requires that all finite patterns get generated in every position of the space, that is, the forward orbit of the initial finite seed is dense in the product topology. We demonstrate a one-dimensional universal pattern generator of the weaker type and discuss its relation to some open problems in number theory. We conjecture that strong pattern generators exist, and provide an automaton that we believe to have this property.
