Grau de Turing

Em ciência da computação e lógica matemática o grau de Turing ou grau de insolubilidade de um conjunto de números naturais mede o nível de insolubilidade algorítmica do conjunto. O conceito de grau de Turing é fundamental na teoria da computabilidade, onde conjuntos de números naturais são frequentemente considerados como problemas de decisão, o grau de Turing de um conjunto diz o quão difícil é resolver o problema de decisão associado com o conjunto.

Dois conjuntos são Turing equivalentes, se tiverem o mesmo nível de insolubilidade; cada grau de Turing é uma coleção de conjuntos Turing equivalentes, de modo que dois conjuntos estão em graus de Turing diferentes exatamente quando não são Turing equivalentes. Além disso, os graus de Turing são parcialmente ordenada de modo que, se o grau de Turing de um conjunto “X” é menor que o grau de Turing de um conjunto “Y”, então qualquer procedimento (computável) que correctamente decide se os números estão em “Y” pode ser convertido de maneira eficaz a um procedimento que corretamente decide se os números estão em “X”. É neste sentido que o grau de Turing de um conjunto corresponde ao seu nível de insolubilidade algorítmica.

Os graus de Turing foram introduzidas por Emil Leon Post (1944), e muitos resultados fundamentais foram estabelecidos por Stephen Cole Kleene e Post (1954). Os graus de Turing têm sido uma área de intensa pesquisa desde então. Muitas provas na área fazem uso de uma técnica de prova conhecida como o método da prioridade.

Turing equivalência

Ver artigo principal: Redução de Turing

Para o resto deste artigo, a palavra conjunto de palavras vai se referir a um conjunto de números naturais. Um conjunto X é dito ser Turing redutível a um conjunto Y se existe uma máquina de Turing oráculo que decide participação em X quando dado um oráculo para ser membro de Y. A notação X ≤_T Y indica que X é Turing redutível a Y.

Dois conjuntos de X e Y são definidos como sendo Turing equivalentes se X é Turing redutível a Y e Y é Turing redutível a X. A notação X ≡_T Y indica que X e Y são Turing equivalentes. A relação ≡_T pode ser vista como uma relação de equivalência, o que significa que para todos os conjuntos de X, Y e Z:

• X ≡_T X
• X ≡_T Y implies Y ≡_T X
• If X ≡_T Y and Y ≡_T Z then X ≡_T Z.

Grau de Turing

Um grau de Turing é uma classe de equivalência da relação ≡_T. A notação [X] denota a classe de equivalência que contém um conjunto X. A coleção inteira de graus de Turing é denotada como ${\mathcal {D}}$.

Os graus de Turing tem uma ordem parcial ≤ definida tal que [X] ≤ [Y] se e somente se ≤ X ≤_T Y. Existe um único grau de Turing que contém todos os conjuntos computáveis, e este grau é inferior a todos os outro graus. É denotado 0 (zero), porque é o menor elemento do poset ${\mathcal {D}}$. (É comum o uso de notação negrito para graus de Turing, a fim de distingui-lo dos conjuntos. Quando alguma confusão pode ocorrer, como com [X], a notação em negrito não é necessária.)

Para qualquer conjuntos X e Y, X junção Y, escrito 'X ⊕ Y, é definida como a união dos conjuntos {2n : n ∈ X} e {2m+1 : m ∈ Y}. O grau de Turing X ⊕ Y é o menor limitante superior dos graus de X e Y. Assim, ${\mathcal {D}}$ é uma junção ‘semi-reticular’. O menor limite superior dos graus a e b é denotado a ∪ b. Sabe-se que ${\mathcal {D}}$ não é um reticulado, uma vez que existem pares de graus com a maior sem limitante inferior.

Para qualquer conjunto X a notação X′ denota o conjunto de índices de máquinas oráculo que param quando usando X como um oráculo. O conjunto X′ é chamado Salto de Turing de X. O Salto de Turing de um grau [X] é definido como sendo o grau [X′]; esta é uma definição válida porque X′ ≡_T Y′ sempre que X ≡_T Y. O exemplo chave é 0′, o grau do Problema da Parada.

Propriedades básicas dos graus de Turing

