A Arquitetura da Computabilidade
Coleção Escola de Lógica Matemática
JOÃO CARLOS MOREIRA
Doutor em Matemática
Universidade Federal de Uberlândia
Copyright©2013-2025 Coleção Escola de Lógica Matemática. Todos os direitos reservados.
Imagine um programa de computador que pudesse examinar qualquer outro programa e determinar, com certeza absoluta, se ele vai parar ou continuar executando para sempre. Seria o sonho de todo programador, o fim dos travamentos e loops infinitos. Porém, em 1936, Alan Turing demonstrou algo extraordinário: tal programa não pode existir. Esta impossibilidade fundamental não é uma limitação tecnológica, mas uma barreira matemática intransponível que revela a existência de uma hierarquia infinita de problemas computacionais, cada um mais complexo que o anterior. Os graus de Turing são a estrutura matemática que organiza esta hierarquia, mapeando o território do computável e do incomputável com precisão cirúrgica.
O problema da parada surgiu naturalmente quando matemáticos começaram a questionar os limites da computação. Se pudéssemos construir uma máquina que decidisse se qualquer programa para, teríamos resolvido inúmeros problemas matemáticos de uma só vez. Poderíamos verificar conjecturas simplesmente escrevendo programas que as testassem e usando nossa máquina mágica para saber se encontrariam contraexemplos. Mas Turing mostrou que esta máquina leva a uma contradição lógica inescapável.
A técnica que Turing usou, conhecida como diagonalização, tem raízes no trabalho de Cantor sobre infinitos. Assim como Cantor provou que existem mais números reais que naturais, Turing mostrou que existem mais problemas que algoritmos para resolvê-los. A ideia é construir um problema que difere de cada possível solução algorítmica em pelo menos um aspecto, garantindo que nenhum algoritmo pode resolvê-lo completamente.
O problema da parada é apenas o primeiro degrau de uma escada infinita. Podemos perguntar: existe um programa que decide se outro programa resolve o problema da parada? Esta meta-parada também é indecidível, mas de uma forma ainda mais profunda. E podemos continuar: a meta-meta-parada, e assim por diante, criando uma hierarquia infinita de problemas cada vez mais insolúveis.
Para estudar esta hierarquia, introduzimos o conceito de oráculo — uma caixa-preta hipotética que resolve instantaneamente um problema específico. Uma máquina de Turing com oráculo para o problema da parada poderia decidir a parada de qualquer programa comum, mas encontraria seus próprios problemas indecidíveis. Este conceito nos permite explorar mundos computacionais além do nosso alcance real.
A descoberta de Turing teve consequências profundas para toda a matemática. O sonho de Hilbert de um procedimento mecânico para decidir verdades matemáticas foi destruído. Gödel já havia mostrado que existem verdades não demonstráveis; Turing mostrou que não podemos nem mesmo reconhecer mecanicamente quais afirmações têm demonstrações. Esta limitação fundamental moldou nossa compreensão moderna do que é possível conhecer e provar.
Nem todos os problemas indecidíveis são igualmente difíceis. Alguns podem ser resolvidos se tivermos acesso a oráculos para outros problemas. Esta observação leva naturalmente ao conceito de graus de Turing — classes de equivalência de problemas que são mutuamente redutíveis. Dois problemas têm o mesmo grau se cada um pode ser resolvido usando o outro como oráculo.
Embora o problema da parada seja indecidível em geral, suas implicações práticas são enormes. Compiladores usam análises aproximadas para detectar loops infinitos prováveis. Verificadores de software trabalham com subconjuntos decidíveis do problema. A teoria dos graus de Turing guia o desenvolvimento de ferramentas que navegam inteligentemente entre o possível e o impossível.
Os graus de Turing revelam que o mundo do incomputável não é um caos uniforme, mas possui estrutura rica e surpreendente. Existem graus mínimos (acima do computável), graus maximais em certas classes, e uma complexidade que rivaliza com qualquer estrutura matemática conhecida. Esta organização do impossível é um dos insights mais profundos da teoria da computação.
A teoria dos graus de Turing transcende a matemática e a computação, tocando questões filosóficas fundamentais sobre conhecimento, mente e realidade. Se nossa mente é uma máquina de Turing, existem verdades que nunca poderemos conhecer algoritmicamente. Se não é, o que nos torna diferentes? Estas questões continuam a inspirar debates sobre consciência, inteligência artificial e os limites do conhecimento humano.
O problema da parada e a hierarquia de graus de Turing que dele emerge representam uma das descobertas mais profundas da matemática do século XX. Ao estabelecer limites precisos para o que pode ser computado, Turing não apenas respondeu a questões fundamentais sobre a natureza da matemática, mas também lançou as bases para a ciência da computação moderna. Como veremos nos próximos capítulos, esta hierarquia é apenas o começo de uma jornada fascinante pelo território do computável e do incomputável, onde cada novo teorema revela paisagens inesperadas de complexidade e beleza matemática.
Antes dos computadores existirem fisicamente, Alan Turing imaginou uma máquina abstrata de simplicidade enganosa: uma fita infinita, um cabeçote que lê e escreve símbolos, e um conjunto finito de regras. Esta máquina teórica, hoje conhecida como máquina de Turing, captura a essência de toda computação possível. Surpreendentemente, desde calculadoras simples até os supercomputadores mais poderosos, todos são equivalentes em poder computacional a esta humilde máquina imaginária. Neste capítulo, exploraremos como estas máquinas definem precisamente o que significa "computar" e estabelecem a base matemática para os graus de Turing.
Uma máquina de Turing consiste em componentes surpreendentemente simples. Imagine uma fita infinita dividida em células, cada uma contendo um símbolo de um alfabeto finito. Um cabeçote de leitura/escrita move-se sobre a fita, uma célula por vez. A máquina possui um conjunto finito de estados internos e uma tabela de transições que determina, baseado no estado atual e no símbolo lido, qual símbolo escrever, para onde mover o cabeçote e qual será o próximo estado.
A genialidade de Turing foi perceber que qualquer processo de cálculo que possa ser descrito precisamente pode ser executado por sua máquina. Somar números, ordenar listas, verificar primalidade — todos estes processos podem ser codificados como sequências de passos simples que a máquina executa mecanicamente. A máquina não "entende" o que faz; apenas segue regras, passo a passo, até alcançar um estado final (ou continuar para sempre).
Independentemente, Church e Turing chegaram à mesma conclusão revolucionária: toda função computável intuitivamente pode ser computada por uma máquina de Turing. Esta tese, embora não demonstrável matematicamente (pois "computável intuitivamente" não é um conceito formal), tornou-se o fundamento da ciência da computação. Todos os modelos de computação propostos — cálculo lambda, funções recursivas, autômatos celulares — mostraram-se equivalentes às máquinas de Turing.
Uma descoberta fundamental é que máquinas de Turing podem ser codificadas como números. Cada máquina pode ser descrita por uma string finita que especifica seus estados, alfabeto e transições. Esta string pode ser convertida em um número natural único. Mais impressionante ainda: existe uma máquina de Turing universal que pode simular qualquer outra máquina de Turing, dado seu código e entrada. Este é o princípio por trás dos computadores modernos programáveis.
Uma função é computável se existe uma máquina de Turing que, para cada entrada, produz a saída correta e para. Um conjunto é decidível (ou recursivo) se sua função característica é computável — existe uma máquina que sempre para e responde "sim" ou "não" corretamente sobre pertinência. Conjuntos recursivamente enumeráveis são aqueles para os quais existe uma máquina que aceita exatamente seus elementos, mas pode não parar para não-elementos.
Como máquinas de Turing podem ser codificadas como números, podemos enumerá-las: M₀, M₁, M₂, ... Esta enumeração permite aplicar diagonalização para provar existência de funções não-computáveis. Definimos uma função que difere da i-ésima máquina na i-ésima entrada, garantindo que não é computada por nenhuma máquina da lista. Como a lista contém todas as máquinas, a função é não-computável.
Com o formalismo das máquinas de Turing, podemos expressar precisamente o problema da parada: dado o código de uma máquina M e uma entrada x, M para em x? Se existisse uma máquina H que sempre parasse e respondesse corretamente, poderíamos construir uma máquina D que se comporta paradoxalmente quando aplicada a seu próprio código, levando à contradição clássica que prova a indecidibilidade.
Um problema A é redutível a B se podemos transformar instâncias de A em instâncias de B preservando as respostas. Se A é redutível a B e B é decidível, então A também é. O problema da parada é completo para a classe dos conjuntos recursivamente enumeráveis: todo conjunto r.e. reduz ao problema da parada. Esta completude o torna um benchmark natural para medir complexidade computacional.
Vários teoremas fundamentais emergem do estudo das máquinas de Turing. O teorema de Rice afirma que toda propriedade não-trivial de funções computáveis é indecidível. O teorema s-m-n mostra como parametrizar computações. O teorema da recursão permite programas que operam em seu próprio código. Estes resultados formam o arsenal técnico para estudar graus de Turing.
Variações das máquinas de Turing incluem máquinas não-determinísticas, probabilísticas, quânticas e com oráculos. Surpreendentemente, exceto as com oráculos, todas têm o mesmo poder computacional para funções totais — podem simular umas às outras. Máquinas com oráculos, porém, acessam informação não-computável, permitindo explorar níveis superiores da hierarquia de Turing.
As máquinas de Turing são muito mais que um modelo teórico — elas definem os limites fundamentais da computação. Ao formalizar precisamente o que significa calcular, Turing nos deu as ferramentas para explorar não apenas o que podemos computar, mas também para mapear o vasto território do incomputável. Como veremos no próximo capítulo, a noção de redutibilidade entre problemas, formalizada através destas máquinas, nos permitirá construir a intrincada estrutura dos graus de Turing, revelando a surpreendente organização hierárquica dos problemas insolúveis.
Se você pudesse resolver instantaneamente qualquer equação matemática, poderia usar esse poder para prever o tempo? Se soubesse o futuro do mercado de ações, poderia curar doenças? Estas questões sobre transformar a solução de um problema na solução de outro são a essência da redutibilidade de Turing. Como uma linguagem universal para comparar dificuldades computacionais, a redutibilidade nos permite dizer precisamente quando um problema é "pelo menos tão difícil quanto" outro. Esta relação fundamental organiza todos os problemas computacionais em uma vasta hierarquia, onde cada nível representa um grau diferente de insolubilidade.
Reduzir o problema A ao problema B significa usar B como uma ferramenta para resolver A. Se conseguirmos fazer isso, então A não pode ser mais difícil que B — afinal, qualquer método para resolver B automaticamente nos dá um método para resolver A. Esta ideia simples tem consequências profundas: se A é redutível a B e sabemos que A é impossível de resolver, então B também deve ser impossível.
Para formalizar redutibilidade, introduzimos máquinas de Turing com oráculo. Imagine uma máquina de Turing comum, mas com um poder adicional: ela pode fazer perguntas a um oráculo sobre pertinência a um conjunto específico B. O oráculo responde instantaneamente e corretamente. Se esta máquina aumentada consegue decidir o conjunto A, dizemos que A é Turing-redutível a B.
Considere o problema de determinar se uma máquina de Turing aceita alguma entrada (problema da vacuidade). Podemos reduzi-lo ao problema da parada: para cada possível entrada, perguntamos ao oráculo da parada se a máquina para nela. Se para e aceita em alguma entrada, o conjunto não é vazio. Esta redução mostra que a vacuidade é pelo menos tão difícil quanto a parada.
A redutibilidade de Turing é reflexiva (todo problema reduz a si mesmo) e transitiva (se A reduz a B e B reduz a C, então A reduz a C). Porém, não é antissimétrica — existem problemas distintos que se reduzem mutuamente. Esta observação leva naturalmente à definição de equivalência de Turing: A e B são Turing-equivalentes quando cada um reduz ao outro.
Além da redutibilidade de Turing, existem noções mais restritivas. Redutibilidade many-one (ou m-redutibilidade) requer uma função computável que transforma instâncias de A em instâncias de B. Redutibilidade um-um adiciona a exigência de injetividade. Redutibilidade em tempo polinomial é crucial para teoria da complexidade. Cada tipo captura diferentes aspectos da relação entre problemas.
A redutibilidade de Turing permite consultas adaptativas — a próxima pergunta pode depender de respostas anteriores. Isto a torna mais poderosa que reduções uniformes como truth-table, onde todas as perguntas são determinadas antecipadamente. Esta adaptatividade é crucial para muitas reduções naturais e reflete como realmente resolvemos problemas: aprendendo com informação parcial.
Um conjunto é completo para uma classe se pertence à classe e todo membro da classe reduz a ele. O problema da parada é Turing-completo para os conjuntos recursivamente enumeráveis. K = {x : φₓ(x) converge} é outro conjunto r.e.-completo fundamental. Conjuntos completos servem como representantes canônicos de suas classes de complexidade.
Classes de equivalência sob Turing-equivalência são chamadas graus de Turing. Dois conjuntos têm o mesmo grau se são inter-redutíveis. O grau de um conjunto captura sua complexidade computacional intrínseca, abstraindo detalhes específicos de codificação. Esta abstração revela a estrutura fundamental da hierarquia computacional.
Surpreendentemente, existem conjuntos A e B tais que nem A ≤ᴛ B nem B ≤ᴛ A. Estes conjuntos incomparáveis não podem ser ordenados por dificuldade — cada um possui informação que o outro não pode computar. A existência de graus incomparáveis mostra que a hierarquia computacional não é linear, mas forma uma estrutura parcialmente ordenada extremamente complexa.
Embora abstrata, a redutibilidade tem aplicações concretas. Em criptografia, a segurança de sistemas frequentemente depende da redutibilidade de quebrar o sistema a problemas reconhecidamente difíceis. Em inteligência artificial, reduzimos problemas de aprendizado a otimização. Em bioinformática, reduzimos análise de proteínas a problemas de grafos.
A redutibilidade de Turing é a linguagem que usamos para comparar o incomparável — problemas que transcendem a computação ordinária. Ao estabelecer quando um problema pode ser transformado em outro, criamos um mapa do território computacional que revela conexões surpreendentes entre áreas aparentemente distintas. Como veremos no próximo capítulo, existe uma operação especial, o salto de Turing, que nos permite subir sistematicamente nesta hierarquia, revelando sempre novos níveis de incomputabilidade acima de qualquer ponto que possamos alcançar.
Imagine uma escada infinita onde cada degrau representa um nível de impossibilidade computacional. O salto de Turing é a operação mágica que nos permite subir esta escada, sempre encontrando problemas mais difíceis, não importa quão alto já tenhamos chegado. Como uma função que transforma qualquer grau de dificuldade em um estritamente maior, o salto revela que não existe um "problema mais difícil possível" — sempre há algo ainda mais incomputável além do horizonte. Esta descoberta fundamental mostra que a hierarquia da incomputabilidade não tem topo, estendendo-se infinitamente em complexidade crescente.
Para qualquer conjunto A, o salto de A, denotado A', é o problema da parada relativizado a A. Formalmente, A' = {x : φₓᴬ(x) converge}, onde φₓᴬ representa a x-ésima máquina de Turing com oráculo para A. Em essência, A' responde: "esta máquina com acesso a A para em sua própria descrição?" Esta definição elegante captura a ideia de subir um nível na hierarquia computacional.
Aplicando o salto repetidamente ao conjunto vazio, obtemos a hierarquia aritmética: ∅, ∅', ∅'', ∅''', ... Cada nível desta hierarquia corresponde a uma classe de complexidade lógica. ∅' contém informação sobre parada de máquinas, ∅'' sobre parada de máquinas com oráculo para parada, e assim por diante. Esta torre infinita de complexidade crescente tem conexões profundas com a lógica matemática.
Um resultado surpreendente de Friedberg mostra que a operação de salto não é sobrejetora nos graus r.e.: existem graus r.e. que não são o salto de nenhum grau. Isto revela uma assimetria fundamental na estrutura dos graus — nem todo nível de complexidade pode ser alcançado aplicando o salto a algo mais simples. Esta descoberta abriu caminho para o estudo profundo da estrutura fina dos graus.
Uma propriedade crucial do salto é sua invariância: se A ≡ᴛ B, então A' ≡ᴛ B'. Isto significa que o salto está bem-definido nos graus de Turing, não apenas em conjuntos individuais. Esta invariância permite estudar o salto como operação na estrutura dos graus, revelando padrões que seriam invisíveis ao olhar conjuntos específicos.
Existe uma conexão profunda entre o salto e a definibilidade em aritmética. Conjuntos em ∅⁽ⁿ⁾ correspondem exatamente aos definíveis por fórmulas aritméticas com n alternâncias de quantificadores. Esta correspondência, conhecida como hierarquia aritmética de Kleene, une computabilidade e lógica de forma fundamental, mostrando que complexidade computacional e complexidade lógica são faces da mesma moeda.
O salto pode ser iterado além dos números naturais, através dos ordinais transfinitos. Para ordinais limites λ, definimos A⁽λ⁾ como o join (união efetiva) de todos A⁽α⁾ para α < λ. Esta extensão transfinita revela níveis de incomputabilidade que transcendem qualquer iteração finita, alcançando reinos de complexidade inimagináveis.
Dado um grau b, quais graus a satisfazem a' = b? Este problema de inversão do salto tem respostas surpreendentes. Para b > 0', sempre existem soluções, mas nunca uma única. De fato, existem sempre continuum-muitas soluções! Este resultado, provado por Friedberg e Shoenfield, mostra a riqueza estrutural escondida na operação de salto.
Graus são classificados por seu comportamento sob o salto. Graus baixos satisfazem a' = 0'', comportando-se como o grau computável quanto ao salto. Graus altos satisfazem a' = 0''', tendo máxima complexidade de salto possível para graus r.e. Graus intermediários formam uma região complexa com propriedades fascinantes.
O salto aparece naturalmente em muitos contextos. Em teoria da demonstração, corresponde a adicionar consistência de teorias. Em análise, relaciona-se com diferenciabilidade de funções descontínuas. Em teoria dos jogos, determina estratégias vencedoras em jogos infinitos. Estas conexões mostram que o salto captura algo fundamental sobre aumentar poder dedutivo.
Filosoficamente, o salto representa barreiras intransponíveis ao conhecimento algorítmico. Cada aplicação do salto nos leva a um novo reino de incomputabilidade, revelando camadas sempre mais profundas de impossibilidade. Não importa quanto poder computacional tenhamos, o salto sempre nos mostra problemas além de nosso alcance.
O salto de Turing é uma das construções mais elegantes e profundas da matemática. Como uma escada que sempre tem mais um degrau, não importa quão alto subamos, ele revela que a incomputabilidade não é um fenômeno binário — computável ou não — mas possui gradações infinitamente sutis. Esta operação simples, que apenas pergunta sobre parada relativizada, gera toda a complexidade da hierarquia aritmética e além. No próximo capítulo, exploraremos a estrutura global que emerge quando consideramos todos os graus e suas relações, revelando um universo matemático de complexidade e beleza surpreendentes.
Os graus de Turing formam um universo matemático próprio, com geografia tão rica e complexa quanto qualquer estrutura já estudada. Como um mapa de territórios impossíveis, a estrutura dos graus revela paisagens de incomputabilidade onde montanhas de complexidade se erguem infinitamente, vales de graus mínimos se escondem, e vastos planaltos de incomparabilidade se estendem em todas as direções. Este capítulo explora a arquitetura global desta estrutura, revelando propriedades que desafiam a intuição e demonstram que mesmo o incomputável possui organização e beleza matemática profundas.
Os graus de Turing formam uma ordem parcial (D, ≤) onde D é o conjunto de todos os graus e ≤ representa a redutibilidade. Esta estrutura possui um elemento mínimo único, o grau 0 dos conjuntos computáveis, mas surpreendentemente não possui elemento máximo — sempre existem graus ainda maiores. Entre quaisquer dois graus comparáveis existe uma infinidade incontável de graus intermediários, criando uma densidade vertiginosa.
Podemos combinar graus através de operações naturais. O join (união) de graus a e b, denotado a ∪ b, é o grau do conjunto A ⊕ B = {2n : n ∈ A} ∪ {2n+1 : n ∈ B}. Este grau contém toda informação de ambos os graus originais. O meet (interseção) nem sempre existe — dois graus podem não ter ínfimo comum além de 0, revelando a complexidade estrutural.
Um grau é mínimo se é não-computável mas não possui graus estritamente entre ele e 0. A existência de graus mínimos, provada por Spector em 1956, foi uma das primeiras grandes surpresas na teoria. Estes graus são incomputáveis mas "indivisíveis" — não podem ser decompostos em partes mais simples não-triviais. Sua construção requer técnicas sofisticadas de forcing.
Entre quaisquer dois graus comparáveis a < b, existe um grau c com a < c < b. Esta propriedade de densidade, provada independentemente por Sacks e outros, mostra que não existem "saltos" na ordem dos graus — a transição de um grau para outro maior é sempre infinitamente gradual. A demonstração usa o método de forcing com condições perfeitas.
Para qualquer grau a, o cone acima de a consiste em todos os graus b ≥ a. Estes cones têm propriedades uniformes notáveis — todos são isomorfos como ordens parciais! Este resultado surpreendente mostra que a estrutura "local" dos graus se repete em todos os níveis. Filtros (cones superiores fechados para baixo) capturam noções de complexidade uniforme.
Entre 0 e 0' existem infinitos graus, formando o domínio dos graus recursivamente enumeráveis. Estes graus intermediários têm estrutura incrivelmente rica. Alguns são baixos (low), outros altos (high), e muitos são verdadeiramente intermediários. A classificação destes graus por suas propriedades de salto revela camadas de complexidade.
Quais propriedades dos graus podem ser definidas usando apenas a relação de ordem? Surpreendentemente, muitas propriedades naturais são definíveis. O salto, por exemplo, é definível na estrutura dos graus por uma fórmula de primeira ordem. Isto mostra que a estrutura dos graus codifica informação computacional profunda em sua geometria.
A estrutura dos graus tem poucos automorfismos — transformações que preservam a ordem. De fato, conjectura-se que o único automorfismo é a identidade, significando que a estrutura é completamente rígida. Esta rigidez contrasta com a aparente flexibilidade e riqueza, sugerindo que a complexidade está "congelada" em padrões únicos.
Muitas propriedades desejáveis são imposíveis na estrutura dos graus. Não existe um conjunto de graus r.e. que seja denso e fechado para cima. Não podemos ter uma antichain maximal computável. Estes teoremas de impossibilidade delineiam os limites do que pode existir neste universo matemático.
A estrutura dos graus tem conexões surpreendentes com outras áreas da matemática. Técnicas de forcing da teoria dos conjuntos são essenciais para muitas construções. Métodos de teoria dos modelos iluminam questões de definibilidade. Ideias de topologia e análise aparecem no estudo de graus contínuos. Estas conexões enriquecem nossa compreensão.
A estrutura dos graus de Turing é um dos objetos mais fascinantes e misteriosos da matemática. Como um fractal infinito-dimensional de complexidade, ela revela padrões em todas as escalas enquanto mantém surpresas em cada exploração. Propriedades aparentemente contraditórias coexistem: densidade e minimalidade, riqueza e rigidez, regularidade e patologia. Esta estrutura não é apenas um objeto de estudo abstrato — ela mapeia os limites fundamentais do conhecimento computável, organizando o incomputável em uma hierarquia de precisão matemática surpreendente. No próximo capítulo, focaremos na região mais estudada desta estrutura: os graus recursivamente enumeráveis.
Entre o território familiar dos problemas computáveis e o vasto oceano do totalmente incomputável, existe uma região fronteiriça fascinante: os graus recursivamente enumeráveis. Estes são os graus de problemas que podem ser listados por um programa de computador, mesmo que não possamos decidir completamente sobre eles. Como exploradores mapeando uma terra entre dois mundos, os matemáticos descobriram que esta região intermediária possui geografia própria surpreendentemente rica, com montanhas, vales e estruturas que desafiam a intuição. Este capítulo mergulha neste reino especial, revelando como mesmo entre o computável e o incomputável existe complexidade infinita.
Um conjunto é recursivamente enumerável (r.e.) se pode ser listado por uma máquina de Turing — existe um programa que eventualmente imprime cada elemento do conjunto, embora possa nunca parar de imprimir. Alternativamente, é o domínio de uma função parcial computável. Esta caracterização dupla — como imagem ou domínio — revela a natureza semi-decidível destes conjuntos: podemos confirmar pertinência mas não necessariamente não-pertinência.
Os conjuntos r.e. formam um reticulado sob união e interseção efetivas. Se A e B são r.e., então A ∪ B e A ∩ B também são, com índices computáveis a partir dos índices de A e B. Este reticulado tem propriedades algébricas ricas mas patológicas — não é distributivo, não é modular, e tem cadeias e anticadeias de todos os tamanhos possíveis.
Nem todo grau contém um conjunto r.e. Os graus que contêm conjuntos r.e. formam um subconjunto próprio de todos os graus, com estrutura própria distinta. Surpreendentemente, enquanto todos os graus formam uma ordem parcial densa, os graus r.e. não são densos para cima — existem graus r.e. a < b sem grau r.e. estritamente entre eles.
Um dos resultados mais célebres da teoria é a solução independente de Friedberg e Muchnik ao problema de Post: existem graus r.e. intermediários entre 0 e 0'. A construção usa o método de prioridade finita, uma técnica revolucionária que balanceia requisitos conflitantes infinitos. Este teorema abriu as portas para o estudo detalhado da estrutura dos graus r.e.
Todo grau r.e. não-computável pode ser "dividido" em dois graus r.e. menores incomparáveis. Este teorema de splitting de Sacks mostra que os graus r.e. são densos para baixo e não têm átomos. A técnica de splitting se tornou ferramenta fundamental para explorar a estrutura fina dos graus r.e., revelando sua divisibilidade infinita.
Os graus r.e. são classificados por seu comportamento de salto. Graus baixos (low) satisfazem a' = 0'', sendo próximos ao computável em complexidade de salto. Graus altos (high) têm a' = 0''', possuindo máxima complexidade de salto possível para graus r.e. A região intermediária contém graus com comportamentos exóticos de salto.
Alguns graus r.e. têm propriedade de promptidão — seus conjuntos podem ser enumerados de forma que elementos aparecem "rapidamente" após certas condições serem satisfeitas. Graus promptly simples formam uma classe importante com propriedades estruturais especiais, incluindo não ter graus r.e. mínimos abaixo deles.
A teoria de primeira ordem dos graus r.e. é indecidível — não existe algoritmo para determinar verdade de afirmações sobre a estrutura. Mais ainda, a teoria é de complexidade 1-1 equivalente à teoria de segunda ordem da aritmética, uma das teorias mais complexas conhecidas. Isto mostra que a estrutura dos graus r.e. codifica complexidade lógica máxima.
A questão de automorfismos nos graus r.e. permanece um dos grandes problemas abertos. Conjectura-se que todo automorfismo é a identidade, mas isto permanece não provado. Resultados parciais mostram que certos graus especiais são fixados por todos os automorfismos, sugerindo rigidez, mas a questão completa resiste a décadas de ataques.
Graus r.e. aparecem naturalmente em muitos contextos. Problemas de verificação de software frequentemente são r.e. — podemos enumerar programas corretos mas não incorretos. Em lógica matemática, teoremas demonstráveis formam conjuntos r.e. Em teoria dos números, muitos conjuntos diofantinos são r.e. Estas conexões mostram a ubiquidade do conceito.
Os graus recursivamente enumeráveis ocupam um lugar especial na teoria da computabilidade — suficientemente simples para admitir construções explícitas, mas complexos o bastante para exibir fenômenos surpreendentes. Como a fronteira entre o conhecido e o desconhecido, eles capturam a essência da semi-decidibilidade que permeia a matemática e a computação. Sua estrutura, revelada através de décadas de pesquisa intensa, mostra que mesmo nesta região aparentemente simples existe complexidade rivalizado com qualquer estrutura matemática conhecida. No próximo capítulo, exploraremos um dos teoremas mais importantes desta área: o Teorema de Friedberg-Muchnik e o método revolucionário usado em sua demonstração.
Em 1944, Emil Post propôs um dos problemas mais desafiadores da jovem teoria da computabilidade: existem graus de insolubilidade intermediários entre os problemas computáveis e o problema da parada? Por mais de uma década, este problema resistiu aos melhores esforços dos lógicos. Então, em 1956-57, dois jovens matemáticos — Richard Friedberg nos Estados Unidos e Albert Muchnik na União Soviética — independentemente descobriram a resposta e, mais importante, inventaram uma técnica revolucionária para prová-la. O método de prioridade finita que desenvolveram não apenas resolveu o problema de Post, mas transformou completamente o campo, tornando-se a ferramenta fundamental para construir objetos com propriedades computacionais prescritas.
Post perguntou se a estrutura dos graus r.e. era trivial — apenas 0 e 0' — ou rica, contendo graus intermediários. A questão tocava no coração da teoria: a incomputabilidade admite gradações sutis ou é um fenômeno tudo-ou-nada? Post tentou construir graus intermediários mas encontrou obstáculos fundamentais. Requisitos aparentemente simples entravam em conflito infinito, cada tentativa de satisfazer um prejudicando outros.
A genialidade de Friedberg e Muchnik foi perceber que requisitos conflitantes podiam ser organizados por prioridade. Requisitos mais importantes recebem prioridade maior e podem "ferir" requisitos de menor prioridade. Crucialmente, cada requisito é ferido apenas finitamente muitas vezes, eventualmente se estabilizando em estado satisfeito. Esta organização hierárquica permite balancear infinitos requisitos simultaneamente.
Para construir um grau intermediário, precisamos garantir que nosso conjunto A não é computável (requisitos P) e não computa o problema da parada K (requisitos N). Formalmente: Pₑ garante A ≠ Φₑ (A difere da e-ésima função computável), e Nₑ garante K ≠ Φₑᴬ (K não é computável usando A como oráculo). Infinitos requisitos devem ser satisfeitos simultaneamente.
O conjunto A é construído gradualmente, estágio por estágio. Em cada estágio s, examinamos os requisitos em ordem de prioridade. Cada requisito tem oportunidade de agir se necessário para sua satisfação. Requisito Pₑ pode adicionar elemento a A para diferir de Φₑ. Requisito Nₑ pode proibir elementos de entrar em A para evitar computar K. A construção é efetiva — cada estágio é computável.
Para satisfazer Pₑ (garantir A ≠ Φₑ), esperamos até encontrar x tal que Φₑ,ₛ(x) converge. Então escolhemos preservar ou mudar A(x) para diferir de Φₑ(x). Uma vez que agimos, Pₑ está permanentemente satisfeito — encontramos testemunha da diferença. A estratégia é simples mas efetiva, garantindo A não é computável.
Requisitos N são mais sutis. Para garantir K ≠ Φₑᴬ, usamos estratégia de preservação. Escolhemos testemunha x e esperamos ver se x entra em K. Se Φₑᴬ(x) converge para 0 mas x ∈ K, preservamos computação — mantemos A restrito para preservar Φₑᴬ(x) = 0 ≠ K(x). Esta estratégia de "restraint" é chave para controlar o poder computacional de A.
Conflitos surgem quando requisito P quer adicionar elemento que requisito N proíbe. A prioridade resolve: requisito de maior prioridade vence. Requisito ferido é "reiniciado" — esquece história e começa novamente com nova testemunha maior. Crucialmente, requisitos de alta prioridade eventualmente se estabilizam, ferindo requisitos menores apenas finitamente.
A verificação procede por indução. Assumimos que requisitos de prioridade maior que Rₙ eventualmente param de agir. Após este estágio, Rₙ não é mais ferido. Se Rₙ = Pₑ, eventualmente encontra testemunha permanente. Se Rₙ = Nₑ, ou encontra discordância ou restraint permanente não interfere com outros requisitos (pois usa testemunha grande). Logo, Rₙ é satisfeito e eventualmente para de agir.
O método de prioridade finita revolucionou a teoria da computabilidade. Tornou-se a ferramenta padrão para construções em graus r.e., generalizada para prioridade infinita, prioridade com árvore, e métodos ainda mais sofisticados. Praticamente toda construção não-trivial em graus r.e. usa alguma forma de argumento de prioridade.
O teorema de Friedberg-Muchnik fez mais que resolver um problema técnico — estabeleceu que a incomputabilidade admite gradações infinitamente sutis. Entre o computável e o problema da parada existe um universo rico de complexidade intermediária. O método de prioridade mostrou como organizar e resolver conflitos infinitos, uma metáfora poderosa para muitos problemas matemáticos e computacionais.
O teorema de Friedberg-Muchnik e o método de prioridade finita representam um dos grandes triunfos da lógica matemática do século XX. Ao mostrar como construir graus intermediários através de uma dança cuidadosamente coreografada de requisitos conflitantes, Friedberg e Muchnik não apenas resolveram o problema de Post, mas abriram um novo mundo de possibilidades construtivas. O método que inventaram tornou-se a linguagem na qual a teoria moderna dos graus é escrita, permitindo construções de complexidade e sutileza antes inimagináveis. No próximo capítulo, exploraremos o rico território que este método ajudou a revelar: o mundo dos graus abaixo de 0'.
O intervalo entre o computável e o problema da parada — os graus abaixo de 0' — é como uma metrópole matemática densamente povoada, com arranha-céus de complexidade, bairros de graus relacionados e uma infraestrutura intrincada conectando tudo. Este território aparentemente pequeno contém diversidade estrutural que rivaliza com qualquer área da matemática. Aqui vivem os graus baixos que se comportam quase como computáveis, os graus altos que concentram poder computacional máximo, e uma fauna exótica de graus com propriedades surpreendentes. Este capítulo explora esta região fundamental, revelando a complexidade escondida no que parece ser um intervalo simples.
Os graus abaixo de 0' formam um semi-reticulado superior com propriedades únicas. Todo grau aqui é o grau de algum conjunto r.e., estabelecendo correspondência perfeita entre graus ≤ 0' e graus r.e. Esta região é densa — entre quaisquer dois graus comparáveis existem infinitos outros. Porém, também contém fenômenos impossíveis em outras partes da hierarquia, como minimal pairs e graus com propriedades extremas de salto.
A classificação por comportamento de salto divide os graus abaixo de 0' em hierarquias. Graus low₁ têm a' = 0'', sendo minimamente complexos quanto ao salto. Graus high₁ têm a' = 0''', maximizando complexidade de salto. Entre estes extremos existe um espectro contínuo de comportamentos, com graus lowₙ e highₙ formando hierarquias infinitas que refinam nossa compreensão da região.
Lachlan e Yates descobriram que existem graus r.e. não-computáveis a e b cujo ínfimo é 0 — minimal pairs. Isto significa que a única informação computável a partir de ambos simultaneamente é a trivial. Este fenômeno surpreendente mostra que graus podem ser "ortogonais" em sentido informacional, cada um contendo informação que o outro não pode acessar nem parcialmente.
Graus contendo conjuntos promptly simples têm propriedade de velocidade — elementos entram "rapidamente" quando entram. Estes graus não podem ser cobertos por graus baixos e não têm graus r.e. mínimos abaixo. Formam uma classe robusta com propriedades definíveis, servindo como exemplo de como velocidade de enumeração afeta estrutura de graus.
Sacks provou que os graus r.e. são densos — entre quaisquer dois graus r.e. comparáveis existe outro r.e. A demonstração usa forcing com condições perfeitas, técnica importada da teoria dos conjuntos. Este resultado contrasta com a não-densidade para cima, mostrando assimetria fundamental na estrutura local dos graus r.e.
Graus d-r.e. (diferença de r.e.) e n-r.e. formam hierarquias dentro de [0, 0']. Um conjunto é d-r.e. se é diferença de dois r.e., capturando aproximações que podem mudar de opinião uma vez. A hierarquia de Ershov classifica conjuntos por número de mudanças permitidas, revelando estratificação fina baseada em complexidade de aproximação.
Muitas propriedades dos graus abaixo de 0' são definíveis na estrutura. Ser low, high, ou contíguo pode ser expresso por fórmulas de primeira ordem na linguagem de ordem parcial. Esta definibilidade sugere que a estrutura codifica informação computacional profunda em suas relações de ordem, um fenômeno notável de rigidez.
Certos padrões são impossíveis abaixo de 0'. Não existe antichain maximal r.e. — sempre podemos adicionar mais graus incomparáveis. Não existe sequência descendente infinita de graus r.e. Todo grau r.e. não-computável tem cone próprio denso. Estes teoremas delineiam os limites do possível nesta região.
O estudo dos graus abaixo de 0' tem aplicações surpreendentes. Graus baixos correspondem a problemas que não ajudam muito como oráculos. Graus altos concentram poder computacional útil para redução. Esta classificação ajuda entender quando problemas semi-decidíveis podem ser úteis como sub-rotinas em algoritmos.
Técnicas de forcing, importadas da teoria dos conjuntos, são essenciais para construções sofisticadas abaixo de 0'. Forcing com condições perfeitas permite construir graus com propriedades prescritas enquanto preserva requisitos. Esta técnica poderosa permite controle fino sobre propriedades locais e globais dos graus construídos.
Os graus abaixo de 0' formam um microcosmo da teoria da computabilidade, concentrando em um intervalo aparentemente pequeno toda a complexidade e riqueza da hierarquia completa. Como uma cidade vista de cima à noite, cada ponto de luz representa um grau com sua própria história e propriedades, conectados por uma rede intrincada de relações. O estudo desta região revelou fenômenos que desafiam a intuição — minimal pairs, hierarquias de salto, estratificações por velocidade — mostrando que mesmo no território entre o computável e o primeiro nível de incomputabilidade existe complexidade infinita esperando ser descoberta.
A teoria dos graus de Turing não vive isolada em torres de marfim matemáticas — ela ilumina questões fundamentais sobre a natureza da complexidade computacional. Como um microscópio que revela estruturas invisíveis a olho nu, os graus de Turing expõem distinções sutis entre problemas que parecem igualmente difíceis. De P versus NP até a hierarquia polinomial, de complexidade de Kolmogorov até aleatoriedade algorítmica, os conceitos e técnicas dos graus de Turing permeiam a ciência da computação teórica. Este capítulo explora estas conexões profundas, mostrando como o estudo do incomputável ilumina o computável.
O conceito de oráculo dos graus de Turing é fundamental para entender limitações de técnicas de demonstração. Baker, Gill e Solovay mostraram que P = NP relativizado a alguns oráculos e P ≠ NP para outros. Esta relativização implica que técnicas que "relativizam" — funcionam igualmente com oráculos — não podem resolver P vs NP. Os graus de Turing assim revelam barreiras fundamentais para progresso em complexidade.
Analogamente aos graus de Turing, podemos definir graus de redutibilidade em tempo polinomial. A ≤ₚ B se A é redutível a B em tempo polinomial. Esta noção captura complexidade prática, onde não apenas computabilidade mas eficiência importa. Graus polinomiais formam estrutura refinada dentro dos graus de Turing, distinguindo entre diferentes níveis de tratabilidade.
A complexidade de Kolmogorov K(x) — o tamanho do menor programa que gera x — é intimamente ligada aos graus de Turing. K é não-computável, com grau exatamente 0'. Strings aleatórias no sentido de Kolmogorov formam conjunto de grau 0'. Variações de complexidade (prefix-free, monotone) correspondem a diferentes noções de redutibilidade, criando ponte entre informação e computabilidade.
Sequências algoritmicamente aleatórias — aquelas que passam todos os testes computáveis de aleatoriedade — formam classe de medida 1 com propriedades de grau específicas. Sequências Martin-Löf aleatórias não computam 0' e formam cone de graus. Diferentes noções de aleatoriedade (Martin-Löf, Schnorr, Kurtz) correspondem a diferentes classes de graus, revelando estratificação fina da aleatoriedade.
A hierarquia polinomial PH é análoga à hierarquia aritmética, substituindo computabilidade por tempo polinomial. Σₚⁿ e Πₚⁿ correspondem a n alternâncias de quantificadores polinomiais. Se PH colapsa em algum nível, colapsa completamente — fenômeno sem análogo na hierarquia aritmética. Oráculos dos graus de Turing podem fazer PH colapsar ou ser infinita, mostrando sensibilidade a informação externa.
Lower bounds para circuitos booleanos conectam-se a graus via complexidade de Kolmogorov. Strings de alta complexidade de Kolmogorov requerem circuitos grandes. Técnicas de diagonalização dos graus inspiram métodos para lower bounds. A barreira de naturalização de Razborov-Rudich tem interpretação em termos de graus e aleatoriedade.
Em complexidade parametrizada, estudamos problemas com parâmetro k além do tamanho n. A hierarquia W[1], W[2], ... é análoga aos graus, com redutibilidade fpt (fixed-parameter tractable). Técnicas de construção de graus inspiram construções em complexidade parametrizada. A estrutura dos W-graus espelha aspectos dos graus de Turing.
Protocolos de comunicação com acesso a oráculos conectam complexidade de comunicação a graus. Lower bounds em comunicação frequentemente usam técnicas de diagonalização similares às dos graus. Hierarquias de protocolos espelham hierarquias de graus. A complexidade de comunicação de problemas em diferentes graus revela estrutura computacional.
Computação quântica com oráculos clássicos cria nova dimensão de complexidade. BQP com diferentes oráculos tem comportamentos diversos. Algoritmos quânticos para problemas em diferentes graus revelam poder quântico. Separações quânticas frequentemente usam propriedades de graus. A estrutura BQP vs PH depende crucialmente de oráculos.
Embora abstrata, a conexão entre graus e complexidade tem implicações práticas. Entender barreiras de relativização guia pesquisa em P vs NP. Aleatoriedade algorítmica fundamenta criptografia. Complexidade de Kolmogorov aparece em compressão de dados. Graus parametrizados informam design de algoritmos. A teoria dos graus fornece framework conceitual para entender limites práticos.
A teoria dos graus de Turing e a teoria da complexidade computacional são como duas faces de uma mesma moeda — uma estudando o incomputável, outra o intratável, mas ambas revelando estruturas fundamentais da computação. As técnicas, conceitos e insights fluem bidirecionalmente, enriquecendo ambos os campos. Como vimos, desde barreiras de relativização até hierarquias de complexidade, desde aleatoriedade até computação quântica, os graus de Turing fornecem lente poderosa para examinar questões centrais da ciência da computação. No capítulo final, veremos como estes conceitos abstratos se manifestam no mundo digital que nos rodeia.
Os graus de Turing podem parecer abstrações matemáticas distantes, mas suas impressões digitais estão por toda parte no mundo tecnológico moderno. Cada vez que um compilador otimiza código, um antivírus procura malware, ou uma IA toma decisões, as limitações fundamentais descobertas por Turing operam silenciosamente nos bastidores. Como as leis da física que governam o mundo material, os graus de Turing estabelecem as leis do mundo computacional, determinando o que é possível, o que é prático, e o que permanecerá para sempre além de nosso alcance algorítmico. Este capítulo final explora como estes conceitos teóricos profundos moldam a tecnologia que usamos diariamente.
Toda empresa de software gostaria de garantir que seus programas estão livres de bugs. Mas o problema da parada nos diz que verificação completa automática é impossível. Na prática, verificadores trabalham com aproximações e casos especiais decidíveis. Ferramentas como model checkers exploram espaços finitos de estados, analisadores estáticos detectam padrões específicos de erros, e theorem provers requerem intervenção humana. Os graus de Turing explicam por que certas propriedades são verificáveis enquanto outras permanecerão sempre elusivas.
Detectar malware é fundamentalmente equivalente ao problema da parada — determinar se código arbitrário tem comportamento malicioso é indecidível. Antivírus modernos usam heurísticas, assinaturas e análise comportamental, navegando entre falsos positivos e negativos. Sandbox e virtualização isolam código suspeito. A teoria dos graus explica por que segurança perfeita é impossível e guia desenvolvimento de defesas práticas em camadas.
Sistemas de IA enfrentam barreiras fundamentais relacionadas aos graus de Turing. Aprendizado PAC (Probably Approximately Correct) tem limites computacionais. Redes neurais podem aproximar funções arbitrárias mas não podem computar funções não-computáveis. AGI (Artificial General Intelligence) enfrentaria os mesmos limites de incomputabilidade que inteligência humana algorítmica. Os graus estabelecem fronteiras teóricas do que IA pode alcançar.
Compiladores gostariam de fazer otimizações perfeitas, mas muitas propriedades de programas são indecidíveis. Determinar se código é alcançável, se loops terminam, ou se variáveis são usadas relaciona-se ao problema da parada. Compiladores usam análises conservativas — se não podem provar que otimização é segura, não a fazem. A teoria dos graus explica trade-offs entre otimização agressiva e correção garantida.
Linguagens de consulta como SQL são cuidadosamente desenhadas para serem decidíveis. SQL puro (sem recursão) sempre termina. Mas adicionar features como CTEs recursivas ou procedimentos armazenados pode tornar terminação indecidível. Otimizadores de consulta enfrentam problemas NP-completos, usando heurísticas. A teoria dos graus ilumina por que certas extensões de SQL são perigosas e como otimizadores devem aproximar.
Contratos inteligentes em blockchains como Ethereum enfrentam o problema da parada — gas limits existem porque determinar se contrato termina é indecidível. Verificação formal de contratos é limitada pelos graus de Turing. Bugs em contratos podem ser indecidíveis de detectar. A imutabilidade de blockchains amplifica importância de entender estes limites teóricos antes de deployment.
Compressão ótima relaciona-se à complexidade de Kolmogorov, que tem grau 0'. Não podemos computar a melhor compressão possível. Algoritmos práticos (ZIP, JPEG, H.264) usam heurísticas e modelos específicos. Machine learning para compressão aproxima complexidade de Kolmogorov. Limites teóricos dos graus explicam por que compressão perfeita universal é impossível.
Consenso em sistemas distribuídos tem conexões profundas com graus de Turing. Detectar propriedades globais de sistemas assíncronos pode ser indecidível. Algoritmos de consenso (Paxos, Raft) trabalham com modelos restritos. Detecção de deadlock distribuído é complexa. A teoria dos graus ilumina limites fundamentais de coordenação distribuída e necessidade de timeouts e aproximações.
Problemas em bioinformática frequentemente têm alta complexidade computacional. Alinhamento de sequências, predição de estrutura de proteínas, e análise de redes metabólicas envolvem problemas NP-difíceis ou indecidíveis. Heurísticas e aproximações são essenciais. A teoria dos graus explica por que certos problemas biológicos permanecerão computacionalmente intratáveis, guiando desenvolvimento de métodos práticos.
À medida que a computação permeia cada aspecto de nossas vidas, entender os limites fundamentais estabelecidos pelos graus de Turing torna-se cada vez mais importante. Computação quântica não transcende estes limites. IA não resolverá problemas indecidíveis. Novos paradigmas computacionais ainda enfrentarão as barreiras descobertas por Turing. Mas conhecer estes limites nos permite trabalhar inteligentemente dentro deles, desenvolvendo aproximações práticas, identificando casos tratáveis, e focando esforços onde progresso é possível.
Os graus de Turing são mais que curiosidades matemáticas — são os princípios fundamentais que governam o que é possível no mundo digital. Como as leis da termodinâmica limitam máquinas físicas, os graus de Turing limitam máquinas computacionais. Mas assim como engenheiros criam maravilhas trabalhando dentro das leis físicas, cientistas da computação e programadores criam tecnologias incríveis navegando dentro dos limites da computabilidade. Entender estes limites não é desencorajador — é libertador, focando nossos esforços onde podemos fazer diferença real, desenvolvendo soluções práticas para problemas reais, e apreciando a profunda beleza matemática que fundamenta nosso mundo digital. A jornada de Turing continua, não na busca por transcender estes limites, mas em explorar o vasto e rico território que existe dentro deles.
Este volume sobre Graus de Turing foi construído sobre décadas de pesquisa em teoria da computabilidade, lógica matemática e ciência da computação teórica. As referências abrangem desde os trabalhos pioneiros de Turing, Post e Kleene até desenvolvimentos contemporâneos em complexidade computacional e aplicações práticas. Esta bibliografia oferece recursos para aprofundamento em cada aspecto dos graus de Turing, desde sua teoria fundamental até suas conexões com outras áreas da matemática e computação.
AMBOS-SPIES, Klaus; FEJER, Peter A. Degrees of Unsolvability. In: Handbook of Computability Theory. Amsterdam: Elsevier, 1999.
COOPER, S. Barry. Computability Theory. Boca Raton: Chapman and Hall/CRC, 2004.
DAVIS, Martin. Computability and Unsolvability. New York: Dover Publications, 1982.
DOWNEY, Rodney G.; HIRSCHFELDT, Denis R. Algorithmic Randomness and Complexity. New York: Springer, 2010.
EPSTEIN, Richard L.; CARNIELLI, Walter A. Computability: Computable Functions, Logic, and the Foundations of Mathematics. 3rd ed. Socorro: Advanced Reasoning Forum, 2008.
FRIEDBERG, Richard M. Two Recursively Enumerable Sets of Incomparable Degrees of Unsolvability. Proceedings of the National Academy of Sciences, v. 43, p. 236-238, 1957.
GÖDEL, Kurt. Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme I. Monatshefte für Mathematik, v. 38, p. 173-198, 1931.
JOCKUSCH, Carl G. Jr.; SOARE, Robert I. Degrees of Members of Π₁⁰ Classes. Pacific Journal of Mathematics, v. 40, p. 605-616, 1972.
KLEENE, Stephen Cole. Introduction to Metamathematics. Amsterdam: North-Holland, 1952.
KLEENE, Stephen Cole; POST, Emil L. The Upper Semi-lattice of Degrees of Recursive Unsolvability. Annals of Mathematics, v. 59, p. 379-407, 1954.
LACHLAN, Alistair H. Lower Bounds for Pairs of Recursively Enumerable Degrees. Proceedings of the London Mathematical Society, v. 16, p. 537-569, 1966.
LERMAN, Manuel. Degrees of Unsolvability: Local and Global Theory. Berlin: Springer-Verlag, 1983.
LI, Ming; VITÁNYI, Paul. An Introduction to Kolmogorov Complexity and Its Applications. 3rd ed. New York: Springer, 2008.
MARTIN, Donald A. Classes of Recursively Enumerable Sets and Degrees of Unsolvability. Zeitschrift für Mathematische Logik, v. 12, p. 295-310, 1966.
MILLER, Webb; MARTIN, Donald A. The Degrees of Hyperimmune Sets. Zeitschrift für Mathematische Logik, v. 14, p. 159-166, 1968.
MUCHNIK, Albert A. On the Unsolvability of the Problem of Reducibility in the Theory of Algorithms. Doklady Akademii Nauk SSSR, v. 108, p. 194-197, 1956. [Em russo]
NIES, André. Computability and Randomness. Oxford: Oxford University Press, 2009.
ODIFREDDI, Piergiorgio. Classical Recursion Theory. Amsterdam: North-Holland, 1989. 2 v.
POST, Emil L. Recursively Enumerable Sets of Positive Integers and Their Decision Problems. Bulletin of the American Mathematical Society, v. 50, p. 284-316, 1944.
ROBINSON, Raphael M. Recursion and Double Recursion. Bulletin of the American Mathematical Society, v. 54, p. 987-993, 1948.
ROGERS, Hartley Jr. Theory of Recursive Functions and Effective Computability. Cambridge: MIT Press, 1987.
SACKS, Gerald E. Degrees of Unsolvability. Princeton: Princeton University Press, 1963.
SACKS, Gerald E. Higher Recursion Theory. Berlin: Springer-Verlag, 1990.
SHOENFIELD, Joseph R. On Degrees of Unsolvability. Annals of Mathematics, v. 69, p. 644-653, 1959.
SHOENFIELD, Joseph R. Degrees of Unsolvability. Amsterdam: North-Holland, 1971.
SIMPSON, Stephen G. Subsystems of Second Order Arithmetic. 2nd ed. Cambridge: Cambridge University Press, 2009.
SLAMAN, Theodore A.; WOODIN, W. Hugh. Definability in the Turing Degrees. Illinois Journal of Mathematics, v. 30, p. 320-334, 1986.
SOARE, Robert I. Recursively Enumerable Sets and Degrees. Berlin: Springer-Verlag, 1987.
SOARE, Robert I. Turing Computability: Theory and Applications. Berlin: Springer, 2016.
SPECTOR, Clifford. On Degrees of Recursive Unsolvability. Annals of Mathematics, v. 64, p. 581-592, 1956.
TURING, Alan M. On Computable Numbers, with an Application to the Entscheidungsproblem. Proceedings of the London Mathematical Society, v. 42, p. 230-265, 1936.
TURING, Alan M. Systems of Logic Based on Ordinals. Proceedings of the London Mathematical Society, v. 45, p. 161-228, 1939.
YU, Liang. A Study of Singular Computably Enumerable Degrees. Singapore: World Scientific, 2006.
CARNIELLI, Walter; EPSTEIN, Richard L. Computabilidade: Funções Computáveis, Lógica e os Fundamentos da Matemática. 2ª ed. São Paulo: Editora UNESP, 2006.
COSTA, Newton C. A. da; DORIA, Francisco A. Foundations of Science: The Incompleteness Phenomenon. São Paulo: EDUSP, 1995.
FEITOSA, Hércules de Araújo; PAULOVICH, Leonardo. Um Prelúdio à Lógica. São Paulo: Editora UNESP, 2005.
FINGER, Marcelo; SILVA, Flávio S. C. da; MELO, Ana Cristina V. de. Lógica para Computação. 2ª ed. São Paulo: Thomson Learning, 2006.
MENDELSON, Elliott. Introdução à Lógica Matemática. Tradução da 5ª ed. São Paulo: Cengage Learning, 2015.
MORTARI, Cezar A. Introdução à Lógica. 2ª ed. São Paulo: Editora UNESP, 2016.
SILVA, Flávio Soares Corrêa da; MELO, Ana Cristina Vieira de. Modelos Clássicos de Computação. São Paulo: Thomson Learning, 2007.
TEIXEIRA, João de Fernandes. Mentes e Máquinas: Uma Introdução à Ciência Cognitiva. Porto Alegre: Artes Médicas, 1998.