Categorifying computable reducibilities

MaRDI QIDQ6507968arXivFDO

Authors Davide Trotta, Manlio Valenti, Valeria de Paiva

Mathematics Subject Classification ID

Categorical logic, topoi (03G30) Other degrees and reducibilities in computability and recursion theory (03D30)

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.

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)