PL EN


Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
2016 | 234 | 1 | 41-53
Tytuł artykułu

Asymptotic density, computable traceability, and 1-randomness

Treść / Zawartość
Warianty tytułu
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.
Słowa kluczowe
Rocznik
Tom
234
Numer
1
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.
  • Department of Mathematics, Dartmouth College, Hanover, NH 03755, U.S.A.
  • Google, 1600 Amphitheatre Parkway, Mountain View, CA 94043, U.S.A.
  • Department of Mathematics, University of Illinois at Urbana-Champaign, 1409 W. Green St., Urbana, IL 61801 U.S.A.
  • 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
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.