How Incomputable is the Separable Hahn-Banach Theorem?
How Incomputable is the Separable Hahn-Banach Theorem?
复制标题
可分离哈恩-巴纳赫定理有多不可计算？
DOI：
10.1016/j.entcs.2008.12.009
复制
发表时间：
2008
影响因子：
1.3
通讯作者：
Alberto Marcone
中科院分区：
文献类型：
--
作者：
G. Gherardi;Alberto Marcone
我们研究了逆向数学和可计算分析之间的一些基本联系。特别是，我们将展示如何使用弱柯尼希引理的框架内的可计算分析分类的不可计算的功能的低复杂性。通过定义多值函数Sep和多值函数约简的自然概念，得到了二阶算术子系统WKL 0的计算对应.研究了WKL 0与SEP-可计算多值函数类的相似性和区别。我们使用这些概念来提供一种方法来确定计算复杂性的哈恩-巴拿赫扩展定理。
We investigate some basic connections between reverse mathematics and computable analysis. In particular, we show how to use Weak König's Lemma within the framework of computable analysis to classify incomputable functions of low complexity. By defining the multi-valued function Sep and through the definition of a natural notion of reducibility for multi-valued functions, we obtain a computational counterpart of the subsystem of second order arithmetic WKL0. We study analogies and differences between WKL0and the class of Sep-computable multi-valued functions. We use these notions to provide a method to determine the computational complexity of the Hahn-Banach Extension Theorem.