ALGORITHMIC QUESTIONS IN DYNAMICAL SYSTEMS

From 26 to 29 march in Toulouse

Presentation

The theoretical study of the computational challenges involved in the simulation of dynamical systems has seen an enormous increase in the last decades, and even more so as the logical limitations of the computer, when dealing with the numerical calculations of dynamical objects, have started to become increasingly apparent.
This workshop will bring together experts interested in these computational challenges in a variety of dynamical systems including symbolic, smooth and complex dynamical systems. The goal will be to exchange questions, ideas, techniques and results, as well as to promote collaboration in view of the significant development of the field in the next years.

Program

Place of the meeting

Institut de Mathématiques de Toulouse, Amphithéâtre Laurent Schwartz, Bâtiment 1R3. More details here.

Registration

There is no registration fee, but in order to organise the logistics, we kindly request interested people to register before 5 March, by sending an email to Cristobal Rojas (crojas at mat-unab dot cl) or Mathieu Sablik (mathieu.sablik at math.univ-toulouse dot fr).

Submission of talks

Proposed talks are welcome. If you are interested please submit a short abstract to Cristobal Rojas (crojas at mat-unab dot cl) or Mathieu Sablik (mathieu.sablik at math.univ-toulouse dot fr). Time and seminar rooms for informal discussions will also be planned.

Speakers

Schedule

Lundi Mardi Mercredi Jeudi
9h40-10h30 Hellouin Bournez Nies Ouazzani
10h30-11h Pause café
11h-11h50 Torma Dudko Graça Durand-Lose
12h-14h Repas
14h-14h50 Hoyrup Galatolo Vanier Gangloff
15h-15h50 Wolf Schneider Barbieri Labbé
15h50-16h20 Pause café
16h20-17h10 Theyssier Stull Guillon Free Discussion
17h10-18h30 Free Discussion Free Discussion Free Discussion Free Discussion

Abstracts

