RÉCURSIVITÉ, logique mathématique

Carte mentale

Élargissez votre recherche dans Universalis

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éto [...]


1  2  3  4  5
pour nos abonnés,
l’article se compose de 14 pages





Écrit par :

Classification


Autres références

«  RÉCURSIVITÉ, logique mathématique  » est également traité dans :

CHURCH ALONZO (1903-1995)

  • Écrit par 
  • Françoise ARMENGAUD
  •  • 611 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 « le plus fidèle des disciples de Frege ». Réputé « platonisant », il défend une conception délibérément réaliste de la propo […] Lire la suite

DÉMONSTRATION THÉORIE DE LA

  • Écrit par 
  • Jean-Yves GIRARD
  •  • 6 260 mots
  •  • 1 média

Dans le chapitre « La logique Π12 »  : […] L'extension des résultats obtenus par Takeuti, Pohlers, Buchholz... pour le schéma de compréhension Π 1 1 à des systèmes plus forts nécessite de remplacer la ω-logique par des logiques correspondant à de plus grandes complexités logiques, Π 2 1 et plus généralement Π 1 n . Le problème de la B -règle, posé par Mostowski est le suivant : Caractériser les énoncés qui sont vrais dans tout modèle da […] Lire la suite

KLEENE STEPHEN COLE (1909-1994)

  • Écrit par 
  • Pierre GOUJON
  •  • 370 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. Il est successivement membre du Conseil national de la recherche scientifique (1957), puis président de l […] Lire la suite

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 en 1935. Sa thèse de doctorat, publiée en 1921, porte sur le calcul propositionnel de A. N. Whitehead et B. Ru […] Lire la suite

Voir aussi

Pour citer l’article

Kenneth Mc ALOON, Bernard JAULIN, Jean-Pierre RESSAYRE, « RÉCURSIVITÉ, logique mathématique », Encyclopædia Universalis [en ligne], consulté le 02 juillet 2020. URL : http://www.universalis.fr/encyclopedie/recursivite-logique-mathematique/