Higher computability and randomnes
Institution:
Paris 7Disciplines:
Directors:
Abstract EN:
We mainly deal with higher randomness notions, that is, Delta^1_1-randomnes, Pi^1_1-Martin-Löf randomness, weak-Pi^1_1-randomness and especially Pi^1_1-randomness. We also try to understand the similarities and differences between all those higher randomness notions, but also between the classical randomness notions and the higher ones. One important difference between the notions of higher computability/randomness and their classical counterparts, is of topological nature. Also we have concentrated our efforts on three different concepts for which this topological difference arises : The notion of computation, the notion of relativization of randomness and the notion of approximation. We also emphasize the tight connection between randomness and the genercity notions, as we can consider the latter as a categorical version (in the sense of Baire) of randomness. For this reason we also study higher effective categoricity and we point out the differences and similarities higher categoricity shares with higher randomness.
Abstract FR:
Dans cette thèse, nous traitons principalement des notions d'aléatoirité d'ordre supérieur, notamment les notions de Delta ^1_1-aléatoirité, de Pi^1_1-Martin-Löf aléatoirité, de Pi^1_1- aléatoirité faible, et de Pi^1_1-aléatoirité, en mettant plus particulièrement l'accent sur cette dernière notion : la Pi^1_1-aléatoirité. L'étude de ces notions d'aléatoirité soulève plusieurs problématiques. Nous essayons notamment de comprendre les similarités et les différences entre toutes ces notions, mais aussi entre ces notions et les notions d'aléatoirités classiques, largement étudiées ces quinze dernières années. Une différence importante entre les notions de calculabilité/aléatoirité d'ordre supérieur et les notions de calculabilité/aléatoirité classique est de nature topologique. Aussi nous avons concentré nos efforts sur trois des phénomènes à travers lesquels cette différence s'exprime : Dans la notion de calcul, dans la notion d'aléatoire relatif, et dans la notion d'approchabilité. Nous soulignons également les liens étroits entre la notion d'aléatoirité et celle de généricité, que l'on peut considérer comme une version catégorique (au sens de Baire) d'aléatoirité. Pour cette raison, nous étudions aussi la catégoricité effective d'ordre supérieur et nous mettons en avant les différences et similarités qu'elle présente avec la notion d'aléatoirité.