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

Le n-ième saut de Turing X(n) est défini récursivement par

Le saut-ω X(ω) de X est la jointure effective de la suite d'ensembles X(n) pour nN :

pi 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(n) 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 α < ω1CK, où ω1CK est l'ordinal de Church–Kleene, sont liés à la hiérarchie hyperarithmétique (en). Au-delà de ω1CK, 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].

Exemples

Propriétés

Références

  1. Lubarsky, « Uncountable master codes and the jump hierarchy », The Journal of Symbolic Logic, vol. 52, no 4, , p. 952–958 (ISSN 0022-4812, DOI 10.2307/2273829, JSTOR 2273829)
  2. Shore et Slaman, « Defining the Turing Jump », Mathematical Research Letters, vol. 6, no 6, , p. 711–722 (DOI 10.4310/MRL.1999.v6.n6.a10)
  3. Hodes, « Jumping through the transfinite: the master code hierarchy of Turing degrees », The Journal of Symbolic Logic, vol. 45, no 2, , p. 204–220 (ISSN 0022-4812, DOI 10.2307/2273183, JSTOR 2273183)
  • Portail de l'informatique théorique
  • Portail de la logique
Cet article est issu de Wikipedia. Le texte est sous licence Creative Commons - Attribution - Partage dans les Mêmes. Des conditions supplémentaires peuvent s'appliquer aux fichiers multimédias.