This workshop focuses on computability aspects of dynamical systems. Topics addressed include

The organizers are Nathalie Aubrun, Mathieu Sablik and Maxime Senot.

Speakers

Program

Tuesday December 17 (room 435 (morning) and Amphi I (afternoon))

9h30-10h15 Welcoming and coffee
10h15-11h M. Hoyrup, Computability in ergodic theory. [pdf]
11h-11h45 E. Hainry, Robust computation in perturbed dynamical systems. [pdf]
11h45-12h30 O. Bournez, On The Hardness of Reachability for Dynamical Systems: Computability and Complexity. [pdf]
12h30 Lunch
14h-14h45 B. Hellouin, Possible asymptotic behaviors of cellular automata. [pdf], [Image], [Image2]
14h45-15h30 T. Monteil, Quantifying the aperiodicity of a Wang tile set.
15h30 Coffee break
16h-16h45 B. Adamczewski, Some decision problems around the Skolem-Mahler-Lech theorem.
16h45-17h30 J. Cassaigne, SMART : a small aperiodic reversible Turing machine. [Image]

Wednesday December 18 (room 435 (morning) and Amphi J (afternoon))

9h-9h45 I. Marcovici, Measures of maximal entropy of SFT on lattices and trees. [pdf]
9h45-10h30 T. Meyerovitch, On direct product factorization of homeomorphisms. [pdf]
10h30 Coffee break
11h-11h45 Y. de Cornulier, On topological full groups.
11h45-12h30 E. Jeandel, Communication Complexity for multidimensional subshifts. [pdf]
12h30 Lunch
14h00-14h45 A. Grandjean, Small aperiodic tilings and entropy. [pdf]
14h45-15h30 V. Salo, A few words on percolation properties of freezing monotone CA. [pdf]
15h30-16h30 P. Guillon & C. Zinoviadis, Hierarchy and expansiveness. [pdf]
16h30-?? Open discussions

