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

1. Contesto e Problema

Il lavoro si inserisce nel campo della teoria della computabilità e della teoria dei topos, in particolare nello studio dei gradi di Turing generalizzati all'interno del topos effettivo (effective topos).

• Oggetto di studio: I "gradi Arthur-Nimue-Merlin" (spesso indicati come gradi $T_3$), introdotti da Kihara. Questi gradi generalizzano i gradi di Turing classici ($T_0$) incorporando due forme di non-determinismo in un gioco a tre giocatori:
  • Arthur: Un giocatore computazionale (strategie computabili).
  • Nimue: Un agente "angelico" (benevolo) che sceglie un insieme di opzioni per Arthur.
  • Merlin: Un agente "demoniaco" (avversario) che sceglie un valore specifico dall'insieme fornito da Nimue.
• Gerarchia dei gradi:
  • $T_0$: Gradi di Turing classici (funzioni totali $N \to N$).
  • $T_1$: Funzioni parziali ($N \rightharpoonup N$).
  • $T_2$: Funzioni parziali non deterministiche avversarie ($N \rightharpoonup \mathcal{P}(N)$).
  • $T_3$: Funzioni totali con non-determinismo sia angelico che avversario ($N \to \mathcal{P}(\mathcal{P}(N))$).
• Il Problema: Sebbene i gradi di Turing siano stati mappati nei gradi $T_3$ da Hyland, la relazione tra l'ordine dei gradi di Turing e la struttura più ricca dei gradi $T_3$ non era completamente compresa. In particolare, gli autori si chiedono se esista un modo naturale per incorporare i gradi di Turing in questo nuovo ordinamento, e come questi si relazionino tra loro (es. esistenza di minimi, massimi, comparabilità).

2. Metodologia

Gli autori utilizzano un approccio ibrido che combina:

1. Teoria dei Giochi: Definizione rigorosa del "gioco di riduzione" tra oracoli. Un oracolo $f$ è riducibile a $g$ ($f \preceq g$) se Arthur e Nimue hanno una strategia vincente contro Merlin per calcolare $f$ usando $g$.
2. Teoria della Computabilità Classica: Uso di riduzioni many-to-one su problemi di promessa (promise problems) e proprietà dei gradi di Turing (es. coppie minime, teoremi di base).
3. Teoria dei Topos (Categorie): Riformulazione dei risultati in termini di topologie di Lawvere-Tierney sul topos effettivo. Questo fornisce un ponte tra la computabilità concreta e la logica intuizionista di ordine superiore.

La metodologia centrale ruota attorno alla definizione di due nuovi tipi di oracoli associati a un problema di promessa $(P, Q)$ (dove $P$ e $Q$ sono sottoinsiemi disgiunti e non vuoti di $\mathbb{N}$):

• Oracolo di Decodifica ($d_{P,Q}$): Risolve il problema di promessa (determina se un elemento è in $P$ o $Q$). Corrisponde a un grado $T_1$.
• Oracolo di Codifica ($c_{P,Q}$): Fornisce una risposta a una domanda "sì/no" arbitraria, ma codificata attraverso un elemento di $P$ (per "no") o $Q$ (per "sì"). Corrisponde a un grado $T_3$ "basico".

3. Contributi Chiave e Risultati Principali

A. Definizione dei "Co-Gradi di Turing" (Co-Turing Degrees)

Gli autori definiscono una nuova classe di gradi $T_3$, chiamati co-Gradi di Turing ($\text{coT}(d)$), associati a ogni grado di Turing $d = [A]_{T_0}$.

• Costruzione: Data una funzione caratteristica $A$, si definiscono gli insiemi $H^A_0$ e $H^A_1$ (insiemi di programmi che, con oracolo $A$, terminano restituendo 0 o 1).
• Si costruisce l'oracolo di codifica $\tilde{c}_A = c_{H^A_0, H^A_1}$.
• Risultato Fondamentale (Teorema 5.8): La mappa $\text{coT}: [A]_{T_0} \mapsto \tilde{c}_A$ è un embedding ordinante inverso (order-reversing embedding) dai gradi di Turing nei gradi $T_3$.
  • Formalmente: $d_1 \leq d_2 \iff \text{coT}(d_1) \geq \text{coT}(d_2)$.
  • Questo significa che un grado di Turing più "potente" (più difficile) corrisponde a un grado $T_3$ più "debole" (più facile da ridurre) nel nuovo ordinamento.

