Grau de Turing

Este artigo ou secção contém uma lista de referências no fim do texto, mas as suas fontes não são claras porque não são citadas no corpo do artigo, o que compromete a confiabilidade das informações. Ajude a melhorar este artigo inserindo citações no corpo do artigo. (Dezembro de 2024)

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.