论文标题
分类可计算的还原性
Categorifying computable reducibilities
论文作者
论文摘要
本文介绍了使用律师学说的图灵，梅德韦杰夫，muchnik和Weihrauch降低的分类公式。尽管第一个概念将自己借助平稳的分类呈现，从本质上讲是使传统的可靠性学说的偶数偶联，但Weihrauch的可降低性及其扩展为代表和多代表的空间需要单独研究。我们对这些概念的抽象分析突出了所有这些降低性的共同特征。具体而言，我们证明，所有这些学说源于可计算性概念，可以被证明是量化学说的完成的实例，类似于实现可实现的学说的情况。作为这些结果的推论，我们将能够将Weihrauch的可缩回性正式比较与代表图灵学位的学说构建的辩证法学说。
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.
