La logique ordinale de Turing

Le sujet visé par cette dissertation est la logique ordinale de Turing. Nous nous référons au texte original de Turing «Systems of logic based on ordinals» (Turing [1939]), la thèse que Turing rédigea à Princeton sous la direction du professeur Alonzo Church. Le principe d’une logique ordinale consiste à surmonter localement l’incomplétude gödelienne pour l’arithmétique par le biais de progressions d’axiomes récursivement consistantes. Étant donné son importance considérable pour la théorie de la calculabilité et les fondements des mathématiques, cette recherche méconnue de Turing mérite une attention particulière. Nous retraçons ici le projet d’une logique ordinale, de ses origines dans le théorème d’incomplétude de Gödel jusqu'à ses avancées dans les développements de la théorie de la calculabilité. Nous concluons par une discussion philosophique sur les fondements des mathématiques en fonction d’un point de vue finitiste.

L'Approximation diophantienne simultanée et l'optimisation discrète

Étant donnée une fonction bornée (supérieurement ou inférieurement) $f:\mathbb{N}^k \To \Real$ par une expression mathématique, le problème de trouver les points extrémaux de $f$ sur chaque ensemble fini $S \subset \mathbb{N}^k$ est bien défini du point de vu classique. Du point de vue de la théorie de la calculabilité néanmoins il faut éviter les cas pathologiques où ce problème a une complexité de Kolmogorov infinie. La principale restriction consiste à définir l'ordre, parce que la comparaison entre les nombres réels n'est pas décidable. On résout ce problème grâce à une structure qui contient deux algorithmes, un algorithme d'analyse réelle récursive pour évaluer la fonction-coût en arithmétique à précision infinie et un autre algorithme qui transforme chaque valeur de cette fonction en un vecteur d'un espace, qui en général est de dimension infinie. On développe trois cas particuliers de cette structure, un de eux correspondant à la méthode d'approximation de Rauzy. Finalement, on établit une comparaison entre les meilleures approximations diophantiennes simultanées obtenues par la méthode de Rauzy (selon l'interprétation donnée ici) et une autre méthode, appelée tétraédrique, que l'on introduit à partir de l'espace vectoriel engendré par les logarithmes de nombres premiers.

Classer calculer

Un rêve, plus ou moins explicite, hante nos esprits depuis plusieurs millénaires. On le retrouve ci et là dans les listes égyptiennes, dans les catalogues aristotéliciens, dans les règles mnémotechniques des néoplatoniciens florentins de la Renaissance, dans les constructions mathématiques de Leibniz, dans les affirmations des grands noms du Web : le monde est constitué d’une masse énorme d’informations, dont la connaissance et l’exploitation permettrait la maîtrise quasi-totale. Il serait alors possible de tout savoir, de tout prévoir, de tout faire. Mais deux limites, proprement humaines, empêchent la détention et l’exploitation de cette globalité d’informations : l’accessibilité et la calculabilité. [Introduction]

La logique ordinale de Turing

Dans Systems of logic based on ordinals (1939), Turing explore les possibilités de minimiser les effets du théorème d’incomplétude pour l’arithmétique par le biais d’une logique ordinale. Nous rendons ici compte de cette recherche méconnue menée par Turing sur les fondements des mathématiques en replaçant ses apports dans le contexte actuel de la théorie de la calculabilité.