JEDNOSTKA NAUKOWA KATEGORII A+

Asymptotic density, computable traceability, and 1-randomness

Tom 234 / 2016

Uri Andrews, Mingzhong Cai, David Diamondstone, Carl Jockusch, Steffen Lempp Fundamenta Mathematicae 234 (2016), 41-53 MSC: 03D28, 03D32. DOI: 10.4064/fm118-10-2015 Opublikowany online: 15 February 2016

Streszczenie

Let $r\in [0,1]$. A set $A \subseteq \omega $ is said to be coarsely computable at density $r$ if there is a computable function $f$ such that $\{n \mid 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 $\mathbf {a}$ is hyperimmune or PA, then there is an $\mathbf {a}$-computable set which is not coarsely computable at any positive density.

Autorzy

  • Uri AndrewsDepartment of Mathematics
    University of Wisconsin
    480 Lincoln Dr.
    Madison, WI 53706-1388, U.S.A.
    e-mail
  • Mingzhong CaiDepartment of Mathematics
    Dartmouth College
    Hanover, NH 03755, U.S.A.
    e-mail
  • David DiamondstoneGoogle
    1600 Amphitheatre Parkway
    Mountain View, CA 94043, U.S.A.
    e-mail
  • Carl JockuschDepartment of Mathematics
    University of Illinois at Urbana-Champaign
    1409 W. Green St.
    Urbana, IL 61801 U.S.A.
    e-mail
  • Steffen LemppDepartment of Mathematics
    University of Wisconsin
    480 Lincoln Dr.
    Madison, WI 53706-1388, U.S.A.
    e-mail

Przeszukaj wydawnictwa IMPAN

Zbyt krótkie zapytanie. Wpisz co najmniej 4 znaki.

Przepisz kod z obrazka

Odśwież obrazek

Odśwież obrazek