Sebastian Barbieri: A strongly aperiodic SFT in the Grigorchuk group [PDF]
An action of a finitely generated group over a Cantor set is called effectively closed if there is a Turing machine which recieves as input a cylinder and a generator and computes an effective aproximation of the complement of the image of such cylinder under the generator. I will show that every effectively closed action of a finitely generated group $G$ can be realized as a factor of the $G$-subaction of an SFT in $G \times H_1 \times H_2$ for any pair of infinite f.g. groups $H_1,H_2$. As a corollary we obtain that any group of the form $G_1 \times G_2 \times G_3$ admits a strongly aperiodic SFT whenever all the $G_i$ are finitely generated and have decidable word problem. In particular, we show how this theorem implies the existence of strongly aperiodic SFTs in the Grigorchuk group.
Olivier Bournez: Computing with Chemical Reaction Networks [PDF]
Bioinformatics has many contexts where some agents can be considered as doing computations. For example, cells compute, in the sense that they process signals, they regulate their metabolism, and they take actions similar to decisions such as division, differentiation or migration. For a large part, this can be seen as a kind of model of computation, based on analog computations with proteins.
Models to describe these dynamics are based on biochemical reaction networks (CRN). We will review the basic approaches to describe such systems, and then discuss how this relates to some other models of computation, i.e. how this relates to continuous time analog models of computation such as the GPAC (general purpose analog computer) from Claude Shannon, but also classical models such as Turing machines. We will do it both at the computability and complexity levels, and we will discuss the associated challenges.
We will also relate this to prototypes that have been programed or tested experimentally, and that can be experienced online.
Artem Dudko: On the Lebesgue measure of the Feigenbaum Julia set [PDF]
Using computer-assisted means with explicit bounds on errors we show that the Julia set of the Feigenbaum polynomial has Hausdorff dimension less than 2 (and consequently it has zero Lebesgue measure). This solves a long-standing open question. The talk is based on a joint work with Scott Sutherland.
Jérôme Durand-Loze: Simulation between signal machines [PDF]
In this talk, we first recall the origin and definition of signal machines. Then, as an illustrative example, we show how they can simulate both Turing and linear Blum, Shub and Smale machines. The second part of the talk is the construction of a signal machine that is able to simulate any signal machine whose speed belongs to a given finite set of reals. The last part of the talk presents how to simulate a non-deterministic signal machine with a regular (deterministic) one.
Stefano Galatolo: Computer aided results in ergodic theory and Existence of Noise Induced Order
Having rigorous quantitative information about the statistical properties of dynamics is not easy. One of the reasons is that the interesting systems for which we can have a direct analytical way of computing the invariant measure of interest are very few. The use of computers and certified computation techniques can help much in extending our knowledge of these statistical properties in many interesting systems. After a short overview about the rigorous computational methods for this kind of problems, we see how a computer aided proof can rigorously show the existence of noise induced order. This is a phenomenon firstly discovered by simulations of models of chaotic chemical reactions and then confirmed by real experiments. The system behavior appears to be less chaotic and more stable when a certain quantity of noise is added. We show that in the original model of Matsumoto and Tsuda, consisting in a random dynamical system, the addition of noise causes the Lyapunov exponent to decrease from positive to negative. The method is based on a certified approximation of the stationary measure in the L¹ norm. This is done by an efficient algorithm which is general enough to be adapted to any dynamical system with additive noise on the interval.
Silvère Gangloff: Computability of growth type invariants of Z^d SFTs under dynamical constraints.
Subshifts of finite type are symbolic dynamical systems which are adapted to the study of the interplay between computability and dynamics. For instance, Mike Hochman and Tom Meyerovitch proved a characterization of the entropies of multidimensional SFT with a computability condition. The proof of this result uses an implementation of computing machines into hierarchical structures that appear in some aperiodic SFT, in order to control the frequency of some random bits that generate the entropy. In their paper, they expressed the question of the adaptability of their construction to transitivity condition. This is indeed adaptable, and I will provide the main principles for some adaptation of the general scheme of this construction in order to ensure some dynamical constraints such as transitivity or minimality. This is a joint work with Mathieu Sablik.
Daniel Graça Computing the asymptotic behavior of low-dimensional dynamical systems [PDF]
In this talk we will survey some computability results and problems about the asymptotic behavior of low-dimensional systems. Namely we will consider dynamical systems defined by ordinary differential equations in the plane and in the three dimensional space. We will present results about the computability of basins of attractor and, more generally, of the stable and unstable manifolds. We will also present a computable version of the classical Hartman-Grobman theorem, and we will analyze the computability of the Lorenz attractor.
Pierre Guillon: Soficité de sous-shifts à composantes connexes contraintes.
Soit un alphabet A et 0∈A. Une configuration x∈A^ℤ² est constituée de "composantes connexes" de cellules dans A\{0}. On se demande si l'on peut représenter par contraintes locales et projection (soficité) l'ensemble des configurations dont on contraint les coloriages de ces composantes connexes finies par un langage abélien.
Par exemple, il est connu que le sous-shift des configurations dont les composantes connexes finies sont de taille paire est sofique, et par une construction de Julien Cassaigne en 2010, la même chose pour une taille impaire. Nous généralisons aux langages abéliens rationnels.
Travail en collaboration avec Julien Cassaigne.
Benjamin Hellouin: A tour on computation, decision and prediction in symbolic dynamical systems [PDF]
This talk is meant as an introduction to the translation between the computational and the dynamical point of view in some of the simplest cases: symbolic and discrete-time systems.
Starting from the standard Turing machine, I will show how classical decision problems can be expressed as natural properties of the corresponding dynamical system, and generalised to other systems. Taking cellular automata as a second example, I will consider various points of view regarding the prediction of long-term behaviour. Most of them turn out to be undecidable problems, but proving so requires different methods for embedding universal computation inside the system, leading to different notions of Turing-universality.
I will then exhibit some (proved or conjectural) situations where some form of long-term prediction is decidable, for systems that are Turing-universal in a different sense. In a sense, these conflicting notions challenge the common intuition that "every interesting property of Turing-universal systems is undecidable".
Mathieu Hoyrup: Computability of invariant measures [pdf]
Invariant measures are a classical way of describing the long-term statistical behavior of a dynamical system. We study the possibility of computing those invariant measures, especially the ergodic ones, assuming that the step-by-step evolution of the dynamical system can be computed. I will present several results obtained in recent years on this problem.
Sébastien Labbé: On Jeandel-Rao aperiodic tiling [PDF]
In 2015, Jeandel and Rao showed by exhaustive computer search that every Wang tile set of cardinality <=10 either (1) admit a periodic tiling of the plane or (2) admit no tiling of the plane at all. Moreover, they found a Wang tile set of cardinality 11 which admits tilings of the plane but never periodically. In this talk, we present an alternative definition of the aperiodic tilings of Jeandel-Rao as the coding of a $\mathbb{Z}^2$-action on the torus. We conjecture that it is a complete characterization.
Andre Nies: Quantum Martin-Loef randomness and the Shannon-McMillan-Breiman Theorem [PDF]
We consider states on the CAR algebra that can be interpreted as infinite sequences of qubits, or, more generally, of density matrices. We introduce an algorithmic notion of randomness for such states relative to a computable ergodic state (an analog of a computable ergodic measure). Then we consider the question whether a quantum analog of the effective Shannon-McMillan-Breiman theorem holds for such states. We prove it in the case where the ergodic state is i.i.d., corresponding to a computable Bernoulli measure.
Joint works with Volkher Scholz, and with Marco Tomamichel.
Sabrina Ouazzani: Computing to the infinite with Ordinary Differential Equations [PDF]
In this talk, we present a class of differential equations that are equivalent to some transfinite time computation models and how they relate to each other.
We consider Continuous Ordinary Differential Equations (CODE). That is to say equations $x'=f(x)$, where $f: \R^n \to \R^n$ is a continuous function. Such ordinary equations are known to always have solutions for a given initial condition $x(0)=x_0$, these solutions being possibly non unique. We restrict our attention to the class of continuous functions such that for all $x_0$, the trajectory starting from $x_0$ is either locally constant, or with a specific property of local forward uniqueness. This class includes all common examples of functions, as well as all classical functions usually considered in mathematics as counterexamples related to unicity of solutions.
After having recalled the main results about Infinite Time Turing Machines (ITTM), we then prove the rather unexpected following result: CODE can be seen as models of computation over the ordinals (ITTM) and conversely in a very strong sense. More specifically, this implies the next statements: To trajectories an ordinal can be associated, corresponding to some ordinal time of computation, and conversely.
Jon Schneider: Tight space-noise tradeoffs in computing the ergodic measure
In this work we obtain tight bounds on the space-complexity of computing the ergodic measure of a low-dimensional discrete-time dynamical system affected by Gaussian noise. If the scale of the noise is ε, and the function describing the evolution of the system is not by itself a source of computational complexity, then the density function of the ergodic measure can be approximated within precision δ in space polynomial in log1/ε+loglog1/δ. We also show that this bound is tight up to polynomial factors.
In the course of showing the above, we prove a result of independent interest in space-bounded computation: that it is possible to exponentiate an n by n matrix to an exponentially large power in space polylogarithmic in n.
Joint work with Mark Braverman (Princeton University, USA) and Cristóbal Rojas (Universidad Andres Bello, Chile).
Donald Stull: Projection Theorems using Effective Dimension [PDF]
In this talk we will discuss recent work, joint with Neil Lutz, which uses tools from computability theory to study problems in fractal geometry. Specifically, we will focus on the Hausdorff dimension of projections of Euclidean sets. Using the Kolmogorov complexity characterization of effective dimension and the point-to-set principle, we will prove two new theorems giving lower bounds on the Hausdorff dimension of projected sets. In this talk we will give an overview of this approach, and discuss new research directions.
Guillaume Theyssier: Revisiting circuits embeddings in cellular automata.
TBD
Ilkka Torma: Physical universality in cellular automata and beyond [PDF]
This talk concerns physical universality in cellular automata, which intuitively means that one can perform arbitrary manipulations on finite regions of the configuration space using the dynamics of the automaton. The concept of physical universality was introduced by Janzing, and Schaeffer later proved the existence of a two-dimensional physically universal cellular automaton. Together with Salo, we modified the example into a one-dimensional physically universal cellular automaton. I present these examples and others, and discuss the implications of physical universality for the computational and dynamical properties of the automaton. I also outline possible generalizations beyond cellular automata.
Pascal Vanier: Higman type theorems for subshifts [PDF]
Subshifts are sets of colorings of Z² by a finite alphabet that avoid some family of forbidden patterns. We investigate here some analogies with group theory that were first noticed by Emmanuel Jeandel. In particular we will show theorems on subshifts inspired by Higman's embedding theorems of group theory, among which, the fact that subshifts with a computable language can be obtained as restrictions of minimal subshifts of finite type.
This is joint work with Emmanuel Jeandel.
Christian Wolf: Computability of thermodynamic invariants: pressure, entropy and zero-temperature measures [PDF]
The topological pressure has been a powerful tool in the development of the theory of dynamical systems, in part since it naturally connects topological and measure-theoretic dynamics. A particular useful feature of the topological pressure is that it identifies several natural invariant measures as equilibrium states of certain continuous potentials. In this talk, we discuss the computability of certain invariants that are linked via the topological pressure. In particular, we establish computability criteria for generalized rotation sets, localized entropies and zero-temperature measures. We then apply these criteria to subshifts of finite type. For example, one of our results shows that the localized entropy function (i.e. the entropy spectrum) is computable on the interior of the generalized rotation set but in general not on its boundary. This is joint work with Michael Burr and Martin Schmoll.
Michael Yampolsky:Computational Intractability of attractors in the real quadratic family
We show that there exist real quadratic maps of the interval whose attractors are computationally intractable. This is the first known class of such natural examples.

