La théorie de la calculabilité au 20ème siècle

Martin Davis

Nous ferons un tour d’horizon des points les plus marquants dans le développement de la théorie de la calculabilité/ recursivité. L’importance des définitions récursives est devenue claire à partir des travaux fondationnels de Dedekind et Péano à la fin du siècle dernier. A cette époque Axel Thue étudia des opérations sur des suites. Dans les années 20 Skolem proposa d’utiliser des définitions récursives pour fonder l’arithmétique sur un calcul sans variables, et Hilbert voulait les utiliser pour prouver l’hypothèse du continu. En 1931 Gödel utilisa la classe des fonctions aujourd’hui appelées primitive récursives dans l’article classique où il démontre l’existence dénoncés arithmétiques indécidables dans les systèmes formels. Dans des conférences en 1934 Gödel suggère qu’une extension appropriée de la notion de définition récursive pouvait amener à une classe de fonctions équivalente à celle des fonctions algorithmiquement calculables. Peu de temps après Church s’aperçoit que les fonctions exprimables dans son lambda calcul ont précisement cette propriété, et son élève Kleene demontre que cette lambda-definissabilité était équivalente à la récursivité au sens de Gödel. Par ailleurs, en Angleterre, Turing propose sa notion de calculabilité par une machine abstraite et fait une analyse du processus de calculabilité, en concluant que ses machines permettaient d’englober toute calculabilité. Il s’avère rapidement que la notion de Turing était équivalente aux deux autres. Déjà dans les années 20, Post avait trouvé sa propre version (équivalente aux autres), mais il n’avait pas réussi à produire une théorie convaincante. Après la publication du travail de Church —mais avant prendre connaissance de celui de Turing— Post produit sa propre variante des machines de Turing.

Les preuves de l’équivalence des diverses notions de calculabilité furent publiées en 1936, l’année même où le Journal of Symbolic Logic fut lancé, ainsi que le premier exemple d’un problème important dont la preuve de la non-résolubilité utilisait les nouvelles techniques, à savoir, la démonstration par Turing et Church de la nonrésolubilité récursive du problème de la décision (Entscheidungsproblem) de Hilbert. Ces résultats établissent la théorie de la calculabilité comme une discipline cohérente pouvant se développer dans plusieures directions (où seuls les points les plus marquants seront abordés dans cette conférence).

Dans un article fécond, en 1938, Kleene introduisait la notion de fonction récursive partielle, en montrant le théorème s-m-n et les deux théorèmes de la récursion, et appliquait cette machinerie aux ordinaux constructifs. dans un article de 1943 il étudie la hierarchie arithmétique. Dans sa thèse (1939) Turing avait introduit la notion féconde de calculabilité relative à un oracle. Dans une conférence à l’American Mathematical Society qui a eu une très grande influence, Post initiait l’étude des ensembles récursivement énumerables (r.e.) et de leurs deg˚ ’es, et posait la question —connue depuis lors comme le “problème de Post”— de l’existence d’un ensemble r.e., non récursif, ayant un degré plus petit que celui de son ensemble créatif K. Post montra également comment les niveaux de la hierarchie arithmétique étaient liés au “jump” d’un ensemble aux ensembles r.e. relativement à lui. Davis et Mostowski (1950) étudient des extensions de la hierarchie arithmétique (la hierarchie hyper-arithmétique), étude poursuivi par Kleene et Spector.

Post et Markov prouvent indépendamment la non-résolubilté du problème des mots pour les semigroupesn et, puis, Novikov et Boone étendent ce résultat aux groupes. En obtenant, en 1950, une forme normale pour les ensembles r.e., Davis fait un premier pas vers une preuve de la non-résolubilité du 10ième problème de Hilbert. Simultanement, Julia Robinson approche le problème à partir de la direction opposée, en examinant la question de définir l’exponentiation au moyen d’une équation diophantienne. Avec la participation de Hilary Putnam, ces approches se rencontrent à mi-chemin dans leur preuve, en 1960, de la nno-résolubilité du problème de la décision pour les équations diophantiennes exponentielles. Pour compléter la preuve de la non-résolubilité du 10ième problème de Hilbert, il fallait trouver une équation diophantienne dont la solution a une croissance exponentielle; cette équation fut trouvée par Matijasievich en 1970 au moyen d’une ingénieuse construction.

La “méthode de la priorité”, introduit par Friedberg et Muchnik en 1957 donne la clef pour la solution du problème de Post. Cette méthode permet de satisfaire, eventuellement, un nombre infini de contraintes apparemment contradictoires par un processus dont le résultat est un ensemble r.e. Ceci marque le début d’un développement, encore en cours, permettant de démontrer, en déployant une grande virtuosité, certains théorèmes surprenants. Deux exemples, dus à Sacks, seront donnés dans la conférence.

Address: Visiting Scholar UC Berkeley – Professor Emeritus, New York University, USA

E-mail: martin@eipye.com