Asymptotic density, computable traceability, and 1-randomness

作者：Andrews Uri^*; Cai Mingzhong; Diamondstone David; Jockusch Carl; Lempp Steffen

来源：Fundamenta Mathematicae, 2016, 234(1): 41-54.

DOI：10.4064/fm118-10-2015

• computability theory
• asymptotic density
• computably traceable
• 1-random
• hyperimmune degrees
• PA degrees

Let r is an element of [0, 1]. A set A subset of omega is said to be coarsely computable at density r if there is a computable function f such that {n vertical bar f (n) = A(n)} has lower density at least r. Our main results are that Lambda is coarsely computable at density 1/2 if Lambda is computably traceable or truth-table reducible to a 1-random set. In the other direction, we show that if a degree a is hyperimmune or PA, then there is an a-computable set which is not coarsely computable at any positive density.

• 出版日期2016