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

Aquí presento un resumen técnico detallado del artículo "An order-reversing embedding of Turing degrees into Arthur–Nimue–Merlin degrees" de Jean Abou Samra y David Alexander Madore.

1. Contexto y Problema

El artículo se sitúa en la intersección de la teoría de la computabilidad clásica, la teoría de la realizabilidad y la teoría de topos. El objeto de estudio son los grados de Arthur-Nimue-Merlin (ANM), una generalización de los grados de Turing introducida por Kihara (2023). Estos grados describen el conjunto parcialmente ordenado de las topologías de Lawvere-Tierney en el topos efectivo (equivalentemente, los subtopos del topos efectivo).

El Problema:
Los grados ANM modelan la computación con oráculos que incorporan dos formas de no-determinismo:

1. No-determinismo "demoníaco" (Merlin): Un agente adversario que elige el valor de salida dentro de un conjunto posible.
2. No-determinismo "angelical" (Nimue): Un agente benevolente que elige el conjunto de posibles salidas para ayudar al computador.

La jerarquía de grados se divide en niveles:

• T0: Grados de Turing estándar (funciones totales $N \to N$).
• T1: Funciones parciales ($N \rightharpoonup N$).
• T2: Funciones parciales no deterministas ($N \rightharpoonup \mathcal{P}(N)$).
• T3: Funciones totales con doble no-determinismo ($N \to \mathcal{P}(\mathcal{P}(N))$).

El problema central que abordan los autores es entender la relación de orden entre los grados de Turing clásicos (T0) y estos grados generalizados (específicamente T3). ¿Cómo se incrustan los grados de Turing en este nuevo universo? ¿Existe una relación de orden inversa o directa? Además, buscan caracterizar la estructura de los "grados básicos" T3 (constantes) y su interacción con los grados T0.

2. Metodología

Los autores utilizan una combinación de teoría de juegos, teoría de la computabilidad y teoría de topos:

• Juegos de Reducción (Arthur-Nimue-Merlin): La noción de reducibilidad se define mediante un juego de tres jugadores. Arthur (el computador, con estrategias computables) y Nimue (el aliado) juegan contra Merlin (el adversario). Arthur gana si puede determinar un valor correcto basándose en las respuestas de Merlin, con la ayuda de Nimue para elegir los conjuntos de respuestas.
• Problemas de Promesa (Promise Problems): Se introducen oráculos de "decodificación" ($d_{P,Q}$) y "codificación" ($c_{P,Q}$) asociados a problemas de promesa $(P, Q)$, donde $P$ y $Q$ son conjuntos disjuntos e inhabitados.
  • $d_{P,Q}$: Dado un elemento en $P \cup Q$, decide si está en $P$ o en $Q$.
  • $c_{P,Q}$: Responde preguntas de sí/no, codificando la respuesta en un elemento de $P$ (para 0) o $Q$ (para 1).
• Construcción de Grados Co-Turing: Definen grados específicos $\tilde{c}_A$ (grados co-Turing) asociados a un conjunto $A \subseteq \mathbb{N}$, basados en la codificación de la información sobre la computabilidad relativa a $A$.
• Reformulación Topos-teórica: En la sección 7, reinterpretan las construcciones en términos de topologías de Lawvere-Tierney y sheafification (sheafificación) en el topos efectivo, conectando los grados ANM con la lógica interna del topos.

3. Contribuciones Clave y Resultados Principales

A. Inmersión Inversa de Orden (Teorema 5.8)

El resultado principal del artículo es la construcción de una inmersión de orden inverso de los grados de Turing en los grados ANM (específicamente en los grados básicos T3).

• Definición: Para cada grado de Turing $a = [A]_{T0}$, se define un grado "co-Turing" $\text{coT}(a) = \tilde{c}_A$.
• Resultado: La aplicación $\text{coT}: \mathcal{D}_{T0}^{op} \to \mathcal{D}_{T3}$ es una inmersión de orden. Es decir:
  $$a \leq b \iff \text{coT}(a) \geq \text{coT}(b)$$
  Esto significa que si un grado de Turing es "más difícil" que otro, su grado co-Turing correspondiente es "más fácil" (o menor en la jerarquía de grados ANM).

