No Cover Image

Journal article 182 views 13 downloads

Categorifying computable reducibilities

Davide Trotta, Manlio Valenti Orcid Logo, Valeria de Paiva

Logical Methods in Computer Science, Volume: 21, Issue: 1, Pages: 15:1 - 15:36

Swansea University Author: Manlio Valenti Orcid Logo

  • 71415.VoR.pdf

    PDF | Version of Record

    © D.Trotta, M. Valenti, and V. de Paiva. Released under the terms of a Creative Commons Attribution 4.0 International (CC BY 4.0) license.

    Download (589.43KB)

Check full text

DOI (Published version): 10.46298/lmcs-21(1:15)2025

Abstract

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...

Full description

Published in: Logical Methods in Computer Science
ISSN: 1860-5974 1860-5974
Published: Centre pour la Communication Scientifique Directe (CCSD) 2026
Online Access: Check full text

URI: https://cronfa.swan.ac.uk/Record/cronfa71415
first_indexed 2026-02-13T10:50:28Z
last_indexed 2026-03-17T05:37:09Z
id cronfa71415
recordtype SURis
fullrecord <?xml version="1.0"?><rfc1807><datestamp>2026-03-16T12:02:00.4684947</datestamp><bib-version>v2</bib-version><id>71415</id><entry>2026-02-13</entry><title>Categorifying computable reducibilities</title><swanseaauthors><author><sid>133b5d626ca91216041d4556dc9251fb</sid><ORCID>0000-0003-0351-3058</ORCID><firstname>Manlio</firstname><surname>Valenti</surname><name>Manlio Valenti</name><active>true</active><ethesisStudent>false</ethesisStudent></author></swanseaauthors><date>2026-02-13</date><deptcode>MACS</deptcode><abstract>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.</abstract><type>Journal Article</type><journal>Logical Methods in Computer Science</journal><volume>21</volume><journalNumber>1</journalNumber><paginationStart>15:1</paginationStart><paginationEnd>15:36</paginationEnd><publisher>Centre pour la Communication Scientifique Directe (CCSD)</publisher><placeOfPublication/><isbnPrint/><isbnElectronic/><issnPrint>1860-5974</issnPrint><issnElectronic>1860-5974</issnElectronic><keywords>Mathematics - Logic, Mathematics - Category Theory</keywords><publishedDay>11</publishedDay><publishedMonth>2</publishedMonth><publishedYear>2026</publishedYear><publishedDate>2026-02-11</publishedDate><doi>10.46298/lmcs-21(1:15)2025</doi><url/><notes/><college>COLLEGE NANME</college><department>Mathematics and Computer Science School</department><CollegeCode>COLLEGE CODE</CollegeCode><DepartmentCode>MACS</DepartmentCode><institution>Swansea University</institution><apcterm>Another institution paid the OA fee</apcterm><funders>Davide Trotta&#x2019;s research has been partially supported by the Italian MIUR project PRIN 2017FTXR7S IT-MATTERS (Methods and Tools for Trustworthy Smart Systems). Manlio Valenti&#x2019;s research was partially supported by the Italian PRIN 2017 Grant Mathematical Logic: models, sets, computability. Valeria de Paiva and Davide Trotta are grateful to the Hausdorff Research Institute for Mathematics in Bonn, Germany, for hosting us as part of the trimester &#x201C;Prospects of Formal Mathematics,&#x201D; funded by the Deutsche Forschungsgemeinschaft (DFG, German Research Foundation) under Germany&#x2019;s Excellence Strategy&#x2013; EXC2047/1&#x2013; 390685813.</funders><projectreference/><lastEdited>2026-03-16T12:02:00.4684947</lastEdited><Created>2026-02-13T10:47:07.8635886</Created><path><level id="1">Faculty of Science and Engineering</level><level id="2">School of Mathematics and Computer Science - Computer Science</level></path><authors><author><firstname>Davide</firstname><surname>Trotta</surname><order>1</order></author><author><firstname>Manlio</firstname><surname>Valenti</surname><orcid>0000-0003-0351-3058</orcid><order>2</order></author><author><firstname>Valeria de</firstname><surname>Paiva</surname><order>3</order></author></authors><documents><document><filename>71415__36418__7df777d598d5476b8a82ec0b2fa0b99c.pdf</filename><originalFilename>71415.VoR.pdf</originalFilename><uploaded>2026-03-16T11:58:43.1887545</uploaded><type>Output</type><contentLength>603575</contentLength><contentType>application/pdf</contentType><version>Version of Record</version><cronfaStatus>true</cronfaStatus><documentNotes>&#xA9; D.Trotta, M. Valenti, and V. de Paiva. Released under the terms of a Creative Commons Attribution 4.0 International (CC BY 4.0) license.</documentNotes><copyrightCorrect>true</copyrightCorrect><language>eng</language><licence>https://creativecommons.org/licenses/by/4.0</licence></document></documents><OutputDurs/></rfc1807>
spelling 2026-03-16T12:02:00.4684947 v2 71415 2026-02-13 Categorifying computable reducibilities 133b5d626ca91216041d4556dc9251fb 0000-0003-0351-3058 Manlio Valenti Manlio Valenti true false 2026-02-13 MACS 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. Journal Article Logical Methods in Computer Science 21 1 15:1 15:36 Centre pour la Communication Scientifique Directe (CCSD) 1860-5974 1860-5974 Mathematics - Logic, Mathematics - Category Theory 11 2 2026 2026-02-11 10.46298/lmcs-21(1:15)2025 COLLEGE NANME Mathematics and Computer Science School COLLEGE CODE MACS Swansea University Another institution paid the OA fee Davide Trotta’s research has been partially supported by the Italian MIUR project PRIN 2017FTXR7S IT-MATTERS (Methods and Tools for Trustworthy Smart Systems). Manlio Valenti’s research was partially supported by the Italian PRIN 2017 Grant Mathematical Logic: models, sets, computability. Valeria de Paiva and Davide Trotta are grateful to the Hausdorff Research Institute for Mathematics in Bonn, Germany, for hosting us as part of the trimester “Prospects of Formal Mathematics,” funded by the Deutsche Forschungsgemeinschaft (DFG, German Research Foundation) under Germany’s Excellence Strategy– EXC2047/1– 390685813. 2026-03-16T12:02:00.4684947 2026-02-13T10:47:07.8635886 Faculty of Science and Engineering School of Mathematics and Computer Science - Computer Science Davide Trotta 1 Manlio Valenti 0000-0003-0351-3058 2 Valeria de Paiva 3 71415__36418__7df777d598d5476b8a82ec0b2fa0b99c.pdf 71415.VoR.pdf 2026-03-16T11:58:43.1887545 Output 603575 application/pdf Version of Record true © D.Trotta, M. Valenti, and V. de Paiva. Released under the terms of a Creative Commons Attribution 4.0 International (CC BY 4.0) license. true eng https://creativecommons.org/licenses/by/4.0
title Categorifying computable reducibilities
spellingShingle Categorifying computable reducibilities
Manlio Valenti
title_short Categorifying computable reducibilities
title_full Categorifying computable reducibilities
title_fullStr Categorifying computable reducibilities
title_full_unstemmed Categorifying computable reducibilities
title_sort Categorifying computable reducibilities
author_id_str_mv 133b5d626ca91216041d4556dc9251fb
author_id_fullname_str_mv 133b5d626ca91216041d4556dc9251fb_***_Manlio Valenti
author Manlio Valenti
author2 Davide Trotta
Manlio Valenti
Valeria de Paiva
format Journal article
container_title Logical Methods in Computer Science
container_volume 21
container_issue 1
container_start_page 15:1
publishDate 2026
institution Swansea University
issn 1860-5974
1860-5974
doi_str_mv 10.46298/lmcs-21(1:15)2025
publisher Centre pour la Communication Scientifique Directe (CCSD)
college_str Faculty of Science and Engineering
hierarchytype
hierarchy_top_id facultyofscienceandengineering
hierarchy_top_title Faculty of Science and Engineering
hierarchy_parent_id facultyofscienceandengineering
hierarchy_parent_title Faculty of Science and Engineering
department_str School of Mathematics and Computer Science - Computer Science{{{_:::_}}}Faculty of Science and Engineering{{{_:::_}}}School of Mathematics and Computer Science - Computer Science
document_store_str 1
active_str 0
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.
published_date 2026-02-11T05:42:26Z
_version_ 1862872593251434496
score 11.102276

Similar Items