• Cada grau de Turing é infinito contável, ou seja, ela contém exatamente conjuntos $\aleph _{0}$.
• Há $2^{\aleph _{0}}$ graus de Turing distintos.
• Para cada grau a de desigualdade estrita detém a < a′.
• Para cada grau a, o conjunto de graus abaixo de a é máximo contável. O conjunto de graus maiores que a tem o tamanho $2^{\aleph _{0}}$.

Estrutura dos graus de Turing

Uma grande parte da pesquisa foi conduzida para a estrutura dos graus de Turing. A pesquisa a seguir lista apenas alguns dos muitos resultados conhecidos. Uma conclusão geral que pode ser retirada da pesquisa é que a estrutura dos graus de Turing é extremamente complicada.

Propriedades de Ordem

• Existem graus mínimos. Um grau a é mínimo, se a é diferente de zero e não há nenhum grau entre 0 e a. Assim, a relação de ordem sobre os graus não é uma ordem densa.
• Para cada grau diferente de zero, existe um grau b incomparável com a.
• Há um conjunto de $2^{\aleph _{0}}$ pares graus de Turing incomparáveis .
• Existem pares de graus com a maior sem limite inferior. Assim, ${\mathcal {D}}$ não é um reticulado.
• Cada conjunto contável parcialmente ordenado pode ser incorporado nos graus de Turing.
• Nenhuma seqüência infinita estritamente crescente de graus tem um menor limite superior.

Propriedades envolvendo o salto

• Para todo grau a de que existe estritamente um grau entre a e a′. Na verdade, há uma seqüência enumerável de pares de graus incomparáveis entre a e a′.
• Um grau a é da forma b′ se e somente se 0′ ≤ a.
• Para qualquer grau a existe um grau b tal que a < b e b′ = a′; o tal grau b é chamado relativo inferior a a.
• Há uma seqüência infinita de graus a_i tal que a′_i+1 ≤ a_i para cada i.

Propriedades lógicas

• Simpson (1977) mostrou que a teoria de primeira ordem de ${\mathcal {D}}$ na linguagem ⟨ ≤, = ⟩ ou ⟨ ≤, ′, =⟩ é equivalente por mapeamento à teoria da aritmética de segunda ordem verdadeira. Isto indica que a estrutura de ${\mathcal {D}}$ é extremamente complicada.
• Shore e Slaman (1999) mostrou que o operador salto é definível na estrutura de primeira ordem dos graus com a linguagem ⟨ ≤, =⟩.

Estrutura Recursivamente Enumerável dos Graus de Turing

Um grau é chamado r.e. (recursivamente enumerável) se ele contém um conjunto recursivamente enumerável. Cada grau recursivamente enumerável é menor ou igual a 0′, mas nem todos os graus menores que 0′ é um grau recursivamente enumerável.

• (G. E. Sacks, 1964) Os graus recursivamente enumeráveis são densos; entre qualquer dois graus recursivamente enumeráveis existe um terceiro grau recursivamente enumerável.
• (A. H. Lachlan, 1966a and C. E. M. Yates, 1966) Existem dois graus recursivamente enumeráveis sem maior limite inferior nos graus recursivamente enumerável.
• (A. H. Lachlan, 1966a and C. E. M. Yates, 1966) Existe um par de graus re diferente de zero, cujo maior limite inferior é 0.
• (S. K. Thomason, 1971) Cada reticulado finito distributivo pode ser incorporado aos graus recursivamente enumeráveis. De fato, a álgebra booleana atômica contável pode ser incorporada de uma forma que preserve supremo e ínfimo.
• (A. H. Lachlan and R. I. Soare, 1980) Nem todos os reticulados finitos podem ser incorporados nos graus recursivamente enumeráveis (através de uma inclusão que preserva suprema e ínfima). O seguinte reticulado particular não pode ser incluído nos graus r.e.:

• (A. H. Lachlan, 1966b) Não há par de graus recursivamente enumeráveis, cujo maior limite inferior é 0 e cujo limite superior é de 0′. Este resultado é chamado informalmente o teorema nondiamond.
• (L. A. Harrington and T. A. Slaman, see Nies, Shore, and Slaman (1998)) A teoria de primeira-ordem dos graus recursivamente enumeráveis na linguagem ⟨ 0, ≤, = ⟩ equivalente por mapeamento a teoria da aritmética verdadeira de primeira-ordem.

