Czasopismo
Tytuł artykułu
Warianty tytułu
Języki publikacji
Abstrakty
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.
Słowa kluczowe
Kategorie tematyczne
Czasopismo
Rocznik
Tom
Numer
Strony
41-53
Opis fizyczny
Daty
wydano
2016
Twórcy
autor
- Department of Mathematics, University of Wisconsin, 480 Lincoln Dr., Madison, WI 53706-1388, U.S.A.
autor
- Department of Mathematics, Dartmouth College, Hanover, NH 03755, U.S.A.
autor
- Google, 1600 Amphitheatre Parkway, Mountain View, CA 94043, U.S.A.
autor
- Department of Mathematics, University of Illinois at Urbana-Champaign, 1409 W. Green St., Urbana, IL 61801 U.S.A.
autor
- Department of Mathematics, University of Wisconsin, 480 Lincoln Dr., Madison, WI 53706-1388, U.S.A.
Bibliografia
Typ dokumentu
Bibliografia
Identyfikatory
Identyfikator YADDA
bwmeta1.element.bwnjournal-article-doi-10_4064-fm118-10-2015