RÉCURSIVITÉ, logique mathématique
Quelques exemples de généralisation et d'application de la récursivité
On peut étendre la notion de calcul par machine en introduisant la possibilité de « consulter un oracle ». Par oracle, nous entendons ici un ensemble X d'entiers ; permettre à la machine de consulter l'oracle X, c'est l'autoriser à poser la question « n ∈ X ? » et à poursuivre son calcul selon la réponse qui lui est faite. On introduit, à cet effet, la notion de récursivité relative : on dira qu'un ensemble Y est récursif en X s'il existe une machine qui, en utilisant X comme oracle, décide, pour tout entier n, en un nombre fini de démarches, que n ∈ Y, ou pas. Le degré de Turing de X est l'ensemble de tous les Y tels que X est récursif en Y et Y est récursif en X.
En 1948, E. Post posait le problème suivant : Existe-t-il deux ensembles récursivement énumérables X et Y tels que X n'est pas récursif en Y et Y n'est pas récursif en X ? R. M. Friedberg (1957) et A. A. Mučnik (1956) ont apporté (indépendamment et par la même méthode !) une réponse positive à cette question. Pour ce faire, ils ont dû définir pas à pas, en une énumération récursive, deux ensembles X et Y de telle sorte que, pour toute machine de Turing M, si M munie de l'oracle X définit un ensemble X′ récursif en X, on ait Y ≠ X′ et vice versa. L'idée est d'attribuer un ordre de priorité aux différents moyens de satisfaire à ces exigences à partir d'approximations finies de X et de Y. Supposons que, à une étape de l'énumération, il faille, pour satisfaire par un moyen donné à une exigence donnée, renoncer à tel autre moyen mis en œuvre antérieurement pour satisfaire à une autre exigence : on tranche selon la priorité relative des deux moyens. Il faut alors prouver que toutes les exigences sont finalement satisfaites de façon définitive, ce qui demande, tant pour résoudre le problème de Post que pour réaliser d'autres constructions, une analyse combinatoire parfois très fine. Le procédé inventé par Friedberg et par Mučnik, appelé métode de priorité a été brillamment exploité ultérieurement par de nombreux mathématiciens pour mettre en évidence l'extraordinaire richesse de la structure des degrés de Turing et pour opérer d'autres applications en récursivité. Notons aussi que cette technique a été utilisée récemment (1975) en théorie des ensembles par D. Martin pour démontrer que les jeux boréliens (cf. théorie axiomatique des ensembles) sont déterminés, ce qui nous conduit fort loin du problème de Post !
Théorie descriptive effective des ensembles
Les Borel, Lebesgue, Luzin et autres (ce qu'on appelle parfois l'école semi-intuitionniste), en élaborant la théorie descriptive (classique) des ensembles, avaient eu l'intuition de ses aspects effectifs. Dans les années cinquante, S. C. Kleene jetait les fondements d'une théorie permettant de rendre compte rigoureusement de cette intuition. Le principal outil de l'analyse de Kleene est la théorie de la récursivité.
On prendra ici comme espace topologique de référence l'espace de Baire de toutes les fonctions de N dans N, que nous notons NN. Ce que nous dirons s'applique également à la droite réelle R, à l'espace de Cantor 2N et, en gros, à tout espace polonais.
L'espace de Baire NN est muni d'une métrique naturelle : aussi, pour f ≠ g, posons d (f, g) = (n + 1)−1, où n est le premier entier tel que f (n) ≠ g(n). Pour cette métrique, l'espace NN est complet. À chaque fonction h dont le domaine et l'image sont des parties finies de N, on associe un ouvert élémentaire N = {g|g(n) = h(n)} pour tout n dans le domaine de h. Les ouverts élémentaires forment une base dénombrable pour la topologie sur NN.
La hiérarchie borélienne[...]
La suite de cet article est accessible aux abonnés
- Des contenus variés, complets et fiables
- Accessible sur tous les écrans
- Pas de publicité
Déjà abonné ? Se connecter
Écrit par
- Kenneth Mc ALOON : maître de recherche au C.N.R.S.
- Bernard JAULIN : membre de l'Académie des sciences
- Jean-Pierre RESSAYRE : chargé de recherche au C.N.R.S.
Classification
Autres références
-
CHURCH ALONZO (1903-1995)
- Écrit par Françoise ARMENGAUD
- 616 mots
Mathématicien et logicien, philosophe et historien de la logique, Alonzo Church est né le 14 juin 1903 à Washington et mort le 11 août 1995 à Hudson (Ohio). Professeur de mathématiques à l'université de Princeton, directeur du Journal of Symbolic Logic, il est selon Kneale «...
-
DÉMONSTRATION THÉORIE DE LA
- Écrit par Jean-Yves GIRARD
- 6 140 mots
- 1 média
...fini, détermine uniquement (par unicité du prolongement par limites directes) la famille (Pα). Il devient alors possible de parler de B-démonstration récursive, autrement dit nous avons un concept syntaxique. (Mais l'ensemble des indices de B-démonstrations est Π12 .) Et Girard a pu établir en... -
KLEENE STEPHEN COLE (1909-1994)
- Écrit par Pierre GOUJON
- 371 mots
Mathématicien américain né à Hartford (Connecticut). Diplômé de l'Amherst College, Stephen C. Kleene entre, en 1930, à l'université de Princeton. Il est docteur de la même université en 1934. Dès cette époque, il partage son temps entre l'enseignement (université du Wisconsin) et la recherche....
-
POST EMIL LEON (1897-1954)
- Écrit par Bernard JAULIN
- 622 mots
Mathématicien américain né à Augustów (Pologne) et mort à New York. Arrivé aux États-Unis en 1904, Emil Post obtint son Ph.D. à l'université Columbia de New York en 1920. Il était membre de l'American Mathematical Society depuis 1918 et de l'Association for Symbolic Logic dès sa fondation...
