Page 1

Displaying 1 – 1 of 1

Showing per page

Asymptotic density, computable traceability, and 1-randomness

Uri Andrews, Mingzhong Cai, David Diamondstone, Carl Jockusch, Steffen Lempp (2016)

Fundamenta Mathematicae

Let r ∈ [0,1]. A set A ⊆ ω is said to be coarsely computable at density r if there is a computable function f such that {n | f(n) = A(n)} has lower density at least r. Our main results are that A is coarsely computable at density 1/2 if A 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.

Currently displaying 1 – 1 of 1

Page 1