Salto de Turing

Predefinição:Sem notas 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 Predefinição:Math um sucessivo problema de decisão mais difícil Predefinição:Math que tem a propriedade Predefinição:Math é não-decidível por uma Máquina Oráculo com um oráculo para Predefinição:Math.

O operador é chamado de operador de salto porque ele aumenta o Grau de Turing do problema Predefinição:Math. Ou seja, o problema Predefinição:Math é redutível por uma máquina de Turing (Redução de Turing) para Predefinição:Math. 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 Predefinição:Math e um Número de Gödel Predefinição:Math das funções Predefinição:Math-computáveis, o Salto de Turing Predefinição:Math de Predefinição:Math é definido como:

$X^{\prime }=\{x\mid {\phi }_x^X(x)\text{é definido}\}.$

O Predefinição:Math-ésimo Salto de Turing Predefinição:Math é definido indutivamente por

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

$X^{(n+1)}=(X^{(n)}{)}^{\prime }.$

O Predefinição:Math Salto Predefinição:Math do Predefinição:Math é a união das sequências de conjuntos Predefinição:Math para Predefinição:Math:

$X^{(\omega )}=\{p_i^k\mid k\in X^{(i)}\},$

onde Predefinição:Math denota o Predefinição:Math-ésimo primo.

A notação Predefinição:Math ou Predefinição:Math é, 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, Predefinição:Math é o Predefinição:Math-ésimo salto do conjunto vazio. Para um Predefinição:Math finito, esses conjuntos são relacionados à hierarquia aritmética.

O salto pode ser iterado por números Transfinitos: os conjuntos Predefinição:Math para Predefinição:Math, onde Predefinição:Math é o Ordinal de Church-Kleen, são muito relacionados à hierarquia hiperaritmética. Por trás de Predefinição:Math, 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 Predefinição:Math do conjunto vazio é Turing equivalente ao Problema da parada.
• Para cada Predefinição:Math, o conjunto Predefinição:Math é redutível por mapeamento (redução por mapeamento) no nível ${\mathrm{\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 Predefinição:Math é computável através de Predefinição:Math.

Propriedades

• Predefinição:Math é Predefinição:Math-reconhecível (Conjuntos recursivamente enumeráveis) mas não é Predefinição:Math-computável (Função computável)].
• Se Predefinição:Math é Turing equivalente à Predefinição:Math então Predefinição:Math é Turing equivalente à Predefinição:Math. O Contrário desta implicação não é verdade
• (Shore E Slaman, 1999) A função de mapeamento Predefinição:Math para Predefinição:Math é 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
• Predefinição:Citar periódico
• Predefinição:Citar livro
• Predefinição:Cite article
• Predefinição:Citar livro
• Predefinição:Citar periódico
• Predefinição:Citar livro