Degré de Turing

Notion algorithmique

En informatique et en logique mathématique, le degré de Turing (nommé d'après Alan Turing) ou le degré d'insolubilité d'un ensemble d'entiers naturels mesure le niveau d'insolubilité algorithmique de l'ensemble.

Aperçu

modifier

Le concept de degré de Turing est fondamental dans la théorie de la calculabilité, où des ensembles d'entiers naturels sont souvent considérés comme des problèmes de décision. Le degré de Turing d'un ensemble révèle combien il est difficile de résoudre le problème de décision associé à cet ensemble, à savoir, déterminer si un nombre arbitraire est dans l'ensemble donné.

Deux ensembles sont Turing-équivalents s'ils ont le même niveau d’insolvabilité ; chaque degré de Turing est une collection d'ensembles Turing-équivalents, de sorte que deux ensembles ayant un degré de Turing différent ne sont pas Turing-équivalent. En outre, les degrés de Turing sont partiellement ordonnés de telle sorte que si le degré de Turing d'un ensemble X est inférieur au degré de Turing d'un ensemble Y, alors toute procédure (récursive) qui décide correctement si les nombres sont dans Y peut être efficacement convertie en une procédure qui décide correctement si les nombres sont dans X. Ainsi, le degré de Turing d'un ensemble correspond à son niveau d'insolubilité algorithmique.

Les degrés de Turing ont été introduits par Emil Leon Post (1944), et de nombreux résultats fondamentaux ont été établis par Stephen Cole Kleene et Post (1954). Les degrés de Turing ont dès lors été un domaine de recherche intense.

Turing-équivalence

modifier

Pour l'ensemble de cet article, le mot ensemble fera référence à un ensemble d'entiers naturels. Un ensemble X est dit Turing-réductible à un ensemble Y s'il y a un oracle qui décide l'appartenance dans X quand un oracle décide de l'appartenance dans Y. La notation XT Y indique que X est Turing-réductible à Y.

Deux ensembles X et Y sont définis Turing-équivalents si X est Turing-réductible à Y et Y est Turing-réductible à X. La notation XT Y indique que  X et Y sont Turing-équivalents. La relation ≡T peut être vue comme une relation d'équivalence, ce qui veut dire que pour tout ensemble X, Y, et Z :

  • XT X
  • XT Y implique YT X
  • Si XT Y et YT Z alors XT Z.

Un degré de Turing est une classe d'équivalence de la relation ≡T.

La notation [X] désigne la classe d'équivalence contenant un ensemble X. La collection entière des degrés de Turing est notée  .

Les degrés de Turing sont munis d'un ordre partiel ≤ défini de telle sorte que [X] ≤ [Y] si et seulement si XY. Le degré de Turing contenant tous les ensembles récursifs est le plus petit degré de Turing, il est noté 0 (zéro).

Pour tout ensemble X et Y, X joint Y, noté XY, est défini comme étant l'union des ensembles {2n: nX} et {2m+1: mY}. Le degré de Turing de XY est la borne supérieure des degrés de X et Y. Ainsi,   est un semi-treillis. La borne supérieure des degrés de a et b est notée ab.

Pour tout ensemble X, la notation X' désigne l'ensemble des programmes utilisant un oracle (ou leurs indices) qui s'arrêtent lorsqu'on utilise X comme un oracle. L'ensemble X' est appelé le saut de Turing de X. Le saut de Turing d'un degré [X] est défini comme étant le degré [X']; ceci est une définition valable car X′ ≡T Y′ lorsque XT Y. Un exemple clé est 0′, le degré du problème de l'arrêt.

Propriétés basiques

modifier
  • Chaque degré de Turing est infini dénombrable, à savoir, il contient exactement   ensembles.
  • Il y a   degrés de Turing distincts.
  • Pour chaque degré a, on a l'inégalité stricte a < a′.
  • Pour chaque degré a, l'ensemble des degrés inférieurs à a est dénombrable. L'ensemble des degrés supérieurs à a est de cardinal  .

Structure

modifier

Un grand nombre de recherches ont été menées sur la structure des degrés de Turing. Les propriétés suivantes sont seulement quelques-unes des nombreuses existantes. Une conclusion générale qui peut être tirée de ces recherches est que la structure des degrés de Turing est extrêmement compliquée.

Autres propriétés

modifier
  •  Il y a des degrés minimaux. Un degré a est minimal si a est non nul et il n'existe pas de degré entre 0 et a. Ainsi, la relation d'ordre sur les degrés n'est pas un ordre dense.
  • Pour chaque degré non nul a, il existe un degré b incomparable avec a.
  • Il y a un ensemble de  degrés de Turing deux-à-deux incomparables.
  • Il y a des paires de degrés sans borne inférieure. Ainsi,   n'est pas un treillis.
  • Tout ensemble partiellement ordonné dénombrable se plonge dans  .
  • Aucune suite infinie strictement croissante de degrés de Turing n’a de borne supérieure.

Propriétés impliquant le saut

modifier
  • Pour chaque degré a, il existe un degré entre a et a'. En fait, il existe une suite dénombrable de degrés deux-à-deux incomparables entre a et a'.
  • Un degré a est de la forme b′ si et seulement si 0′a.
  • Pour tout degré a, il existe un degré b tel que a < b et b′ = a′; un tel degré b est dit faible par rapport à a.
  • Il y a une suite infinie ai de degrés de telle sorte que ai+1ai pour chaque i.

Propriétés logiques

modifier
  • Simpson (1977) a montré que la théorie du premier ordre de   dans le langage ⟨ ≤, = ⟩ ou ⟨ ≤, ′, =⟩ est many-one équivalente (en) à la théorie du second-ordre arithmétique. Cela indique que la structure de   est extrêmement compliquée.
  • Shore et Slaman (1999) ont montré que l'opérateur de saut est définissable dans la structure du premier ordre des degrés dans le langage ⟨ ≤, =⟩.

Voir aussi

modifier

Références

modifier
Monographies (niveau de premier cycle)
Monographies et études (niveau universitaire)
  • Ambos-Spies, K. et Fejer, P. Degrees of Unsolvability. Unpublished. http://www.cs.umb.edu/~fejer/articles/History_of_Degrees.pdf
  • Lerman, M. Degrees of unsolvability. Perspectives in Mathematical Logic. Springer-Verlag, Berlin, 1983. (ISBN 3-540-12155-2)
  • Rogers, H. The Theory of Recursive Functions and Effective Computability, MIT Press. (ISBN 0-262-68052-1); (ISBN 0-07-053522-1)
  • Sacks, Gerald E. Degrees of Unsolvability (Annals of Mathematics Studies), Princeton University Press. (ISBN 978-0691079417)
  • Simpson, S. Degrees of unsolvability: a survey of results. Handbook of Mathematical Logic, North-Holland, 1977, pp. 631–652.
  • Shoenfield, Joseph R. Degrees of Unsolvability, North-Holland/Elsevier, (ISBN 978-0720420616).
  • Shore, R. The theories of the T, tt, and wtt r.e. degrees: undecidability and beyond. Proceedings of the IX Latin American Symposium on Mathematical Logic, Part 1 (Bahía Blanca, 1992), 61–70, Notas Lógica Mat., 38, Univ. Nac. del Sur, Bahía Blanca, 1993.
  • Soare, R. Recursively enumerable sets and degrees. Perspectives in Mathematical Logic. Springer-Verlag, Berlin, 1987. (ISBN 3-540-15299-7)
  • Soare, Robert I. Recursively enumerable sets and degrees. Bull. Amer. Math. Soc. 84 (1978), no. 6, 1149–1181. lien Math Reviews
Documents de recherche