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^0_n$ 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.. (June 1980). "Jumping Through the Transfinite: The Master Code Hierarchy of Turing Degrees". Journal of Symbolic Logic 45 (2): 204–220. Association for Symbolic Logic. DOI:10.2307/2273183.
• Lerman, M.. Degrees of unsolvability: local and global theory. [S.l.]: Berlin; New York: Springer-Verlag, 1983. ISBN 3-540-12155-2
• Predefinição:Cite article
• Rogers Jr, H.. Theory of recursive functions and effective computability. [S.l.]: MIT Press Cambridge, MA, USA, 1987. ISBN 0-07-053522-1
• Shore, R.A.; Slaman, T.A.. (1999). "Defining the Turing jump". Mathematical Research Letters 6 (5–6): 711–722.
• Soare, R.I.. Recursively Enumerable Sets and Degrees: A Study of Computable Functions and Computably Generated Sets. [S.l.]: Springer, 1987. ISBN 3-540-15299-7