Pratical information

Getting to IMT

IMT's address is the following :
118 Route de Narbonne
31062
Toulouse

The nearest Metro Station is "Université Paul Sabatier" on the yellow metro line (Metro B).

From the Airport : You can :

From the station "Gare Matabiau" :

Take the metro line A (red line) in direction "Basso Cambo" and get down at "Jean Jaurés" (just one stop) then change and take the metro line B (yellow line) in direction "Ramonville" and get down at "Université Paul Sabatier".

Once you are at the metro station "Université Paul Sabatier", you are at approximately 200 m from IMT : the main building of IMT is the building 1R2, in the grid of the campus map it is in the square C4. See the map of the campus here below :

Plan of the Campus

The closest airport is Toulouse Blagnac (TLS), with many flights to european cities and a few intercontinental ones. The centre is conveniently reached with the airport shuttle.
The university can be reached using the Metro B line, stop at "Université Paul Sabatier"; the maths department is in buildings 1R1,1R2,1R3.

Some accomodations in Toulouse

Here is a list of hotels in Toulouse that should have vacancies:

Most hotels are located north of the city centre, while the University is located south east. You will need to use public transport, especially the tube/subway, as there is a very convenient stop "Université Paul Sabatier" on line B, just 200m far from the Math Institute. Information about transport can be found on Tisseo website, see https://www.tisseo.fr/se-deplacer/horaires/metro

More information about the transport from the airport or the train station can be found on the information webpage of the CIMI.

Support

Financial support

Organizers