Math-Info 2010

Towards new interactions between mathematics and computer science


Invited Seminars

Thematic month

The five weeks

Dynamics And Computation

1.  Dates

From February 8 to February 12, 2010.

2.  Description of the week

Computer simulations of a dynamical system may help better understand its behavior, and some new conjectures may thus arise. Scientists are then confronted with the problem of simulating continuous dynamical systems, which leads to computability questions on real numbers. For example, which invariants (e.g. entropy) of continuous dynamical systems are computable? In this week, computability theory and effective simulation will be seen as tools for the study of dynamical systems.

3.  Abstracts of the morning lectures (4h30 each)

Abstract: We will provide an overview of theories of computation for analog models of computation, focusing mainly on continuous time models of computation. These theories allow us to understand both the hardness of questions related to continuous time dynamical systems and the computational power of analog models. We will survey some existing models like the General Purpose Analog Computer of Claude Shannon, or the R-recursive model proposed by Cris Moore, some Hybrid System models used in verification. We will recall some of their properties. Will see that all of them correspond to particular classes of continuous time dynamical systems. We will discuss how such models can be compared. We will survey results about comparing the computational power of these continuous time models to classical discrete time models in theoretical computer science, in particular to Turing machines, or to recursive analysis. We will also discuss some questions related to the hardness of their verification, and we will present some open problems.
Abstract: Cellular automata are the most natural theoretical model in which to pose the problem of computing reliably. First since they possess parallelism, which is necessary to deal with noise of constant intensity. Second, due to their space-time homogeneity it is arguable that no structure has been taken for granted, other than the elementary geometrical properties of space and the "physics" or "chemistry" defining the transition function.
In the lectures, I will tell the story of constructing reliable cellular automata. I will start with the simplest model, a three-dimensional one that can be defined easily, though the proof that it works is nontrivial. Then I will outline the construction of a one-dimensional reliable cellular automaton. This is a complex hierarchical construction, and the exposition will focus on the main ideas.
  • Mike Hochman: Recursion theory, computation and {{$\mathbb{Z}^d$}} actions on Cantor space
Abstract: I will describe results from the past few years, and some open questions, concerning the nature of higher rank actions on the Cantor set, and particularly symbolic dynamics and Wang tiling systems. As time permits we will cover some or all of the following topics:
- Effective dynamical systems and recursive invariants, Simpson's realization theorem for Medvedev degrees, implications for studying factorization in multidimensional symbolic dynamics.
- Subdynamics of higher-rank shifts of finite type (Wang tile systems) and sofic shifts, realization theorem for effective systems, obstructions to precise realization.
- Approximation in the space of {{$\mathbb{Z}^d$}} actions, obstruction to effective approximation, and the role of SFTs. The main result is that "most" {{$\mathbb{Z}^d$}} minimal actions cannot be approximated by effective minimal actions (in {{$\mathbb{Z}^2$}} this is always possible).
- Open problems. I will focus on problems which arise when trying to determine if certain natural examples of symbolic systems are sofic systems or not. This question is closely related to some problems in synchronization and computation.

4.  Schedule of the morning lectures

11h-12h30BournezGacsBournez Hochman 
16h-17h   Hochman  

5.  Proposed workshops (add your suggestions here)

  • C. Bonanno. Entropy and PDE.
  • A. Goetz."Piecewise isometries". See
  • Mathieu Hoyrup and Cristobal Rojas: "Computability in ergodic theorems"
  • Petr Kurka: "Exact real arithmetic based on Moebius number systems" Moebius number systems generalize both positional and continued fraction systems. Real numbers are represented by sequences of Moebius transformations. If the system is redundant, efficient algorithms for exact real arithmetic exist.
  • S. Simpson: "Medvedev and Muchnik degrees of subshifts".
  • P. Collins: "Computable Analysis and Nonlinear Dynamics"

6.  General Schedule (will be updated every night)

  • Monday 8th
    • 9h00-10h30 : Péter Gács - Reliable computation with cellular automata I.
    • 11h00-12h30 : Olivier Bournez - Analog Models of Computations I.
    • 14h45-15h00 : Workshop organization.
    • 15h00-16h30 : Cristobal Rojas and Mathieu Hoyrup - Computability in ergodic theorems.
    • 17h00-18h00 : Cristobal Rojas and Mathieu Hoyrup - Back to basics in ergodic theory.
    • 18h00-19h30 : Apéritif at IML.
  • Tuesday 9th
    • 9h00-10h30 : Olivier Bournez - Analog Models of Computations II.
    • 11h00-12h30 : Péter Gács - Reliable computation with cellular automata II.
    • 15h15-16h15 : L. Bienvenu - Introduction to Algorithmic Randomness and Kolmogorov Complexity
    • 16h30-17h30: Two parallel sessions:
      • B. Schratzberger - Singularisation of continued fraction algorithms (relocation of Ernest seminar at Chapelle)
      • C. Rojas - Computability of Invariant Measures
    • 18h00-19h00: C. Bonanno - Applications of Kolmogorov complexity to dynamical systems
  • Wednesday 10th
    • 9h00-10h30 : Péter Gács - Reliable computation with cellular automata III.
    • 11h00-12h30 : Olivier Bournez - Analog Models of Computations III.
    • 16h15-17h15 : proposed by A. Shen / suggested speakers P. Gacs, M. Hoyrup, C. Rojas - Randomness in general spaces and uniform tests of randomness.
    • 17h30-18h30: F. Blanchard - Chaos: stronger definitions of the butterfly effect (sensitivity)
    • 18h30-19h30: Petr Kurka - Möbius number system
  • Thursday 11th
    • 9h00-9h50 : P. Collins - Computable analysis and nonlinear dynamics: Introductory talk.
    • 10h00-10h50 : A. Goetz - Piecewise isometries - two dimensional generalizations of interval exchanges: Introductory talk.
    • 11h30-12h30 : Two parallel sessions
      • P. Collins - Computable analysis and nonlinear dynamics: Informal discussions.
      • A. Goetz - Piecewise isometries - two dimensional generalizations of interval exchanges: Informal discussions.
    • 14h30-15h30 : S. Capobianco - Enforcing reversibility in cellular automata or Computer without batteries? Rewriting cellular automata as block automata or both
    • 16h00-18h00 : M. Hochman - Recursion theory, computation and Zd actions on Cantor space I. Live from Princeton.
  • Friday 12th
    • 9h00-10h30 : S. Simpson - Mass problem, Medvedev degrees, Muchnik degrees, applied to symbolic dynamics.
    • 10h45-12h15: Mike Hochman - Recursion theory, computation and Zd actions on Cantor space II.Live from Princeton.
    • 14h-15h : C. Jadur and J. Yazlle - Finite codes in cellular automata.
    • 15h30-17h A. Shen - Every one dimensional effectively closed subshift is a projection of two dimensional finite type subshift.

7.  Currently uploaded slides

8.  Participants

See the page Dynamics And Computation Participants


For any technical question or comment regarding this wiki, you can contact the wemaster.