Degré de Turing

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

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

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 X ≤_T 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 X ≡_T 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 :

• X ≡_T X
• X ≡_T Y implique Y ≡_T X
• Si X ≡_T Y et Y ≡_T Z alors X ≡_T 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 ${\mathcal {D}}$.

Les degrés de Turing sont munis d'un ordre partiel ≤ défini de telle sorte que [X] ≤ [Y] si et seulement si X ≤_T Y. 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é X ⊕ Y, est défini comme étant l'union des ensembles {2n: n ∈ X} et {2m+1: m ∈ Y}. Le degré de Turing de X ⊕ Y est la borne supérieure des degrés de X et Y. Ainsi, ${\mathcal {D}}$ est un semi-treillis. La borne supérieure des degrés de a et b est notée a ∪ b.

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 X ≡_T Y. Un exemple clé est 0′, le degré du problème de l'arrêt.

Propriétés basiques

• Chaque degré de Turing est infini dénombrable, à savoir, il contient exactement $\aleph _{0}$ ensembles.
• Il y a $2^{\aleph _{0}}$ 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 $2^{\aleph _{0}}$.

Structure

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

•  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 $2^{\aleph _{0}}$degrés de Turing deux-à-deux incomparables.
• Il y a des paires de degrés sans borne inférieure. Ainsi, ${\mathcal {D}}$ n'est pas un treillis.
• Tout ensemble partiellement ordonné dénombrable se plonge dans ${\mathcal {D}}$.
• Aucune suite infinie strictement croissante de degrés de Turing n’a de borne supérieure.

Propriétés impliquant le saut

• 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 a_i de degrés de telle sorte que a′_i+1 ≤ a_i pour chaque i.

Propriétés logiques

• Simpson (1977) a montré que la théorie du premier ordre de ${\mathcal {D}}$ dans le langage ⟨ ≤, = ⟩ ou ⟨ ≤, ′, =⟩ est many-one équivalente (en) à la théorie du second-ordre arithmétique. Cela indique que la structure de ${\mathcal {D}}$ 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

• Mesure de Martin
• Machine de Turing
• Saut de Turing

Références

• (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Turing degree » (voir la liste des auteurs).

Monographies (niveau de premier cycle)

• Cooper, S.B. Computability theory. Chapman & Hall/CRC, Boca Raton, FL, 2004. (ISBN 1-58488-237-9)
• Cutland, N. Computability. Cambridge University Press, Cambridge-New York, 1980. (ISBN 0-521-22384-9); (ISBN 0-521-29465-7)

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

• Kleene, Stephen Cole; Post, Emil L. (1954), "The upper semi-lattice of degrees of recursive unsolvability", Annals of Mathematics, Second Series, 59 (3): 379–407, doi:10.2307/1969708, ISSN 0003-486X, JSTOR 1969708, MR 0061078
• Lachlan, A.H. (1966a), "Lower Bounds for Pairs of Recursively Enumerable Degrees", Proceedings of the London Mathematical Society, 3 (1): 537, doi:10.1112/plms/s3-16.1.537.
• Lachlan, A.H. (1966b), "The impossibility of finding relative complements for recursively enumerable degrees", J. Symb. Logic, 31 (3): 434–454, doi:10.2307/2270459, JSTOR 2270459.
• Lachlan, A.H.; Soare, R.I. (1980), "Not every finite lattice is embeddable in the recursively enumerable degrees", Advances in Math, 37: 78–82, doi:10.1016/0001-8708(80)90027-4.
• Nies, André; Shore, Richard A.; Slaman, Theodore A. (1998), "Interpretability and definability in the recursively enumerable degrees", Proceedings of the London Mathematical Society, 77 (2): 241–291, doi:10.1112/S002461159800046X, ISSN 0024-6115, MR 1635141
• Post, Emil L. (1944), "Recursively enumerable sets of positive integers and their decision problems", Bulletin of the American Mathematical Society, 50 (5): 284–316, doi:10.1090/S0002-9904-1944-08111-1, ISSN 0002-9904, MR 0010514 
• Sacks, G.E. (1964), "The recursively enumerable degrees are dense", Annals of Mathematics, Second Series, 80 (2): 300–312, doi:10.2307/1970393, JSTOR 1970393. 
• Shore, Richard A.; Slaman, Theodore A. (1999), "Defining the Turing jump", Mathematical Research Letters, 6: 711–722, doi:10.4310/mrl.1999.v6.n6.a10, ISSN 1073-2780, MR 1739227 
• Simpson, Stephen G. (1977), "First-order theory of the degrees of recursive unsolvability", Annals of Mathematics, Second Series, 105 (1): 121–139, doi:10.2307/1971028, ISSN 0003-486X, JSTOR 1971028, MR 0432435 
• Thomason, S.K. (1971), "Sublattices of the recursively enumerable degrees", Z. Math. Logik Grundlag. Math., 17: 273–280, doi:10.1002/malq.19710170131. 
• Yates, C.E.M. (1966), "A minimal pair of recursively enumerable degrees", J. Symbolic Logic, 31 (2): 159–168, doi:10.2307/2269807, JSTOR 2269807.