Saut de Turing

En théorie de la calculabilité, le saut de Turing, du nom d'Alan Turing, est une opération qui attribue à chaque problème de décision X un problème de décision plus difficile X′ avec la propriété que X′ n'est pas décidable par une machine à oracle relative à X.

Le saut est appelé opérateur de saut car il augmente le degré de Turing du problème X. Autrement dit, le problème X′ n'est pas Turing-réductible (en) à X . Le théorème de Post établit une relation entre l'opérateur de saut de Turing et la hiérarchie arithmétique des ensembles de nombres naturels. De manière informelle, étant donné un problème, le saut de Turing renvoie l'ensemble des machines de Turing qui s'arrêtent lorsqu'elles ont accès à un oracle qui résout ce problème.

Définition

Le saut de Turing de X peut être considéré comme un oracle au problème d'arrêt pour les machines à oracle avec un oracle à X.

Formellement, étant donné un ensemble X et un codage de Godël φ_i^X des fonctions X-calculables, le saut de Turing X′ de X est défini par

$X'=\{x\mid \varphi _{x}^{X}(x)\ {\mbox{est défini}}\}.$

Le n-ième saut de Turing X⁽ⁿ⁾ est défini récursivement par

$X^{(0)}=X,$

$X^{(n+1)}=(X^{(n)})'.$

Le saut-ω X^(ω) de X est la jointure effective de la suite d'ensembles X⁽ⁿ⁾ pour n ∈ N :

$X^{(\omega )}=\{p_{i}^{k}\mid i\in \mathbb {N} {\text{ et }}k\in X^{(i)}\},$

où p_i désigne le i ème nombre premier.

La notation 0′ ou ∅′ est parfois utilisée pour le saut de Turing de l'ensemble vide. Elle se lit zero-jump.

De même, 0⁽ⁿ⁾ est le n-ième saut de l'ensemble vide. Pour n fini, ces ensembles sont étroitement liés à la hiérarchie arithmétique.

Le saut peut être itéré aux ordinaux transfinis : les ensembles 0^(α) pour α < ω₁^CK, où ω₁^CK est l'ordinal de Church–Kleene, sont liés à la hiérarchie hyperarithmétique (en). Au-delà de ω₁^CK, le processus peut se poursuivre à travers les ordinaux dénombrables de l'univers constructible, en utilisant les méthodes de la théorie des ensembles (Hodes 1980). Le concept a également été généralisé aux cardinaux réguliers non dénombrables (Lubarsky 1987).

Exemples

• Le saut de Turing 0′ de l'ensemble vide est Turing-équivalent au problème de l'arrêt.
• Pour chaque n, l'ensemble 0⁽ⁿ⁾ est se réduit (many-one) au niveau $\Sigma _{n}^{0}$ dans la hiérarchie arithmétique (par le théorème de Post ).
• L'ensemble des nombres de Gödel des formules vraies dans le langage de l'arithmétique de Peano avec un prédicat pour X est calculable à partir de X^(ω).

Propriétés

• X′ est X - récursivement énumérable mais pas X - récursif.
• Si A est Turing-équivalent à B, alors A′ est Turing-équivalent à B′ . La réciproque de cette implication n'est pas vraie.
• (Shore et Slaman, 1999) La fonction envoyant X à X′ est définissable dans l'ordre partiel des degrés de Turing.

Références

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

• Ambos-Spies, K. and Fejer, P. Degrees of Unsolvability. Unpublished. http://www.cs.umb.edu/~fejer/articles/History_of_Degrees.pdf
• Harold T. Hodes, « Jumping Through the Transfinite: The Master Code Hierarchy of Turing Degrees », Association for Symbolic Logic, vol. 45, n^o 2,‎ juin 1980, p. 204–220 (DOI 10.2307/2273183, JSTOR 2273183)
• Lerman, M., Degrees of unsolvability: local and global theory, Berlin; New York: Springer-Verlag, 1983 (ISBN 3-540-12155-2)
• Lubarsky, Robert S., « Uncountable Master Codes and the Jump Hierarchy », Journal of Symbolic Logic, vol. 52, n^o 4,‎ décembre 1987, p. 952–958 (JSTOR 2273829)
• Rogers Jr, H., Theory of recursive functions and effective computability, MIT Press, Cambridge, MA, USA, 1987 (ISBN 0-07-053522-1)
• Shore, R.A. et Slaman, T.A., « Defining the Turing jump », Mathematical Research Letters, vol. 6, n^os 5–6,‎ 1999, p. 711–722 (DOI 10.4310/mrl.1999.v6.n6.a10 , lire en ligne, consulté le 13 juillet 2008)
• Soare, R.I., Recursively Enumerable Sets and Degrees: A Study of Computable Functions and Computably Generated Sets, Springer, 1987 (ISBN 3-540-15299-7)