Problema de Post e do método de prioridade

Emil Post estudou os graus de Turing recursivamente enumeráveis e questionou se há algum grau recursivamente enumerável estritamente entre 0 e 0′. O problema da construção de tal grau (ou mostrar que não existe nenhum) ficou conhecido como problema de Post. Este problema foi resolvido de forma independente por Friedberg e Muchnik na década de 1950, que mostrou que estes graus recursivamente enumeráveis intermediários existem. As provas deles, cada uma, desenvolveu o mesmo método novo para a construção de graus recursivamente enumeráveis que veio a ser conhecido como o método da prioridade. O método da prioridade é agora a principal técnica para estabelecer resultados sobre conjuntos recursivamente enumeráveis.

A ideia do método da prioridade para a construção de um conjunto recursivamente enumerável de X é listar uma sequência contável de requisitos que X deve satisfazer. Por exemplo, para construir um conjunto recursivamente enumerável X entre 0 e 0′ é suficiente satisfazer os requisitos A_e e B_e para cada numero natural e, onde A_e requer que a máquina oráculo com índice e não compute 0′ a partir de X, e B_e requer que a máquina de Turing com índice e (e sem oráculo) não compute X. Estes requisitos são postos em uma ordem de prioridade, que é uma bijeção explícita dos requisitos e números naturais. A prova procede indutivamente com uma fase para cada número natural; estas etapas podem ser pensadas como passos de tempo durante o qual o conjunto X é enumerado. Em cada estagio, os números podem ser postos em X ou sempre prevenir a entrada em X, na tentativa de satisfazer os requisitos (isto é, forçá-los a reter uma vez que todos de X tenham sido enumerados). Por vezes, um número pode ser enumerado em X para satisfazer um requisito, mas fazendo isso iria tornar um requisito anteriormente satisfeito em um requisito insatisfeito (isto é, lesá-lo). A ordem de prioridade sobre os requisitos é utilizada para determinar quais requisitos satisfazer neste caso. A ideia informal é que, se um requisito é lesado, então ele irá eventualmente parar de ser lesado após todos os requisitos de maior prioridade parar de serem lesados, embora nem todos os argumentos de prioridade tenham essa propriedade. Um argumento deve ser construído tal que o conjunto X global é recursivamente enumerável e satisfaz todos os requisitos. Argumentos de prioridade podem ser usados para provar muitos fatos sobre os conjuntos recursivamente enumeráveis; os requisitos utilizados e a maneira em que são satisfeitos, deve ser cuidadosamente escolhida para produzir o resultado desejado.

Referências

Monografias (nivel graduação)

• Cooper, S.B. Computability theory. Chapman & Hall/CRC, Boca Raton, FL, 2004. ISBN 1-58488-237-9
• Cutland, N. Computability. Cambridge University Press, Cambridge-New York, 1980. ISBN 0-521-22384-9; ISBN 0-521-29465-7

Monografias e artigos de pesquisa (nivel pós-graduação)

• Ambos-Spies, K. and Fejer, P. Degrees of Unsolvability. Unpublished. http://www.cs.umb.edu/~fejer/articles/History_of_Degrees.pdf
• Lerman, M. Degrees of unsolvability. Perspectives in Mathematical Logic. Springer-Verlag, Berlin, 1983. ISBN 3-540-12155-2
• Rogers, H. The Theory of Recursive Functions and Effective Computability, MIT Press. ISBN 0-262-68052-1; ISBN 0-07-053522-1
• Simpson, S. Degrees of unsolvability: a survey of results. Handbook of Mathematical Logic, North-Holland, 1977, pp. 631--652.
• Shore, R. The theories of the T, tt, and wtt r.e. degrees: undecidability and beyond. Proceedings of the IX Latin American Symposium on Mathematical Logic, Part 1 (Bahía Blanca, 1992), 61--70, Notas Lógica Mat., 38, Univ. Nac. del Sur, Bahía Blanca, 1993.
• Soare, R. Recursively enumerable sets and degrees. Perspectives in Mathematical Logic. Springer-Verlag, Berlin, 1987. ISBN 3-540-15299-7
• Soare, Robert I. Recursively enumerable sets and degrees. Bull. Amer. Math. Soc. 84 (1978), no. 6, 1149--1181.