Inside the Muchnik degrees I: Discontinuity, learnability and constructivism
Inside the Muchnik degrees I: Discontinuity, learnability and constructivism
复制标题
DOI：
10.1016/j.apal.2014.01.003
复制
发表时间：
2012-10
期刊：
影响因子：
--
通讯作者：
Kojiro Higuchi;Takayuki Kihara
中科院分区：
文献类型：
--
作者：
Kojiro Higuchi;Takayuki Kihara
每个可计算函数都必须是连续的。为了发展不连续函数的可计算性理论，我们研究了Baire空间上非一致可计算函数的算术层次的低层。首先，我们从学习理论和分段可计算性的角度对Baire空间上的非一致可计算函数进行了分类。例如，我们证明了思维变化有界的可学习性等价于有限的（Δ 10）2-分段可计算性（其中（Δ 10）2表示两个Δ 10集合的差），误差有界的可学习性等价于有限的Δ 20-分段可计算性，可学习性等价于可数的Δ 10-分段可计算性（等价于可数的Δ 20-分段可计算性）。其次，我们介绍了析取类操作，如基于BHK的解释的余积，然后，我们看到，这些操作诱导伽罗瓦之间的连接梅德韦杰夫度结构和相关的梅德韦杰夫/Muchnik的度结构。最后，我们解释这些结果的背景下，Weihrauch度和Wadge样的游戏。
Every computable function has to be continuous. To develop computability theory of discontinuous functions, we study low levels of the arithmetical hierarchy of nonuniformly computable functions on Baire space. First, we classify nonuniformly computable functions on Baire space from the viewpoint of learning theory and piecewise computability. For instance, we show that mind-change-bounded learnability is equivalent to finite (Π 1 0) 2-piecewise computability (where (Π 1 0) 2 denotes the difference of two Π 1 0 sets), error-bounded learnability is equivalent to finite Δ 2 0-piecewise computability, and learnability is equivalent to countable Π 1 0-piecewise computability (equivalently, countable Σ 2 0-piecewise computability). Second, we introduce disjunction-like operations such as the coproduct based on BHK-like interpretations, and then, we see that these operations induce Galois connections between the Medvedev degree structure and associated Medvedev/Muchnik-like degree structures. Finally, we interpret these results in the context of the Weihrauch degrees and Wadge-like games.