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⁽ⁿ⁾ é 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⁽ⁿ⁾ 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⁽ⁿ⁾ é 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 α < ω₁^CK, onde ω₁^CK é o Ordinal de Church-Kleen, são muito relacionados à hierarquia hiperaritmética. Por trás de ω₁^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⁽ⁿ⁾ é 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.

Referências

• Ambos-Spies, K. and Fejer, P. Degrees of Unsolvability. Unpublished. http://www.cs.umb.edu/~fejer/articles/History_of_Degrees.pdf
• Hodes, Harold T. (1980). «Jumping Through the Transfinite: The Master Code Hierarchy of Turing Degrees». Association for Symbolic Logic. Journal of Symbolic Logic. 45 (2): 204–220. JSTOR 2273183. doi:10.2307/2273183 
• Lerman, M. (1983). Degrees of unsolvability: local and global theory. [S.l.]: Berlin; New York: Springer-Verlag. ISBN 3-540-12155-2 
• Lubarsky, Robert S. (1987). «Uncountable Master Codes and the Jump Hierarchy». Journal of Symbolic Logic. 52 (4). pp. 952–958. JSTOR 2273829 
• Rogers Jr, H. (1987). Theory of recursive functions and effective computability. [S.l.]: MIT Press Cambridge, MA, USA. ISBN 0-07-053522-1 
• Shore, R.A.; Slaman, T.A. (1999). «Defining the Turing jump» (PDF). Mathematical Research Letters. 6 (5–6): 711–722. Consultado em 13 de julho de 2008. Arquivado do original (PDF) em 9 de julho de 2008 
• Soare, R.I. (1987). Recursively Enumerable Sets and Degrees: A Study of Computable Functions and Computably Generated Sets. [S.l.]: Springer. ISBN 3-540-15299-7