An order-reversing embedding of Turing degrees into Arthur-Nimue-Merlin degrees
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915877590401024 |
|---|---|
| author | Samra, Jean Abou Madore, David Alexander |
| author_facet | Samra, Jean Abou Madore, David Alexander |
| contents | The Arthur-Nimue-Merlin degrees are a generalization of the Turing degrees introduced by Kihara as a tangible description of the partially ordered set of Lawvere-Tierney topologies on the effective topos (equivalently, subtoposes of the effective topos). They are defined in terms of a three-player game that introduces both angelic and demonic non-determinism into oracle queries. We construct an order embedding of the Turing degrees with their order reversed into the Arthur-Nimue-Merlin degrees, whose image we call the "co-Turing degrees"; we then study the order relationship of these co-Turing degrees with the (naturally embedded) Turing degrees within the Arthur-Nimue-Merlin degrees. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2603_19946 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | An order-reversing embedding of Turing degrees into Arthur-Nimue-Merlin degrees Samra, Jean Abou Madore, David Alexander Logic Logic in Computer Science 03D30, 03G30, 03F65 The Arthur-Nimue-Merlin degrees are a generalization of the Turing degrees introduced by Kihara as a tangible description of the partially ordered set of Lawvere-Tierney topologies on the effective topos (equivalently, subtoposes of the effective topos). They are defined in terms of a three-player game that introduces both angelic and demonic non-determinism into oracle queries. We construct an order embedding of the Turing degrees with their order reversed into the Arthur-Nimue-Merlin degrees, whose image we call the "co-Turing degrees"; we then study the order relationship of these co-Turing degrees with the (naturally embedded) Turing degrees within the Arthur-Nimue-Merlin degrees. |
| title | An order-reversing embedding of Turing degrees into Arthur-Nimue-Merlin degrees |
| topic | Logic Logic in Computer Science 03D30, 03G30, 03F65 |
| url | https://arxiv.org/abs/2603.19946 |