B. Incomparabilità tra Gradi di Turing e Co-Gradi

Un risultato sorprendente è la mancanza di comparabilità tra i gradi di Turing non banali e i co-gradi di Turing non banali.

• Teorema 6.4: Per qualsiasi grado di Turing $a > 0$ e $b > 0$:
  • Non è mai vero che $\text{coT}(a) \leq b$.
  • Se $\text{coT}(a) \geq b$, allora necessariamente $a = 0$ o $b = 0$.
• Implicazione: I co-gradi di Turing non forniscono "onniscienza" (il grado $\omega$, che permette di risolvere qualsiasi problema decidibile) a meno che il grado di Turing originale non sia computabile. Inoltre, non permettono di calcolare funzioni deterministiche non computabili che non fossero già computabili.

C. Proprietà dell'Ordine e dei Meet

• Assenza di Coppie Minime in $T_1$: Gli autori forniscono una prova diretta del fatto che non esistono coppie minime di gradi di Turing ($T_0$) all'interno dell'ordinamento $T_1$. Se $f \in T_1$ e $g \in T_0$ hanno meet nullo ($f \wedge g = 0$), allora uno dei due deve essere nullo.
• Struttura del Lattice: Viene analizzata la struttura reticolare dei gradi $T_1, T_2, T_3$. Mentre $T_0$ non è un reticolo completo (mancano meet per alcune coppie), i gradi $T_1, T_2, T_3$ ammettono meet e join binari. In particolare, i gradi $T_3$ formano un'algebra di Heyting (e quindi un reticolo distributivo).

D. Interpretazione Topos-Teorica

La sezione 7 offre una riformulazione profonda dei risultati:

• I gradi $T_3$ corrispondono biunivocamente alle topologie di Lawvere-Tierney sul topos effettivo.
• La costruzione $\text{coT}(d)$ corrisponde all'operazione di prendere la sheafification dell'oggetto a due elementi ($2$) rispetto alla topologia associata al grado di Turing $d$, e poi considerare la topologia più piccola che rende densa l'inclusione di questa sheafification nell'oggetto "costante" $\nabla 2$.
• Questo collega la computabilità inversa alla logica intuizionista e alla struttura dei sottotopi.

4. Significato e Implicazioni

1. Nuova Prospettiva sulla Computabilità: Il lavoro dimostra che l'aggiunta di non-determinismo "angelico" (Nimue) e "demoniaco" (Merlin) crea uno spazio ordinato in cui i gradi di Turing classici appaiono come un "cono" invertito. Questo ribalta l'intuizione classica: più un problema è difficile in senso classico, più diventa "facile" (o meglio, meno informativo) in questo contesto generalizzato di non-determinismo.
2. Risposta a Domande Aperte: Risponde alla domanda di Kihara (2023) sulla ricerca di "gradi $T_3$ basici interessanti", fornendo una classe naturale e strutturata di tali gradi.
3. Connessione Logico-Topos: Fornisce un ponte solido tra la teoria della computabilità classica (gradi di Turing) e la teoria dei topos effettivi, mostrando come operazioni logiche interne (sheafification, topologie di Lawvere-Tierney) corrispondano a operazioni computazionali specifiche (riduzioni, codifiche).
4. Limiti della Computabilità Generalizzata: Il risultato di incomparabilità (Teorema 6.4) stabilisce un confine netto: i gradi $T_3$ derivati da gradi di Turing non possono essere usati per "saltare" la gerarchia di Turing verso l'alto (non danno accesso a funzioni non computabili deterministiche) né verso il basso (non collassano in gradi computabili a meno che non partano da gradi computabili).

Conclusione

Il paper stabilisce una corrispondenza profonda e controintuitiva tra la difficoltà computazionale classica e la potenza di calcolo in un ambiente con non-determinismo misto. L'embedding inverso dei gradi di Turing nei gradi Arthur-Nimue-Merlin non è solo una curiosità tecnica, ma rivela una struttura sottostante nell'organizzazione della computabilità relativa e nella logica del topos effettivo, suggerendo che l'"onniscienza" in questo contesto ha una natura radicalmente diversa rispetto alla computabilità classica.