Degrés Turing dans les sous-shifts minimaux

Orateur: VANIER Pascal
Localisation: Université Paris-Est - Créteil, France
Type: Séminaire cristolien d'analyse multifractale
Site: UPEC
Salle: Salle des thèses
Date de début: 05/01/2017 - 15:00
Date de fin: 05/01/2017 - 15:00

Les sous-shifts sont des sous-ensembles de $\mathbb Z^d$ fermés invariants par translation, ou de manière équivalente, définissables par une famille de motifs interdits. Un sous-shift est minimal si il ne contient proprement aucun autre sous-shift, tous les sous-shifts contiennent donc un sous-shift minimal. Nous nous intéressons ici à la structure calculatoire de ces sous-shifts et en particulier à la structure de leurs ensembles de degrés Turing. Le degré Turing est une des mesures de la difficulté de calculer/produire un point. Nous commencerons par une introduction aux sous-shifts et à la calculabilité.