Computability and Continuity on the Real Arithmetic Hierarchy and the Power of Type-2 Nondeterminism
Computability and Continuity on the Real Arithmetic Hierarchy and the Power of Type-2 Nondeterminism
复制标题
实算术层次结构的可计算性和连续性以及 2 类非确定性的力量
DOI：
--
复制
发表时间：
2005
期刊：
影响因子：
--
通讯作者：
M. Ziegler
中科院分区：
文献类型：
--
作者：
M. Ziegler
有时所谓的递归分析主定理意味着任何可计算的实函数都必然是连续的。为了处理不连续函数 f: ℝ→ℝ，我们考虑对实可计算性这一常见概念进行三种放宽：
非确定性计算；
相对化计算，特别是允许访问像 ∅' 或 ∅" 这样的预言；
根据实算术层次结构以较弱的方式对输入 xeℝ 和/或输出 y = f(x) 进行编码。
事实证明，在这些方法中，只有第一种方法提供了所需的功率。
The sometimes so-called Main Theorem of Recursive Analysis implies that any computable real function is necessarily continuous. We consider three relaxations of this common notion of real computability for the purpose of treating also discontinuous functions f: ℝ→ℝ:
non-deterministic computation;
relativized computation, specifically given access to oracles like ∅′ or ∅″;
encoding input xeℝ and/or output y = f(x) in weaker ways according to the Real Arithmetic Hierarchy.
It turns out that, among these approaches, only the first one provides the required power.