Abstracts

  • Boris Adamczewski, Some decision problems around the Skolem-Mahler-Lech theorem.

  • The Skolem-Mahler-Lech theorem is classical result concerning the vanishing of linear recurrences over fields of characteristic zero. In this talk, I will discuss a joint result with Jason Bell inspired by analogous number theoretical questions over fields of positive characteristic. I will especially focus on some decision problems related to these questions.
  • Olivier Bournez, On The Hardness of Reachability for Dynamical Systems: Computability and Complexity.

  • The verification of a safety property of a dynamical system is equivalent to solving a reachability question for this system: can a trajectory starting from some possible initial state of the system reach a given set of bad states. The control of a discrete time dynamical system or the construction of a controller for a dynamical system often yield to universally quantified questions: are all trajectories starting from some initial state reaching a prescribed set of states. It is known that these properties are undecidable for systems as simple as piecewise affine systems, since it is known that such systems can simulate with arbitrary precision during an arbitrary long time a Turing machine. However, the complexity of these questions when restricting to a bounded time, or when doing computations with a fixed precision seems to be not known, despite their practical interest, and the fact that such restrictions are clearly decidable. We determine the exact complexity of many variants of reachability or control questions: for example, bounded time version is proved to $NP$-complete, bounded precision version to be $PSPACE$-complete, etc. This hence yields lower bounds on the complexity of building computer tool that would guarantee reachability or control properties of such systems. This is done technically by providing ways to simulate a Turing machine by various classes of dynamical systems.
  • Julien Cassaigne, SMART : a small aperiodic reversible Turing machine

  • We consider Turing machines in the moving tape model: the head is always at position 0, and at each step the tape is shifted to the left or to the right. A machine defines a dynamical system on the space of configurations A^Z x Q (contents of the tape and current state). Petr Kurka studied such systems in 1997, and conjectured that they always have a periodic configuration; we disproved that conjecture in 2002 with Vincent Blondel and Codrin Nichitiu, with a 6-state Turing machine. We present here a smaller Turing machine, with 4 states (and it is indeed the minimum possible size), which has the additional property of being reversible. This is joint work with Anahi Gajardo, Nicolas Ollinger and Rodrigo Torres.
  • Yves de Cornulier, On topological full groups

  • Topological groups are (discrete!) groups, defined as groups of self-homeomorphisms of a Cantor set that locally coincide with powers of a fixed minimal self-homeomorphism $\phi$. They provide interesting examples of finitely generated simple groups, keeping the memory of $\phi$ up to topological conjugacy. I'll describe some structural properties of these groups.
  • Anaël Grandjean, Small aperiodic tilings and entropy

  • J.Kari and K.Culik proposed small aperiodic tilings based on mealy machines. Those tilings seem to be structurally different from the existing ones. We study some properties of those tilings in order to better understand this difference. In particular, we show that the proposed 13-tiles tiling has positive entropy.
  • Emmanuel Hainry, Robust computation in perturbed dynamical systems.

  • We analyze the computational power of dynamical systems robust to infinitesimal perturbations. In the general case, reachability in dynamical systems is undecidable. However in practice, it is decidable for the dynamical systems that are encountered. One property that we believe is key to this discrepancy is that those "real world" dynamical systems exhibit robustness to infinitesimal perturbations. We will show that indeed for a large class of dynamical system, robustness implies non Turing completeness. We will also show the converse. In the end we obtain that robustness is equivalent to decidability.
  • Benjamin Hellouin, Possible asymptotic behaviors of cellular automata.

  • Cellular automata are models of computation as well as discrete dynamical systems. For this reason, we study, from a mathematical point of view, its dynamical properties, and from a computer science point of view, its computational limits. Of course these two aspects interact. In this talk, we consider the asymptotic behaviour of a 1D cellular automata starting from a random configuration, this behaviour being described by a limit probability measure. The computational limits of the model impose computatinal obstructions on the limit measure ; we show that this obstruction is really a caracterization. The proof requires to "program" cellular automata by having Turing machines run in the background to reach a target measure. If time allows, we will present different extensions and decidability consequences for some properties of cellular automata. This is a joint work with Mathieu Sablik.
  • Mathieu Hoyrup, Computability in ergodic theory.

  • I will talk about the problem of forecasting the asymptotic statistical behavior of a dynamical system, from a computability perspective. I will review the state of the art concerning the computability of invariant measures, the computability of the speed of convergence of Birkhoff averages. I will then present a recent result about the (non-)computability of the ergodic decomposition.
  • Emmanuel Jeandel, Communication Complexity for multidimensional subshifts.

  • In order to investigate which two-dimensional subshifts S are sofic, we introduce a new notion of complexity of infinite words: Assume Alice and Bob both have a biinfinite word a and b. How much information should they exchange to decide whether (a,b) is in S ? We will give the definitions of this new notion and a few properties, then present some open questions. This is joint work with P. Guillon.
  • Irène Marcovici, Measures of maximal entropy of SFT on lattices and trees

  • I will present a work in progress with Jean Mairesse and Vincent Delecroix. In one dimension, the measure of maximal entropy of a SFT is given by its Parry measure. We explore the properties of this measure, and show that it can be generated in different ways by independent draws of letters, with reject or deletion of forbidden patterns. We also extend the Parry measure to SFT defined on trees and show that it is related to the f-invariant of Bowen, which is a notion generalising the entropy to free group actions. Finally, we explain how the measures of maximal entropy of a SFT can be seen as reversible invariant measures of a probabilistic cellular automaton.
  • Tom Meyerovitch, On direct product factorization of homeomorphisms.

  • Let $T:X \to X$ be a homeomorphism of a compact space $X$. $T$ has a topological factorization into $S_1 :Y_1 \to Y_1$, $S_2:Y_2 \to Y_2$ if there exists an isomorphism $T \cong S_1 \times S_2$, namely a homeomorphism $\phi:Y_1 \times Y_2 \to X$ so that $T(\phi(y_1,y_2))=\phi(S_1y_1,S_2y_2)$. Similarly, one defines the topological factorization of a group action by homeomorphisms. Call a homeomorphism $T$ topologically prime if it has only trivial topological factorizations. In the early 1980's Lind studied topological factorizations for shifts of finite type, and related them to a factorizations of certain algebraic integers. In particular non-uniqueness of factorization was demonstrated. It turns out that existence of a direct topological factorization into primes is implied in general by expansiveness - a well known dynamical property. As time allows, I will show certain new examples of topologically prime systems, including some multidimensional shifts of finite type and non-sofic one dimensional subshifts. To establish such topological primeness results various obstructions to topological factorizations are utilized. These include the $\mathbb{R}$-valued cohomology and local entropy of periodic points.
  • Thierry Monteil, Quantifying the aperiodicity of a Wang tile set.

  • A (Wang) tile set is a finite set of unit squares where each edge got a color. A tile set T tiles the plane if the plane can be covered by Z^2-translated copies of elements of T, where two adjacent edges must have the same color. A tile set is aperiodic if it tiles the plane, but if this can not be done in a periodic way. Most aperiodic tilings are obtained from a substitution process. We introduce two invariants to quantify the level of aperiodicity of a Wang tile set. One is topological, the other is metric. They both rely on the way a tile set tile can tile other objects than the plane. Those invariants allow to prove that the tile sets of Kari and Culik are not ruled by a substitution process.
  • Ville Salo, A few words on percolation properties of freezing monotone CA

  • We study the question of which Bernoulli measures converge to Dirac measures in the action of freezing and/or monotone CA, that is, cellular automata that can only increase the value of each cell and/or are monotone with respect to this cellwise order. We show a simple procedure for deciding the existence of a nontrivial Bernoulli measure that converges to a Dirac measure in the case of a binary freezing monotone CA, give a class of rules where the critical probability for converging to a Dirac measure is nontrivial, and show that freezing CA need not be monotone on measures in the limit. This is joint work with Guillaume Theyssier and Ilkka Törmä.
  • Pierre Guillon & Charalampos Zinoviadis, Hierarchy and expansiveness

  • We present a hierarchical construction of 2D subshifts of finite type with a unique direction of non-expansiveness. This allows to embed computation self-similarly in such SFT, and in particular obtain the undecidability of the emptiness problem, as well as some kind of intrinsic universality.

Venue

The workshop will take place at ENS de Lyon (Monod site). You can find more instructions here.