Time: 15.12.2020 13:00
Speaker: Toni Hotanen, University of Turku
Title: Lyapunov Exponents and Topological Entropy of Cellular Automata and Turing Machines
Abstract: Lyapunov exponents are an important concept in differentiable dynamical systems and they measure stability or sensitivity in the system. Their analogues for cellular automata were proposed by Shereshevsky and since then they have been further developed and studied. It was conjectured that there does not exist such a sensitive cellular automaton, that would have both the right and the left pointwise Lyapunov exponents taking the value zero, for each configuration. In this talk we prove the conjecture false by constructing such a cellular automaton, using aperiodic, complete Turing machines as a building block. In the second part of the talk we will work on several related decision problems in the setting of reversible Turing machines and cellular automata. The decision problems we are interested in are related to the notions of periodicity, topological entropy, speed and Lyapunov exponents. We will prove several of these problems to be undecidable in the setting of reversible Turing machines and as a corollary we get analogous results in the setting of reversible cellular automata.