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 Modèle:Formule un problème de décision plus difficile Modèle:Formule avec la propriété que Modèle:Formule n'est pas décidable par une machine à oracle relative à Modèle:Formule.

Le saut est appelé opérateur de saut car il augmente le degré de Turing du problème Modèle:Formule. Autrement dit, le problème Modèle:Formule n'est pas Modèle:Lien à Modèle:Formule . 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 Modèle:Formule et un codage de Godël Modèle:Math des fonctions X-calculables, le saut de Turing Modèle:Formule de Modèle:Formule est défini par

X^{'} = {x ∣ φ_{x}^{X} (x) est défini} .

Le Modèle:Formule-ième saut de Turing Modèle:Formule est défini récursivement par

X^{(0)} = X,

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

Le saut-Modèle:Formule Modèle:Formule de Modèle:Formule est la jonction effective de la suite d'ensembles Modèle:Formule pour Modèle:Formule :

X^{(ω)} = {p_{i}^{k} ∣ i \in ℕ et k \in X^{(i)}},

La notation Modèle:Formule ou Modèle:Formule est parfois utilisée pour le saut de Turing de l'ensemble vide. Elle se lit zero-jump.

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

Le saut peut être itéré aux ordinaux transfinis : les ensembles Modèle:Formule pour Modèle:Formule, où Modèle:Formule est l'ordinal de Church–Kleene, sont liés à la hiérarchie hyperarithmétique. Au-delà de Modèle:Formule, 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)^[1].

Le saut de Turing Modèle:Formule de l'ensemble vide est Turing-équivalent au problème de l'arrêt^[2].
Pour chaque Modèle:Formule, l'ensemble Modèle:Formule est se réduit (many-one) au niveau $Σ_{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 Modèle:Formule est calculable à partir de Modèle:Formule^[3].