5. 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 pr […]
… pour nos abonnés, l'article se prolonge sur 13 pages…
