English
On centauric subshifts
Multi angle
Auteurs : Romashchenko, Andrei (Auteur de la Conférence)
CIRM (Editeur )
03B80 - Other applications of logic
68Q30 - Algorithmic information theory (Kolmogorov complexity, etc.)
CIRM (Editeur )
Loading the player...
|
Résumé :
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).
Codes MSC : 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).
03B80 - Other applications of logic
68Q30 - Algorithmic information theory (Kolmogorov complexity, etc.)
|
Informations sur la Vidéo
Réalisateur : Hennenfent, GuillaumeLangue : Anglais Date de publication : 06/07/2016 Date de captation : 22/06/2016 Sous collection : Research talks arXiv category : Computer Science ; Logic in Computer Science ; Discrete Mathematics Domaine : Computer Science ; Logic and Foundations Format : MP4 (.mp4) - HD Durée : 01:05:07 Audience : Researchers Download : https://videos.cirm-math.fr/2016-06-22_Romashchenko.mp4 
|
Informations sur la Rencontre
Nom de la rencontre : Computability, randomness and applications / Calculabilité, hasard et leurs applicationsOrganisateurs de la rencontre : Bienvenu, Laurent ; Jeandel, Emmanuel ; Porter, Christopher Dates : 20/06/2016 - 24/06/2016 Année de la rencontre : 2016 URL Congrès : http://conferences.cirm-math.fr/1408.html
Données de citation
DOI : 10.24350/CIRM.V.19006203Citer cette vidéo: Romashchenko, Andrei (2016). On centauric subshifts. CIRM. Audiovisual resource. doi:10.24350/CIRM.V.19006203 URI : http://dx.doi.org/10.24350/CIRM.V.19006203 |
Voir aussi
- [Multi angle] Randomness connecting to set theory and to reverse mathematics / Auteur de la Conférence Nies, André.
- [Multi angle] A derivation on the field of d.c.e.reals / Auteur de la Conférence Miller, Joseph.
- [Multi angle] Carleson's Theorem and Schnorr randomness / Auteur de la Conférence Franklin, Johanna.
- [Multi angle] Independence of normal words / Auteur de la Conférence Becher, Verónica.
Bibliographie
- [1] Ballier, A. (2009). Propriétés structurelles, combinatoires et logiques des pavages. Thèse de doctorat. Marseille : Université d'Aix-Marseille, 2009, 137 p. - http://pageperso.lif.univ-mrs.fr/~alexis.ballier/these/these.pdf
- [2] Ballier, A., & Jeandel, E. (2010). Computing (or not) quasi-periodicity functions of tilings. In J. Kari (Ed.), Proceedings of JAC 2010 (pp. 54–64). Turku: Turku Center for Computer Science - https://www.doria.fi/bitstream/handle/10024/66298/LN13.digi.pdf
- [3] Jeandel, E., & Vanier, P. (2013). Turing degrees of multidimensional SFTs. Theoretical Computer Science, 505 (2013), 81–92 - http://dx.doi.org/10.1016/j.tcs.2012.08.027
- [4] Hochman, M., & Vanier, P. (2014). Turing degree spectra of minimal subshifts.
- [5] Durand, B., & Romashchenko, A. (2015). Quasiperiodicity and non-computability in tilings. In G.F. Italiano, G. Pighizzini, & D.T. Sannella (Eds.), Mathematical foundations of computer science 2015, Part 1 (pp. 218–230). Berlin: Springer - http://www.springer.com/gb/book/9783662480564
