Higher computability and randomnes
Benoît Monin · 2014
Dans cette these, nous traitons principalement des notions d'aleatoirite d'ordre superieur, notamment les notions de Delta ^1_1-aleatoirite, de Pi^1_1-Martin-Lof aleatoirite, de Pi^1_1- aleatoirite faible, et de Pi^1_1-aleatoirite, en mettant plus particulierement l'accent sur cette derniere notion : la Pi^1_1-aleatoirite. L'etude de ces notions d'aleatoirite souleve plusieurs problematiques. Nous essayons notamment de comprendre les similarites et les differences entre toutes ces notions, mais aussi entre ces notions et les notions d'aleatoirites classiques, largement etudiees ces quinze dernieres annees. Une difference importante entre les notions de calculabilite/aleatoirite d'ordre superieur et les notions de calculabilite/aleatoirite classique est de nature topologique. Aussi nous avons concentre nos efforts sur trois des phenomenes a travers lesquels cette difference s'exprime : Dans la notion de calcul, dans la notion d'aleatoire relatif, et dans la notion d'approchabilite. Nous soulignons egalement les liens etroits entre la notion d'aleatoirite et celle de genericite, que l'on peut considerer comme une version categorique (au sens de Baire) d'aleatoirite. Pour cette raison, nous etudions aussi la categoricite effective d'ordre superieur et nous mettons en avant les differences et similarites qu'elle presente avec la notion d'aleatoirite.