An order-reversing embedding of Turing degrees into Arthur-Nimue-Merlin degrees

1. Contexto e Problema

O artigo situa-se no campo da teoria da computabilidade e da teoria das categorias (topos), especificamente na generalização dos graus de Turing. Os autores investigam os graus Arthur–Nimue–Merlin (ANM), uma estrutura introduzida por Kihara que descreve o conjunto parcialmente ordenado das topologias de Lawvere–Tierney no topos efetivo (equivalentemente, os subtopos do topos efetivo).

O Problema Central:
Os graus ANM generalizam os graus de Turing clássicos (denominados aqui $T_0$) ao introduzir dois tipos de não-determinismo em consultas a oráculos:

1. Não-determinismo "demoníaco" (Merlin): O adversário escolhe um valor dentro de um conjunto fornecido, tentando dificultar o cálculo.
2. Não-determinismo "angelical" (Nimue): Um aliado escolhe o melhor conjunto possível dentro de uma estrutura fornecida, ajudando o cálculo.

O objetivo do trabalho é entender a relação de ordem entre os graus de Turing clássicos e esses graus generalizados ($T_3$). Especificamente, os autores buscam determinar se é possível incorporar a estrutura dos graus de Turing dentro dos graus ANM e qual é a natureza dessa incorporação.

2. Metodologia

Os autores utilizam uma abordagem híbrida que combina:

• Teoria de Jogos: A definição fundamental dos graus ANM baseia-se em um jogo de três jogadores (Arthur, Nimue e Merlin) com informação imperfeita. Arthur (computável) e Nimue (aliada) tentam vencer Merlin (adversário) para calcular uma função.
• Teoria da Computabilidade Clássica: Uso de reduções de Turing, problemas de promessa (promise problems) e graus de Turing ($T_0$), parciais ($T_1$) e não-determinísticos ($T_2$).
• Teoria de Topos e Realizabilidade: A interpretação dos graus ANM como topologias de Lawvere–Tierney no topos efetivo, permitindo uma reformulação dos resultados em termos de lógica interna e feixes (sheaves).

Estrutura da Prova:

1. Definição de Graus de Decodificação e Codificação: Para um problema de promessa $(P, Q)$, definem-se oráculos de decodificação ($d_{P,Q}$) e codificação ($c_{P,Q}$).
2. Construção de Graus Co-Turing: Para um conjunto $A \subseteq \mathbb{N}$, definem-se conjuntos $H^A_0$ e $H^A_1$ (programas que, com oráculo $A$, retornam 0 ou 1). O grau de codificação associado, $\tilde{c}_A$, é definido como o grau ANM de $c_{H^A_0, H^A_1}$.
3. Análise de Ordem: Eles provam que a aplicação $A \mapsto \tilde{c}_A$ inverte a ordem de Turing.
4. Comparação de Graus: Investigam a relação de comparabilidade entre um grau de Turing $b$ e um grau co-Turing $\text{coT}(a)$.

3. Principais Contribuições e Resultados

A. Embaralhamento Reverso de Ordem (Order-Reversing Embedding)

O resultado central é a construção de um mergulho (embedding) da ordem dos graus de Turing ($DT_0$) na ordem dos graus ANM ($DT_3$) que inverte a ordem.

• Definição: Para cada grau de Turing $d = [A]_{T_0}$, define-se o grau co-Turing $\text{coT}(d) = \tilde{c}_A$.
• Teorema: Para quaisquer graus de Turing $d_0, d_1$:
  $$d_0 \leq d_1 \iff \text{coT}(d_0) \geq \text{coT}(d_1)$$
  Isso significa que graus de Turing mais "fortes" (mais complexos) correspondem a graus co-Turing mais "fracos" (menos poderosos) no contexto ANM, e vice-versa. O mapa é um mergulho injetivo que preserva e reflete a ordem (no sentido reverso).

B. Incomparabilidade com Graus de Turing Não-Nulos

Os autores provam que, exceto para o grau zero (computável), os graus co-Turing e os graus de Turing são incomparáveis.

• Resultado: Se $a$ e $b$ são graus de Turing não-nulos, então $\text{coT}(a) \not\leq b$ e $\text{coT}(a) \not\geq b$.
• Implicação: Um grau co-Turing não-nulo não permite a computação de nenhuma função determinística $N \to N$ que não fosse já computável (ou seja, não contém graus de Turing não-triviais), e nenhum grau de Turing não-nulo é suficiente para calcular um grau co-Turing não-nulo.

C. Propriedades de "Meet" (Infimo) em Graus Generalizados

O artigo estabelece propriedades cruciais sobre o "meet" (infimo) em diferentes níveis de graus:

• Graus $T_1$: Provam que não existe um par mínimo de graus de Turing ($T_0$) dentro dos graus $T_1$. Ou seja, se $f \in DT_1$ e $g \in DT_0$ e $f \wedge_{T_1} g = 0$, então $f=0$ ou $g=0$.
• Graus $T_2$ e $T_3$: Demonstram que a estrutura de reticulado (lattice) dos graus $T_2$ e $T_3$ é distributiva (ao contrário dos $T_1$), e provam resultados análogos sobre a impossibilidade de certos meets serem zero sob condições específicas.

D. Reformulação Topos-Teórica

Na Seção 7, os autores reinterpretem a construção dos graus co-Turing em termos de topologias de Lawvere–Tierney.

• Eles mostram que a construção $\text{coT}(j)$ corresponde à topologia mais pequena que torna a inclusão do feixe de $2$ (para a topologia $j$) denso no feixe de $2$ para a topologia de negação dupla ($\neg\neg$).
• Isso conecta a computabilidade clássica com a lógica interna do topos efetivo, mostrando que a "inversão de ordem" é uma manifestação de propriedades de feixes e densidade.

4. Significado e Impacto

1. Novo Olhar sobre a Hierarquia de Computabilidade: O trabalho revela uma simetria profunda e inesperada: a complexidade de um oráculo de Turing, quando traduzida para o contexto de não-determinismo angelical e demoníaco, inverte-se. Quanto mais difícil é resolver um problema classicamente, mais "fácil" (ou menos informativo) ele se torna no contexto dos graus co-Turing.
2. Conexão entre Lógica Construtiva e Clássica: Ao conectar graus de Turing com topologias de Lawvere–Tierney, o artigo fornece uma ponte concreta entre a teoria da computabilidade clássica e a matemática construtiva dentro do topos efetivo.
3. Resolução de Questões Abertas: O artigo responde a perguntas sobre a estrutura dos graus ANM, especificamente sobre a existência de pares mínimos e a relação entre os níveis $T_0, T_1, T_2, T_3$.
4. Ferramentas para Pesquisa Futura: A introdução dos graus co-Turing e a análise de sua incomparabilidade com graus de Turing abrem novas linhas de investigação sobre a estrutura do reticulado dos graus ANM e suas aplicações em teoria da realizabilidade.

Em resumo, o paper demonstra que a generalização dos graus de Turing para incluir não-determinismo angelical e demoníaco não apenas expande o universo dos graus computacionais, mas também revela uma estrutura dual onde a ordem de complexidade clássica é invertida, criando uma nova classe de graus (co-Turing) que são fundamentalmente incomparáveis com os graus de Turing originais, exceto no caso trivial.