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

1. Problem Statement and Context

The paper addresses the structural relationship between classical Turing degrees ($T_0$) and the more general Arthur–Nimue–Merlin (ANM) degrees ($T_3$).

• Background: ANM degrees were introduced by Kihara to provide a concrete description of the partially ordered set of Lawvere–Tierney topologies on the effective topos. These degrees generalize Turing degrees by incorporating two forms of non-determinism into oracle queries:
  • Angelic non-determinism (Nimue): A benevolent agent who chooses the "best" set of options for the player.
  • Demonic non-determinism (Merlin): An adversarial agent who chooses the "worst" specific value from the options provided.
• The Hierarchy: The authors define a hierarchy of oracle types:
  • $T_0$: Standard Turing oracles ($N \to N$).
  • $T_1$: Partial functions ($N \rightharpoonup N$).
  • $T_2$: Partial multivalued functions ($N \rightharpoonup \mathcal{P}(N)$), introducing demonic non-determinism.
  • $T_3$: Functions to sets of sets ($N \to \mathcal{P}(\mathcal{P}(N))$), introducing both angelic and demonic non-determinism.
• The Core Question: How do standard Turing degrees sit within this generalized lattice? Specifically, can one embed the Turing degrees into the ANM degrees in a way that reveals a dual or "co-" structure? The authors investigate whether there exists a mapping from Turing degrees to ANM degrees that reverses the standard order ($d_1 \le d_2 \implies \text{coT}(d_1) \ge \text{coT}(d_2)$) and how these "co-Turing" degrees interact with standard Turing degrees.

2. Methodology

The authors employ a combination of game-theoretic reducibility, computability theory, and topos theory.

• The Reduction Game: The core mechanism is a three-player game involving:
  • Arthur: A computable player restricted to computable strategies.
  • Nimue: An angelic ally who chooses sets $G \in g(n)$.
  • Merlin: A demonic adversary who chooses values $v \in G$.
  • Winning Condition: Arthur and Nimue win if Arthur can declare a correct final value based on the initial challenge and Merlin's moves. Reducibility ($f \preceq g$) is defined by the existence of a winning strategy for Arthur+Nimue.
• Promise Problems and Coding/Decoding Oracles:
  • The authors introduce decoding oracles ($d_{P,Q}$) which solve the promise problem of distinguishing between two disjoint sets $P$ and $Q$.
  • They introduce coding oracles ($c_{P,Q}$) which encode a bit (0 or 1) as an element of $P$ or $Q$, respectively.
  • A key technical tool is the analysis of the promise problem $(P \times Q, Q \times P)$, which corresponds to asking a question and its negation simultaneously.
• Topos-Theoretic Reformulation: In Section 7, the authors reinterpret these constructions using Lawvere–Tierney topologies on the effective topos. They map oracles to topologies $J$ and utilize the concept of sheafification to define the "co-Turing" degree. Specifically, they relate the co-Turing degree to the smallest topology making the sheafification of the two-element set dense in the double-negation sheafification.

3. Key Contributions

1. Definition of Co-Turing Degrees:
   The authors define a mapping $\text{coT}: \mathcal{D}_{T_0} \to \mathcal{D}_{T_3}$ (from Turing degrees to $T_3$ degrees). For a Turing degree $a = [A]_{T_0}$, $\text{coT}(a)$ is the degree of the coding oracle $c_{H^A_0, H^A_1}$, where $H^A_i$ is the set of indices of programs that terminate with output $i$ given oracle $A$.

2. Order-Reversing Embedding:
   The primary result (Theorem 5.8) proves that the map $\text{coT}$ is an order-reversing embedding.
   $$[A]_{T_0} \le [B]_{T_0} \iff \text{coT}([A]_{T_0}) \ge \text{coT}([B]_{T_0})$$
   This establishes that the structure of Turing degrees is isomorphic to a "cone" in the ANM degrees, but with the order inverted.

3. Incomparability Result:
   The paper proves that for any non-zero Turing degree $a$ and any non-zero Turing degree $b$, the co-Turing degree $\text{coT}(a)$ is incomparable with $b$ within the $T_3$ lattice.
   $$\text{coT}(a) \not\le b \quad \text{and} \quad \text{coT}(a) \not\ge b \quad (\text{if } a, b > 0)$$
   This implies that co-Turing degrees do not grant Arthur any new power to compute deterministic functions beyond what is already computable, nor do they provide "omniscience" unless the original degree was trivial.

4. Lattice Structure Analysis:
   The authors analyze the meet and join operations across $T_1, T_2,$ and $T_3$ levels.

   • They prove that $T_1$ degrees form a lattice where the meet of two $T_0$ degrees is zero only if one of them is zero (Proposition 3.6).
   • They show that $T_2$ and $T_3$ degrees form distributive lattices (and Heyting algebras), whereas $T_1$ degrees do not.

5. Topos-Theoretic Characterization:
   The paper provides a synthetic interpretation of these results. The co-Turing degree corresponds to the smallest Lawvere–Tierney topology that makes the inclusion of the $j$-sheafification of the two-element set into the double-negation sheafification dense.

4. Key Results

• Theorem 4.17 (Main Technical Lemma): A coding oracle $c_{P,Q}$ is "omniscient" (equivalent to the degree $\omega$) if and only if the promise problem $(P \times Q, Q \times P)$ is decidable. This links the ability to communicate arbitrary information to the decidability of a specific "double-query" promise problem.
• Theorem 5.8: The map $a \mapsto \text{coT}(a)$ is an order-reversing embedding of the Turing degrees into the $T_3$ degrees.
• Theorem 6.4:
  • If $\text{coT}(a) \ge b$ for a Turing degree $b$, then either $a=0$ or $b=0$.
  • $\text{coT}(a)$ is never less than or equal to a non-zero Turing degree $b$.
• Proposition 3.6: In the $T_1$ degrees, there are no minimal pairs of non-zero $T_0$ degrees. If $f \in T_1$ and $g \in T_0$ have a meet of 0, then one of them must be 0.

5. Significance

• Structural Insight: The paper reveals a deep duality in the structure of computability. While Turing degrees represent the complexity of computing functions, the "co-Turing" degrees represent a form of "information hiding" or "adversarial encoding" that is structurally dual to the original complexity.
• Bridging Fields: It successfully bridges classical computability theory (Turing degrees, halting problem) with categorical logic (effective topos, Lawvere–Tierney topologies). The game-theoretic definitions are shown to be equivalent to topological properties in the effective topos.
• Clarification of Non-Determinism: The work clarifies the distinct roles of angelic (Nimue) and demonic (Merlin) non-determinism. It shows that introducing angelic non-determinism (moving from $T_2$ to $T_3$) allows for the construction of degrees that are incomparable with standard Turing degrees, creating a rich structure where classical degrees sit as a specific, order-reversed cone.
• Resolution of Riddles: The paper resolves the "riddle" posed in the introduction regarding whether asking a question and its negation allows one to solve arbitrary boolean problems. It proves that while this trick works for specific promise problems (leading to the omniscient degree $\omega$), it fails for general cases, and the "co-Turing" degrees represent the limit of what can be achieved by such dual-query strategies without collapsing to triviality.

In summary, the paper constructs a rigorous framework where the "co-Turing" degrees serve as a mirror image of the Turing degrees within the landscape of generalized computability, demonstrating that while they are structurally isomorphic (in reverse), they occupy a distinct, incomparable region of the computational universe.