Usuário(a):Rsvc/Grau de Turing

Em ciência da computação e na 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 deste conjunto. Este conceito é 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 informa quão difícil é resolver o problema de decisão associado ao mesmo.

Dois conjuntos são Turing Equivalentes se eles possuem o mesmo grau de insolubilidade; Cada grau de Turing é composto por uma coleção de conjuntos Turing equivalentes, de modo que dois conjuntos estão em diferentes graus de Turing se eles não são Turing equivalentes. Além disso, os graus de Turing são conjunto parcialmente ordenado, o que significa que se um conjunto X possui um grau de Turing menor que o de um conjunto Y então qualquer procedimento (não computável) que decida corretamente se algum número está em Y pode ser convertido efetivamente para um procedimento que decida corretamente se algum número está em X. É neste sentido que o grau de Turing de um conjunto correponde ao seu nível de insoubilidade algorítmica.

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

Turing Equivalência

Ver artigo principal: Redução de Turing

Para o restante do artigo, a palavra conjunto fará referência ao conjunto dos números naturais. Um conjunto X é dito Turing redutível a um conjunto Y se existe uma máquina de Turing oráculo que decide os menbros em X quando dado um oráculo que decide os membros em Y. A notação X ≤_T Y indica que X é turing redutível a Y.

Dois conjuntos X e Y são considerados 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 todo conjunto X, Y e Z:

• X ≡_T X
• X ≡_T Y implica que Y ≡_T X
• Se X ≡_T Y e Y ≡_T Z então X ≡_T Z.

Grau de Turing

O 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 é indicada por ${\mathcal {D}}$.

Os graus de Turing tem uma ordem parcial ≤ defina da seguinte maneira, [X] = [Y] se e somente se X ≤ Y. Existe um único grau de Turing contendo todos os conjuntos computáveis, e este grau é inferior a todos os outros graus. Ele é representado por 0(zero) pelo fato de ser o menor elemento do conjunto parcialmente ordenado (poset, em inglês partially ordered set) ${\mathcal {D}}$ (é comum utilizar letras em negrito para graus de Turing, a fim de diferenciá-los dos conjuntos. Quando nenhuma confusão pode ocorrer, como por exemplo com [X], não é necessário o uso do negrito).

Para quaisquer conjuntos X e Y, X ⊕ Y, escreve-se X ⊕ Y, é definido como a união dos conjuntos {2n : n ∈ X} e {2m+1 : m ∈ Y}. O grau de Turing de X ⊕ Y é o menor limitante superior dos graus de X e Y. Deste modo ${\mathcal {D}}$ é um semi-reticulado superior. O menor limitante superior de graus a e b é indicado por a ∪ b. Sabe-se que ${\mathcal {D}}$ não é um reticulado, pois há pares de graus sem maior limitante inferior.

Para qualquer conjunto X a notação X ′ significa o conjunto de índices de máquinas oráculo que param quando usam X como um oráculo. O conjunto X ′ é chamado de Salto Turing de X. O salto 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. Um importante exemplo é 0 ′, o grau do Problema da parada.

Propriedades básicas dos graus de Turing

• Cada grau de Turing é infinito contável, ou seja, contém exatamente $\aleph _{0}$ conjuntos.
• Existem $2^{\aleph _{0}}$ graus de Turing diferentes.
• Para cada grau a a desigualdade estrita a < a′ se mantém.
• Para cada grau a, o conjunto de graus abaixo de a é um máximo contável. O conjunto de graus maior que a possui tamanho igual a $2^{\aleph _{0}}$.

Estrutura dos graus de Turing

Uma grande quantidade de pesquisas têm sido realizadas na estrutura dos graus de Turing. O levantamento a seguir lista apenas alguns dos vários resultados conhecidos. Uma conclusão geral que pode ser tirada 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 todo grau diferente de zero a há um grau b incomparável a a.

• Existe um conjunto de $2^{\aleph _{0}}$ pares de graus de Turing incomparáveis.

• Existem pares de graus sem maior limite inferior. Portanto ${\mathcal {D}}$ não é um reticulado.

• Todo conjunto contável parcialmente ordenado pode ser incorporado nos graus de Turing.

• Não infinito, seqüência estritamente crescente de graus possui um menor limite superior.

Propriedades envolvendo o salto

• Para cada grau a existe um grau estritamente entre a e a′. Na verdade, existe uma sequência contável 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′; assim um grau b é chamado inferior em relação a a.

• Existe uma sequência infinita a_i de graus tal que a′_i+1 ≤ a_i para cada i.