Asymptotic density and computably Enumerable Sets
Asymptotic density and computably Enumerable Sets
复制标题
渐近密度和可计算可枚举集
DOI：
10.1142/s0219061313500050
复制
发表时间：
2013
期刊：
影响因子：
--
通讯作者：
P. Schupp
中科院分区：
文献类型：
--
作者：
R. Downey;C. Jockusch;P. Schupp
我们研究了经典渐近密度和c.e.之间的联系集.我们证明了一个c.e.图灵度d不低当且仅当d包含c.e.密度为1的集合A没有密度为1的可计算子集，给出了非低c.e.度相反，我们证明了每个非零c.e.度包含一般可计算但不粗可计算的集合。集合的计算复杂性和它作为真实的数的密度的计算复杂性之间有非常密切的联系，其中我们将真实的数的复杂性度量为它们在算术层次中的左戴德金割的位置。我们刻画了可计算集和可计算集的下密度、上密度和密度。我们还研究了“可计算密度r”，其中r是一个任意的真实的数在单位区间。最后，我们研究密度和经典的小概念，如免疫力和凝聚力之间的联系。
We study connections between classical asymptotic density and c.e. sets. We prove that a c.e. Turing degree d is not low if and only if d contains a c.e. set A of density 1 which has no computable subsets of density 1, giving a natural characterization of non-low c.e. degrees. In contrast, we prove that every nonzero c.e. degree contains a set which is generically computable but not coarsely computable. There is a very close connection between the computational complexity of a set and the computational complexity of its density as a real number where we measure complexity of real numbers as the position of their left Dedekind cuts in the Arithmetic Hierarchy. We characterize the lower densities, upper densities and densities of both computable and computably enumerable sets. We also study "computable at density r" where r is an arbitrary real number in the unit interval. Finally, we study connections between density and classical smallness notions such as immunity and cohesiveness.