Saut de Turing

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 une codage de Godël φ_i^X des fonctions X-calculables, le saut de Turing X′ de X est défini par

${\displaystyle 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

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

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

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

${\displaystyle 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é cardinaux réguliers indénombrables (Lubarsky 1987)[1].

• Le saut de Turing 0′ de l'ensemble vide est Turing-équivalent au problème de l'arrêt[2].
• Pour chaque n, l'ensemble 0⁽ⁿ⁾ est se réduit (many-one) au niveau ${\displaystyle \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^(ω)[3].

• 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[2].

• (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)

• Portail de l'informatique théorique
• Portail de la logique