Characterizing the continuous degrees
Characterizing the continuous degrees
复制标题
表征连续度
DOI：
10.1007/s11856-019-1943-x
复制
发表时间：
2019
影响因子：
1
通讯作者：
Soskova, Mariya I.
中科院分区：
文献类型：
--
作者：
Andrews, Uri;Igusa, Gregory;Miller, Joseph S.;Soskova, Mariya I.
连续度度量可计算度量空间元素的可计算性理论内容。它们适当地扩展了图灵度，并自然地嵌入枚举度。虽然不完全（即，非图灵）连续度存在，它们都非常接近于全：将一个连续度与一个不低于它的全度连接起来总是得到一个全度。我们称之为几乎全性，并证明了几乎全度与连续度重合。由于全度可以在枚举度的偏序中定义[1]，我们看到连续度也可以定义。应用先前关于连续度的工作[10]，这表明全度上的关系“PA above”在枚举度中是可定义的。为了证明每个几乎全度都是连续的，我们通过连续度的另一个特征，稍微简化了Kihara和Pauly [7]中的一个。我们证明了A的枚举度是连续的当且仅当A是可编码的，即A是一棵无限树的补树上的枚举，该树的每条路都枚举A。
The continuous degrees measure the computability-theoretic content of elements of computable metric spaces. They properly extend the Turing degrees and naturally embed into the enumeration degrees. Although nontotal (i.e., non-Turing) continuous degrees exist, they are all very close to total: joining a continuous degree with a total degree that is not below it always results in a total degree. We call this property almost totality.We prove that the almost total degrees coincide with the continuous degrees. Since the total degrees are definable in the partial order of enumeration degrees [1], we see that the continuous degrees are also definable. Applying earlier work on the continuous degrees [10], this shows that the relation “PA above” on the total degrees is definable in the enumeration degrees.In order to prove that every almost total degree is continuous, we pass through another characterization of the continuous degrees that slightly simplifies one of Kihara and Pauly [7]. We prove that the enumeration degree ofAis continuous if and only ifAis codable, meaning thatAis enumeration above the complement of an infinite tree, every path of which enumeratesA.
登录
查看更多内容
一般空间上算法随机性的统一测试
影响因子：
1.1
作者：
P. Gács
通讯作者：
P. Gács
不可计算测量的随机性
DOI：
--
发表时间：
2013
期刊：
影响因子：
--
作者：
A. Day;Joseph S. Miller
通讯作者：
Joseph S. Miller
DOI：
--
发表时间：
1959
期刊：
影响因子：
--
作者：
R. Friedberg;H. Rogers
通讯作者：
H. Rogers
P. Urysohn 的超精细测量
DOI：
--
发表时间：
--
期刊：
影响因子：
--
作者：
A. Tychonoff
通讯作者：
A. Tychonoff
DOI：
--
发表时间：
1971
期刊：
影响因子：
--
作者：
A. Selman
通讯作者：
A. Selman