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 um sucessivo problema de decisão mais difícil que tem a propriedade é não-decidível por uma Máquina Oráculo com um oráculo para .
O operador é chamado de operador de salto porque ele aumenta o Grau de Turing do problema . Ou seja, o problema é redutível por uma máquina de Turing (Redução de Turing) para . 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 e um Número de Gödel das funções -computáveis, o Salto de Turing de é definido como:
O -ésimo Salto de Turing é definido indutivamente por
O Salto do é a união das sequências de conjuntos para :
onde denota o -ésimo primo.
A notação 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, é o -ésimo salto do conjunto vazio. Para um finito, esses conjuntos são relacionados à hierarquia aritmética.
O salto pode ser iterado por números Transfinitos: os conjuntos para , onde é o Ordinal de Church-Kleen, são muito relacionados à hierarquia hiperaritmética. Por trás de , 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 do conjunto vazio é Turing equivalente ao Problema da parada. Para cada , o conjunto é redutível por mapeamento (redução por mapeamento) no nível 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 é computável através de .
Propriedades
é -reconhecível (Conjuntos recursivamente enumeráveis) mas não é -computável (Função computável)]. Se é Turing equivalente à então é Turing equivalente à . O Contrário desta implicação não é verdade (Shore E Slaman, 1999) A função de mapeamento para é 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
Categoria:Teoria da computação