You can manage bookmarks using lists, please log in to your user account for this.
Media type:
Text;
E-Book;
Electronic Thesis
Title:
Infinite Computations in Algorithmic Randomness and Reverse Mathematics ; Calcul infini dans l'aléatoire algorithmique et les mathématiques à rebours
Footnote:
Diese Datenquelle enthält auch Bestandsnachweise, die nicht zu einem Volltext führen.
Description:
Cette thèse se concentre sur l'apport du calcul en temps infini à la logique mathématique. Le calcul en temps infini est une variante de la traditionnelle définition du calcul comme suite finie d'étapes, chaque étape étant définie à partir des précédentes, et aboutissant à un état final. Dans le cas de cette thèse, nous considérons le cas où le nombre d'étapes n'est pas forcément fini, mais peut continuer le long des ordinaux, une extension des entiers. Il existe plusieurs manières d'implémenter cette idée, nous en utilisons trois : la calculabilité d'ordre supérieur, les machines de Turing à temps infini et l'α-récursion.Une part de ce travail concerne les mathématiques à rebours, et plus particulièrement le théorème de Hindman. Les mathématiques à rebours sont un programme mathématique consistant en l'étude des théorèmes et axiomes mathématiques du point de vue de leur "puissance", et établissant une hiérarchie sur celle-ci. En particulier la détermination des briques de bases, aussi appelées axiomes, qui sont nécessaires dans une preuve est centrale. Nous étudions au travers de ce prisme le théorème de Hindman, un théorème combinatoire de la théorie de Ramsey qui dit que pour tout partitionnement des entiers en un nombre fini d'ensembles, appelés couleurs, il doit exister une ensemble infini S d'entiers dont toute les sommes d'éléments issus de S ont la même couleur. Dans cette thèse, nous progressons dans la résolution de la question du système d'axiomes minimal pour prouver ce théorème, en montrant que l'existence d'objets combinatoires intermédiaires est prouvable dans un système d'axiome faible.La réduction de Weihrauch est une méthode récente de comparaison de puissance de théorème, qui les considère comme des problèmes à résoudre, puis compare leur difficulté. Cette réduction a été moins étudiée, et en particulier certains des principes les plus importants des mathématiques à rebours ne sont pas bien compris dans ce cadre. L'un d'eux est le principe ATR de Récursion Arithmétique Transfinie, un principe ...