Salto de Turing

Este artigo ou secção contém uma lista de referências no fim do texto, mas as suas fontes não são claras porque não são citadas no corpo do artigo, o que compromete a confiabilidade das informações. Ajude a melhorar este artigo inserindo citações no corpo do artigo. (julho de 2012)

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:

${\displaystyle X'=\{x\mid \varphi _{x}^{X}(x)\ {\mbox{é definido}}\}.}$

O n-ésimo Salto de Turing X⁽ⁿ⁾ é definido indutivamente por

${\displaystyle X^{(0)}=X,\,}$

${\displaystyle X^{(n+1)}=(X^{(n)})'.\,}$

O ω Salto X^(ω) do X é a união das sequências de conjuntos X⁽ⁿ⁾ para n ∈ N:

${\displaystyle 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 ${\displaystyle \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  A referência emprega parâmetros obsoletos |coautor= (ajuda)
• 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