Asymptotic density and the coarse computability bound

dc.contributor.author Hirschfeldt, Dennis
dc.contributor.author Jockusch, Carl
dc.contributor.author McNicholl, Timothy
dc.contributor.author Schupp, Paul
dc.contributor.department Computer Science
dc.contributor.department Mathematics
dc.date 2018-02-18T17:04:27.000
dc.date.accessioned 2020-06-30T05:59:37Z
dc.date.available 2020-06-30T05:59:37Z
dc.date.copyright Fri Jan 01 00:00:00 UTC 2016
dc.date.issued 2016-02-11
dc.description.abstract <p>For r is an element of [0, 1] we say that a set A subset of omega is coarsely computable at density r if there is a computable set C such that {n: C(n) = A(n)} has lower density at least r. Let gamma (A) = sup{r : A is coarsely computable at density r}. We study the interactions of these concepts with Turing reducibility. For example, we show that if r is an element of (0, 1] there are sets A(0), A(1) such that gamma(A(0)) = gamma(A(1)) = r where A(0) is coarsely computable at density r while A(1) is not coarsely computable at density r. We show that a real r is an element of [0, 1] is equal to gamma (A) for some c.e. set A if and only if r is left-Sigma(0)(3). A surprising result is that if G is a Delta(0)(2) 1-generic set, and A < = (T) G with gamma(A) = 1, then A is coarsely computable at density 1.</p>
dc.description.comments <p>This is a manuscript of an article published as Hirschfeldt, Denis R., Carl G. Jockusch Jr, Timothy H. McNicholl, and Paul E. Schupp. "Asymptotic density and the coarse computability bound." <em>Computability</em> 5, no. 1 (2016): 13-27, doi:<a href="http://dx.doi.org/10.3233/COM-150035" target="_blank">10.3233/COM-150035</a>. Posted with permission.</p>
dc.format.mimetype application/pdf
dc.identifier archive/lib.dr.iastate.edu/math_pubs/110/
dc.identifier.articleid 1109
dc.identifier.contextkey 10462982
dc.identifier.s3bucket isulib-bepress-aws-west
dc.identifier.submissionpath math_pubs/110
dc.identifier.uri https://dr.lib.iastate.edu/handle/20.500.12876/54492
dc.language.iso en
dc.source.bitstream archive/lib.dr.iastate.edu/math_pubs/110/2016_McNicholl_AsymptoticDensity.pdf|||Fri Jan 14 18:40:07 UTC 2022
dc.source.uri 10.3233/COM-150035
dc.subject.disciplines Applied Mathematics
dc.subject.disciplines Mathematics
dc.subject.disciplines Numerical Analysis and Computation
dc.subject.keywords Asymptotic density
dc.subject.keywords coarse computability
dc.subject.keywords Turing degrees
dc.title Asymptotic density and the coarse computability bound
dc.type article
dc.type.genre article
dspace.entity.type Publication
relation.isAuthorOfPublication 52624580-cc7d-4600-800e-c84af32578ba
relation.isOrgUnitOfPublication f7be4eb9-d1d0-4081-859b-b15cee251456
relation.isOrgUnitOfPublication 82295b2b-0f85-4929-9659-075c93e82c48
File
Original bundle
Now showing 1 - 1 of 1
No Thumbnail Available
Name:
2016_McNicholl_AsymptoticDensity.pdf
Size:
239.95 KB
Format:
Adobe Portable Document Format
Description:
Collections