Puissance logique et calculatoire de l'aléa algorithmique
Institution:
Paris 7Disciplines:
Directors:
Abstract EN:
Theory of algorithmic randomness theory studies the Jack of structure that characterizes random objects Kolmogorov complexity is a fimdamental tool of this theory and we study the characteristic properties of this fonction. In a second step we investigate the possibility of extending the study of the biased random bit sequences wondering if precise knowledge of using or not changes the quality of randomness we describe, We then focus on the logic power of the random object: What can be inferred from the fact (non provable) that a sequence has no structure? Finally we look a the possibility of calculating a completion of arithmetic from an randomized algorithm.
Abstract FR:
La théorie de l'aléa effective étudie l'absence de structure qui caractérise l'aléa. La complexité de Kolmogorov est un outil fondamental de cette théorie et nous étudions les propriétés caractéristiques de cette fonctions. Dans un second temps noùs nous intéressons à la possibilité d'étendre l'étude de l'aléa aux suites de bits biaisés en nous demandant si la connaissance précise du biais ou non modifie la qualité de l'aléa que nous décrivons. Nous nous intéressons ensuite à la puissance logique de l'aléa: que peut on déduire du fait (non prouvable) qu'une suite est dénué de structure ? Enfin on s'intéresse a la possibilité de calculer une complétion de l'arithmétique à partir d'un algorithme utilisant de l'aléa.