WEIHRAUCH DEGREES, OMNISCIENCE PRINCIPLES AND WEAK COMPUTABILITY
WEIHRAUCH DEGREES, OMNISCIENCE PRINCIPLES AND WEAK COMPUTABILITY
复制标题
DOI：
10.2178/jsl/1294170993
复制
发表时间：
2011-03-01
影响因子：
0.6
通讯作者：
Gherardi, Guido
中科院分区：
文献类型：
--
作者：
Brattka, Vasco;Gherardi, Guido
在本文中，我们研究了一个约化，已介绍了克劳斯Weihrauch，或更准确地说，一个自然的扩展多值函数的表示空间。我们呼吁相应的等价类Weihrauch度，我们表明，相应的偏序诱导下半格。事实证明，并行化是这个半格的一个闭包算子，并行化的Weihrauch度甚至形成了一个可以嵌入梅德韦杰夫格和图灵度的格。Weihrauch度的重要性是基于这样一个事实，即表示空间上的多值函数可以被认为是数学定理的实现者，并且在这个意义上研究定理之间的Weihrauch约简意味着要问哪些定理可以连续地或可计算地相互转换。作为该分类方案的关键点，研究了全知LPO的有限原理、全知LLPO的较小有限原理及其并行化。证明了并行化的LLPO等价于弱Konig引理，从而等价于新的强意义下的Hahn-Banach定理。我们称一个多值函数弱可计算的，如果它是可减少的Weihrauch程度的并行LLPO，我们提出了一个新的证明，基于计算版本的Kleene的三元逻辑，一类弱可计算的操作是封闭的组合。此外，弱可计算运算的可计算度量空间的特点是操作，允许上半可计算的紧值选择器，并证明了任何单值弱可计算运算已经是在普通意义上的可计算。
In this paper we study a reducibility that has been introduced by Klaus Weihrauch or, more precisely, a natural extension for multi-valued functions on represented spaces. We call the corresponding equivalence classes Weihrauch degrees and we show that the corresponding partial order induces a lower semi-lattice. It turns out that parallelization is a closure operator for this semi-lattice and that the parallelized Weihrauch degrees even form a lattice into which the Medvedev lattice and the Turing degrees can be embedded. The importance of Weihrauch degrees is based on the fact that multi-valued functions on represented spaces can be considered as realizers of mathematical theorems in a very natural way and studying the Weihrauch reductions between theorems in this sense means to ask which theorems can be transformed continuously or computably into each other. As crucial corner points of this classification scheme the limited principle of omniscience LPO, the lesser limited principle of omniscience LLPO and their parallelizations are studied. It is proved that parallelized LLPO is equivalent to Weak Konig's Lemma and hence to the Hahn-Banach Theorem in this new and very strong sense. We call a multi-valued function weakly computable if it is reducible to the Weihrauch degree of parallelized LLPO and we present a new proof, based on a computational version of Kleene's ternary logic, that the class of weakly computable operations is closed under composition. Moreover, weakly computable operations on computable metric spaces are characterized as operations that admit upper semi-computable compact-valued selectors and it is proved that any single-valued weakly computable operation is already computable in the ordinary sense.