Degré de Turing

Un article de Wikipédia, l'encyclopédie libre.
Sauter à la navigation Sauter à la recherche

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 | modifier le code]

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 si'ls 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 | modifier le code]

Article détaillé : Turing-équivalent.

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 vu comme une relation d'équivalence, qui veut dire que pour tout ensembles 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 de degrés de Turing est notée .

Les degrés de Turing ont un poset ≤ défini de telle sorte que [X] ≤ [Y] si et seulement si XY. Il y a un degré de Turing unique, contenant tous les ensembles récursifs, et ce degré est inférieur à tous les autres degrés. Il est noté 0 (zéro), car il est le plus petit élément du poset .

Pour tout ensembles 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érieur des degrés de a et b est noté ab.

Pour tout ensemble X, la notation X' désigne l'ensemble des indices de l'oracle qui s'arrête 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 | modifier le code]

  • 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, l'inégalité stricte a < a′ se tient.
  • Pour chaque degré a, l'ensemble de degrés suivant a est dénombrable. L'ensemble des degrés supérieur à a à une taille de .

Structure[modifier | modifier le code]

Un grand nombre de recherches ont été menées sur la structure des degrés de Turing. Les listes d'études suivantes sont seulement quelqu'une des nombreux 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 | modifier le code]

  •  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 paires d'un degrés de Turing incomparables.
  • Il y a des paires de degrés sans borne inférieure. Ainsi,  n'est pas un treillis.
  • Chaque ensemble partiellement ordonné dénombrable peut être affecté des degrés de Turing.
  • Une suite infinie strictement croissante de degrés n’a pas de borne supérieure.

Propriétés impliquant le saut[modifier | modifier le code]

  • Pour chaque degré a, il existe un degré entre a et a'. En fait, il existe une suite de degrés dénombrable incomparables par paire 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 | modifier le code]

  • Simpson (1977) a montré que la théorie du premier ordre  〈 ≤, = 〉 ou 〈 ≤, ′, =〉 est many-one equivalent[pas clair] à 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 du saut est définissable dans la structure du premier ordre des degrés avec le langage ⟨ ≤, =⟩.

Voir aussi[modifier | modifier le code]

Références[modifier | modifier le code]

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