Concept
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. 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 une codage de Godël φiX 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 jointure 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 . 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é cardinaux réguliers indénombrables (Lubarsky 1987). 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 .