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 un problème de décision plus difficile avec la propriété que n'est pas décidable par une machine à oracle relative à .
Le saut est appelé opérateur de saut car il augmente le degré de Turing du problème . Autrement dit, le problème n'est pas à . 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 et un codage de Godël des fonctions X-calculables, le saut de Turing de est défini par
Le -ième saut de Turing est défini récursivement par
Le saut- de est la jonction effective de la suite d'ensembles pour :
où désigne le ème nombre premier.
La notation ou est parfois utilisée pour le saut de Turing de l'ensemble vide. Elle se lit zero-jump.
De même, est le -ième saut de l'ensemble vide. Pour fini, ces ensembles sont étroitement liés à la hiérarchie arithmétique.
Le saut peut être itéré aux ordinaux transfinis : les ensembles pour , où est l'ordinal de Church–Kleene, sont liés à la hiérarchie hyperarithmétique. Au-delà de , 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 de l'ensemble vide est Turing-équivalent au problème de l'arrêt. Pour chaque , l'ensemble est se réduit (many-one) au niveau 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 est calculable à partir de .
Propriétés
est - récursivement énumérable mais pas - récursif. Si est Turing-équivalent à , alors est Turing-équivalent à . La réciproque de cette implication n'est pas vraie. (Shore et Slaman, 1999) La fonction envoyant à est définissable dans l'ordre partiel des degrés de Turing.
Références
Ambos-Spies, K. and Fejer, P. Degrees of Unsolvability. Unpublished. http://www.cs.umb.edu/~fejer/articles/History_of_Degrees.pdf
Catégorie:Alan Turing Catégorie:Calculabilité