Degrés Turing des pavages


Pascal Vanier, LIF, Marseille. 29 mars 2012 10:00 limd 2:00:00
Abstract:

Dans cet exposé, on étudie les ensembles de degrés Turing associés aux pavages générés par un jeu de tuile. En particulier, on prouve qu'il existe un quasi-isomorphisme entre n'importe quelle classe Pi01 de {0,1}^N et un pavage. Pour cela, on introduit une construction permettant d'avoir du calcul tout en ayant un nombre dénombrable de pavages.