Degré de Turing
# 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 vu 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 $≤_TY.$ 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érieur des degrés de a et b est noté 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érieur à 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 ⟨ ≤, =⟩.
