Categorifying computable reducibilities
From MaRDI portal
Publication:6507968
arXiv2208.08656MaRDI QIDQ6507968FDOQ6507968
Authors: Davide Trotta, Manlio Valenti, Valeria de Paiva 
Abstract: This paper discusses categorical formulations of the Medvedev, Muchnik and Weirauch reducibilities in Computability Theory and connects these reducibilities to different Lawvere categorical doctrines. These specific doctrines were used in previous work to provide categorical models for Dialectica logical properties. We relate Medvedev and Weyrauch doctrines to the Dialectica doctrine, showing that all these doctrines can be conceptualized in terms of (logic) quantifier (existential and universal) completions.
Categorical logic, topoi (03G30) Other degrees and reducibilities in computability and recursion theory (03D30)
This page was built for publication: Categorifying computable reducibilities
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6507968)
