Abstracts

Laurent Bienvenu : The interplay between randomness and genericity

In computability theory, one often think of (Cohen)-genericity and algorithmic randomness as orthogonal notions: a truly random real will look very non-generic, and a truly generic real will look very non-random. This orthogonality is best incarnated by the result of Nies, Stephan and Terwijn that any 2-random real and 2-generic real form a minimal pair for Turing reducibility. On the other hand, we know from the Kucera-Gacs theorem that for any n there is a 1-random real which computes an n-generic one, but also (and more surprisingly), by a result of Kautz that every 2-random real computes a 1-generic real. These last two results tell us that the interplay between randomness and genericity is rather complex when “randomness” is between 1-random and 2-random or “genericity” between 1-generic and 2-generic. It is this gray area that we will discuss in this talk (based on the paper of the same title, joint work with Chris Porter).

Djamel Eddine Amir : Spaces with strong computable type

Spaces with strong computable type - Abstract

Quentin Guilmant : Nombres surréels, intégration, calculs

Les nombres surréels forment une classe de nombres étendant les nombres réels et contenants les ordinaux. Depuis leur introduction par J.H. Conway, beaucoup de travaux ont été faits. En particulier, nous savons que les opérations sur les nombres surréels en font un corps réel-clos universel et qu'il est possible de les représenter sous multiples formes (séries de Hahn, suites de signes, coupures à la Dedekind). Il existe de plus une notion de fonctions exponentielle et logarithmique sur ces nombres, ce qui en fait un corps encore plus intéressant. Enfin, ces dernière années, Berraducci et Mantova ont développé une notion de dérivation des nombres surréels. Cette dérivation est à comparer à celles des corps de Hardy de part l'universalité de la classe des surréels en tant que corps ordonné. 

Notre travail s’intéresse à des sous-corps stables « raisonnables » des nombres surréels. En effet, l'utilisation d'une classe propre ne fait pas vraiment de sens du point de vue de la calculabilité. Nos résultats montrent qu'il existe des corps réels-clos, stables par l'exponentielle, le logarithme, la dérivation mais aussi l'anti dérivation. L'ambition à plus long terme étant de pouvoir établir un lien entre ce système différentiel et le calcul par un ordinateur analogique, qui nécessite de savoir intégrer. 

Cet exposé propose d'introduire les surréels et leurs opérations et d'exposer comment il est possible de les contrôler pour envisager un calcul via machines à temps ordinal.

Benjamin Hellouin : Difficulté du domino apériodique en (presque) toute dimension

La calculabilité dans les pavages a commencé avec le problème du domino : étant donné un jeu de tuiles, existe-t-il un pavage du plan ? La construction d'espaces de pavages apériodiques, et plus généralement des considérations d'(a)périodicité ont défini en profondeur ce domaine de recherche.

On peut naturellement se demander si chercher spécifiquement des pavages (a)périodiques est plus ou moins difficile que le problème de base. Il s'avère que le cas apériodique est significativement différent : le domino est r.e. en général, alors que le domino apériodique peut échapper à la hiérarchie arithmétique.

Je ferai un panorama de deux résultats: en dimension 2, le problème est co-r.e-complet ; en dimension > 3, il est hors de la hiérarchie arithmétique. Le cas de la dimension 3 est ouvert. Pour les amateurs de dynamique symbolique, le saut de difficulté dans le cas sofic est exactement entre les dimensions 2 et 3.

Cet exposé est issu de collaborations successives avec Antonin Callard, Anael Grandjean et Pascal Vanier.

Benoit Monin : The computational content of Milliken’s tree theorem

 The Milliken’s tree theorem is an extension of Ramsey’s theorem to trees. It implies for instance that if we assign to all the sets of two strings of the same length, one mong k colors, there is an infinite binary tree within which every pair of strings of the same height has the same color. We are going to present some results on Milliken’s tree theorem from the viewpoint of computability theory and reverse mathematics.