Davide Trotta ; Manlio Valenti ; Valeria de Paiva - Categorifying computable reducibilities

lmcs:11378 - Logical Methods in Computer Science, February 11, 2025, Volume 21, Issue 1 - https://doi.org/10.46298/lmcs-21(1:15)2025
Categorifying computable reducibilitiesArticle

Authors: Davide Trotta ; Manlio Valenti ; Valeria de Paiva

    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.


    Volume: Volume 21, Issue 1
    Published on: February 11, 2025
    Accepted on: December 16, 2024
    Submitted on: May 25, 2023
    Keywords: Mathematics - Logic,Mathematics - Category Theory

    Consultation statistics

    This page has been seen 470 times.
    This article's PDF has been downloaded 200 times.