No Cover Image

Journal article 131 views 7 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
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.
Keywords: Mathematics - Logic, Mathematics - Category Theory
College: Faculty of Science and Engineering
Funders: 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.
Issue: 1
Start Page: 15:1
End Page: 15:36

Similar Items