Salto de Turing
# Salto de Turing

Em teoria da computabilidade, o Salto de Turing ou Operador de Salto de Turing, nomeado por Alan Turing, é um operador que designa para cada problema de decisão X um sucessivo problema de decisão mais difícil X ′ que tem a propriedade X ′ é não-decidível por uma Máquina Oráculo com um oráculo para X.
O operador é chamado de operador de salto porque ele aumenta o Grau de Turing do problema X. Ou seja, o problema X ′ é redutível por uma máquina de Turing (Redução de Turing) para X. O Teorema de Post estabelece um relacionamento entre o operador de Salto de Turing e a hierarquia aritmética de conjuntos pertencentes ao conjunto dos números naturais. Informalmente, dado um problema, o Salto de Turing retorna o conjunto de máquinas de Turing que param quando se é dado um acesso a um oráculo que resolve este problema.

## Definição

Dado um conjunto X e um Número de Gödel φ$_i$$^X$ das funções X-computáveis, o Salto de Turing X ′ de X é definido como:
    $X'=\{x\mid \varphi _{x}^{X}(x)\ {\mbox{é definido}}\}.$
O n-ésimo Salto de Turing X$^{(n)}$ é definido indutivamente por
    $X^{(0)}=X,\,$
    $X^{(n+1)}=(X^{(n)})'.\,$
O ω Salto X$^{(ω)}$ do X é a união das sequências de conjuntos X$^{(n)}$ para n ∈ N:
    $X^{(\omega )}=\{p_{i}^{k}\mid k\in X^{(i)}\},\,$
onde p$_i$ denota o i-ésimo primo.
A notação 0′ ou ∅′ é, de vez em quando, utilizado para o Salto de Turing de um conjunto vazio. Lê-se salto-zero ou, às vezes, primo-zero.
De forma similar, 0$^{(n)}$ é o n-ésimo salto do conjunto vazio. Para um n finito, esses conjuntos são relacionados à hierarquia aritmética.
O salto pode ser iterado por números Transfinitos: os conjuntos 0$^{(α)}$ para α < ω$_1$$^{CK}$, onde ω$_1$$^{CK}$ é o Ordinal de Church-Kleen, são muito relacionados à hierarquia hiperaritmética. Por trás de ω$_1$$^{CK}$, o processo pode ser contínuo através dos ordinais contáveis do Universo construível, utilizando métodos da teoria dos conjuntos(Hodes 1980). O Conceito também foi generalizado para ser estendido aos cardinais regulares incontáveis(Lubarsky 1987).

## Exemplos

* O Salto de Turing 0′ do conjunto vazio é Turing equivalente ao Problema da parada.
* Para cada n, o conjunto 0$^{(n)}$ é redutível por mapeamento (redução por mapeamento) no nível $\Sigma _{n}^{0}$ da hierarquia aritmética
* O conjunto dos números de Gödel das fórmulas com valor verdade na linguagem da Aritmética de Peano que possuem um predicado para X é computável através de X$^{(ω)}$.

## Propriedades

* X ′ é X-reconhecível (Conjuntos recursivamente enumeráveis) mas não é X-computável (Função computável)].
* Se A é Turing equivalente à B então A′ é Turing equivalente à B′. O Contrário desta implicação não é verdade
* (Shore E Slaman, 1999) A função de mapeamento X para X ′ é definida em uma ordem parcial dos graus de Turing.
Muitas das propriedades do operador de Salto de Turing são discutidos no artigo Grau de Turing.