Categorifying computable reducibilities
This paper presents categorical formulations of Turing, Medvedev, Muchnik, and Weihrauch reducibilities in Computability Theory, utilizing Lawvere doctrines. While the first notions lend themselves to a smooth categorical presentation, essentially dualizing the traditional idea of realizability doct...
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Logical Methods in Computer Science e.V.
2025-02-01
|
| Series: | Logical Methods in Computer Science |
| Subjects: | |
| Online Access: | http://lmcs.episciences.org/11378/pdf |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1849344769248985088 |
|---|---|
| author | Davide Trotta Manlio Valenti Valeria de Paiva |
| author_facet | Davide Trotta Manlio Valenti Valeria de Paiva |
| author_sort | Davide Trotta |
| collection | DOAJ |
| description | This paper presents categorical formulations of Turing, Medvedev, Muchnik, and Weihrauch reducibilities in Computability Theory, utilizing Lawvere doctrines. While the first notions lend themselves to a smooth categorical presentation, essentially dualizing the traditional idea of realizability doctrines, Weihrauch reducibility and its extensions to represented and multi-represented spaces require a separate investigation. Our abstract analysis of these concepts highlights a shared characteristic among all these reducibilities. Specifically, we demonstrate that all these doctrines stemming from computability concepts can be proven to be instances of completions of quantifiers for doctrines, analogous to what occurs for doctrines for realizability. As a corollary of these results, we will be able to formally compare Weihrauch reducibility with the dialectica doctrine constructed from a doctrine representing Turing degrees. |
| format | Article |
| id | doaj-art-e1b25e8ac5df4fda850049efe8c7c30b |
| institution | Kabale University |
| issn | 1860-5974 |
| language | English |
| publishDate | 2025-02-01 |
| publisher | Logical Methods in Computer Science e.V. |
| record_format | Article |
| series | Logical Methods in Computer Science |
| spelling | doaj-art-e1b25e8ac5df4fda850049efe8c7c30b2025-08-20T03:42:35ZengLogical Methods in Computer Science e.V.Logical Methods in Computer Science1860-59742025-02-01Volume 21, Issue 110.46298/lmcs-21(1:15)202511378Categorifying computable reducibilitiesDavide TrottaManlio ValentiValeria de PaivaThis paper presents categorical formulations of Turing, Medvedev, Muchnik, and Weihrauch reducibilities in Computability Theory, utilizing Lawvere doctrines. While the first notions lend themselves to a smooth categorical presentation, essentially dualizing the traditional idea of realizability doctrines, Weihrauch reducibility and its extensions to represented and multi-represented spaces require a separate investigation. Our abstract analysis of these concepts highlights a shared characteristic among all these reducibilities. Specifically, we demonstrate that all these doctrines stemming from computability concepts can be proven to be instances of completions of quantifiers for doctrines, analogous to what occurs for doctrines for realizability. As a corollary of these results, we will be able to formally compare Weihrauch reducibility with the dialectica doctrine constructed from a doctrine representing Turing degrees.http://lmcs.episciences.org/11378/pdfmathematics - logicmathematics - category theory |
| spellingShingle | Davide Trotta Manlio Valenti Valeria de Paiva Categorifying computable reducibilities Logical Methods in Computer Science mathematics - logic mathematics - category theory |
| title | Categorifying computable reducibilities |
| title_full | Categorifying computable reducibilities |
| title_fullStr | Categorifying computable reducibilities |
| title_full_unstemmed | Categorifying computable reducibilities |
| title_short | Categorifying computable reducibilities |
| title_sort | categorifying computable reducibilities |
| topic | mathematics - logic mathematics - category theory |
| url | http://lmcs.episciences.org/11378/pdf |
| work_keys_str_mv | AT davidetrotta categorifyingcomputablereducibilities AT manliovalenti categorifyingcomputablereducibilities AT valeriadepaiva categorifyingcomputablereducibilities |