B. Incomparabilidad entre T0 y Co-Turing (Sección 6)

Los autores demuestran que, excepto en el caso trivial del grado computable (0), los grados de Turing y los grados co-Turing son incomparables.

• Si $a > 0$ y $b > 0$ son grados de Turing, entonces $\text{coT}(a) \not\leq b$ y $\text{coT}(a) \not\geq b$.
• Esto implica que los grados co-Turing no proporcionan "omnisciencia" (grado $\omega$) ni permiten computar funciones deterministas no computables, a menos que el grado original sea 0.

C. Caracterización Técnica (Teorema 4.17)

Un resultado técnico crucial que sustenta la demostración principal es la caracterización de cuándo un grado de codificación es "omnisciente" ($\omega$).

• Se demuestra que $c_{P,Q} = \omega$ si y solo si el problema de promesa $(P \times Q, Q \times P)$ es decidible.
• Esto conecta la capacidad de "codificar" información arbitraria con la decidibilidad de un problema de paridad de pares, resolviendo una paradoja planteada en la introducción del artículo (el acertijo de Merlin).

D. Estructura de Retículo y Operaciones

El artículo analiza la estructura de retículo de los grados:

• Los grados T1, T2 y T3 forman retículos distributivos (T3 es un álgebra de Heyting).
• Se estudian los productos (mínimos) y sumas (máximos) en estos niveles.
• Se prueba que no existen pares mínimos en T1 (dos grados T0 no nulos no tienen un mínimo en T1 que sea 0), lo cual es fundamental para probar la incomparabilidad mencionada arriba.

E. Interpretación Topos-teórica

En la sección 7, se muestra que la construcción de $\text{coT}(a)$ corresponde a una operación natural en la teoría de topos:

• Dada una topología de Lawvere-Tierney $j$ (correspondiente a un grado), $\text{coT}(j)$ es la topología más pequeña que hace densa la inclusión de la sheafificación de 2 bajo $j$ dentro de la sheafificación de 2 bajo la topología de doble negación ($\neg\neg$).
• Esto proporciona una justificación sintética y categórica para la inversión de orden observada.

4. Significado e Impacto

1. Nueva Perspectiva sobre la Computabilidad: El trabajo revela una dualidad profunda en la estructura de la computabilidad. La introducción de no-determinismo "angelical" (Nimue) permite invertir el orden de los grados de Turing, sugiriendo que la "dificultad" de un problema en un contexto clásico puede transformarse en "facilidad" en un contexto de realizabilidad con ayuda angelical.
2. Conexión con Topos Efectivo: Al vincular explícitamente los grados ANM con las topologías de Lawvere-Tierney, el artículo proporciona una herramienta concreta para estudiar la estructura de los subtopos del topos efectivo, un área que a menudo se considera abstracta y difícil de manejar.
3. Resolución de Conjeturas: Responde a preguntas abiertas sobre la existencia de grados básicos T3 "interesantes" (más allá de los conocidos) y clarifica la relación entre los grados de Turing y los grados de omnisciencia ($\omega$).
4. Herramientas para Futuras Investigaciones: La introducción de los grados co-Turing y la técnica de reducción de problemas de promesa ofrecen nuevas herramientas para analizar la jerarquía de grados en modelos de computación no clásica y en la teoría de la realizabilidad.

En resumen, el artículo establece que los grados de Turing, vistos desde la perspectiva de los grados generalizados de Arthur-Nimue-Merlin, se incrustan de manera inversa, creando una clase de "grados co-Turing" que son estructuralmente distintos e incomparables con los grados de Turing originales, excepto en el caso trivial. Esto enriquece significativamente nuestra comprensión de la lógica y la computabilidad en entornos constructivos.