Generic computability, Turing degrees, and asymptotic density
Generic computability, Turing degrees, and asymptotic density
复制标题
通用可计算性、图灵度和渐近密度
DOI：
--
复制
发表时间：
2010
期刊：
影响因子：
--
通讯作者：
P. Schupp
中科院分区：
文献类型：
--
作者：
C. Jockusch;P. Schupp
一般可判断性在群论中得到了广泛的研究，现在我们在经典的可计算性理论的背景下研究它。一个自然数集A称为一般可计算的，如果在它的定义域D上有一个部分可计算函数符合A的特征函数，并且D具有密度1，即Lim n→∞|{k
Generic decidability has been extensively studied in group theory, and we now study it in the context of classical computability theory. A set A of natural numbers is called generically computable if there is a partial computable function that agrees with the characteristic function of A on its domain D, and furthermore D has density 1, that is, lim n→∞ |{k