Asymptotic density, computable traceability, and 1-randomness

• Autorzy: Uri Andrews , Mingzhong Cai , David Diamondstone , Carl Jockusch , Steffen Lempp
• Języki publikacji: EN

Abstrakty

EN

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.

Kategorie tematyczne

• 03D28: Other Turing degree structures
• 03D32: Algorithmic randomness and dimension

• Wydawca: Institute of Mathematics Polish Academy of Sciences
• Czasopismo: Fundamenta Mathematicae
• Rocznik: 2016
• Tom: 234
• Numer: 1
• Strony: 41-53

Daty

wydano

2016

Twórcy

autor

Uri Andrews

• Department of Mathematics, University of Wisconsin, 480 Lincoln Dr., Madison, WI 53706-1388, U.S.A.

autor

Mingzhong Cai

• Department of Mathematics, Dartmouth College, Hanover, NH 03755, U.S.A.

autor

David Diamondstone

• Google, 1600 Amphitheatre Parkway, Mountain View, CA 94043, U.S.A.

autor

Carl Jockusch

• Department of Mathematics, University of Illinois at Urbana-Champaign, 1409 W. Green St., Urbana, IL 61801 U.S.A.

autor

Steffen Lempp

• Department of Mathematics, University of Wisconsin, 480 Lincoln Dr., Madison, WI 53706-1388, U.S.A.

Identyfikatory

DOI

10.4064/fm118-10-2015