Français
On centauric subshifts
Multi angle
Authors : Romashchenko, Andrei (Author of the conference)
CIRM (Publisher )
03B80 - Other applications of logic
68Q30 - Algorithmic information theory (Kolmogorov complexity, etc.)
CIRM (Publisher )
Loading the player...
|
Abstract :
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).
MSC Codes : 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.)
|
Information on the Video
Film maker : Hennenfent, GuillaumeLanguage : English Available date : 06/07/2016 Conference Date : 22/06/2016 Subseries : Research talks arXiv category : Computer Science ; Logic in Computer Science ; Discrete Mathematics Mathematical Area(s) : Computer Science ; Logic and Foundations Format : MP4 (.mp4) - HD Video Time : 01:05:07 Targeted Audience : Researchers Download : https://videos.cirm-math.fr/2016-06-22_Romashchenko.mp4 
|
Information on the Event
Event Title : Computability, randomness and applications / Calculabilité, hasard et leurs applicationsEvent Organizers : Bienvenu, Laurent ; Jeandel, Emmanuel ; Porter, Christopher Dates : 20/06/2016 - 24/06/2016 Event Year : 2016 Event URL : http://conferences.cirm-math.fr/1408.html
Citation Data
DOI : 10.24350/CIRM.V.19006203Cite this video as: 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 |
See Also
- [Multi angle] Randomness connecting to set theory and to reverse mathematics / Author of the conference Nies, André.
- [Multi angle] A derivation on the field of d.c.e.reals / Author of the conference Miller, Joseph.
- [Multi angle] Carleson's Theorem and Schnorr randomness / Author of the conference Franklin, Johanna.
- [Multi angle] Independence of normal words / Author of the conference Becher, Verónica.
Bibliography
- [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
