Computability, randomness and applications / Calculabilité, hasard et leurs applications

Collection Computability, randomness and applications / Calculabilité, hasard et leurs applications

Organizer(s) Bienvenu, Laurent ; Jeandel, Emmanuel ; Porter, Christopher
Date(s) 20/06/2016 - 24/06/2016
linked URL http://conferences.cirm-math.fr/1408.html
00:00:00 / 00:00:00
3 5

On centauric subshifts

By Andrei Romashchenko

Also appears in collection : Exposés de recherche

We discuss subshifts of finite type (tilings) that combine virtually opposite properties, being at once very simple and very complex. On the one hand, the combinatorial structure of these subshifts is rather simple: we require that all their configurations are quasiperiodic, or even that all configurations contain exactly the same finite patterns (in the last case a subshift is transitive, i.e., irreducible as a dynamical system). On the other hand, these subshifts are complex in the sense of computability theory: all their configurations are non periodic or even non-computable, or all their finite patterns have high Kolmogorov complexity, the Turing degree spectrum is rather sophisticated, etc. We start with the simplest example of such centaurisme with an SFT that is minimal and contains only aperiodic (and quasiperiodic) configurations. Then we discuss how far these heterogeneous properties can be strengthened without getting mutually exclusive. This is a joint work with Bruno Durand (Univ. de Montpellier).

Information about the video

Citation data

Bibliography

Last related questions on MathOverflow

You have to connect your Carmin.tv account with mathoverflow to add question

Ask a question on MathOverflow




Register

  • Bookmark videos
  • Add videos to see later &
    keep your browsing history
  • Comment with the scientific
    community
  • Get notification updates
    for your favorite subjects
Give feedback