Wyniki wyszukiwania

Sortuj według:

Ogranicz wyniki do:

Asymptotic density, computable traceability, and 1-randomness

100%

Andrews U., Cai M., Diamondstone D., Jockusch C., Lempp S.

Fundamenta Mathematicae

2016

tom 234

nr 1

41-53

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.

Ograniczanie wyników

1 Fundamenta Mathematicae

1 Andrews U.

1 Cai M.

1 Diamondstone D.

1 Jockusch C.

1 Lempp S.

1 2016

Wyniki wyszukiwania

Asymptotic density, computable traceability, and 1-randomness