preprint · arXiv (Cornell University) · 2010

-Generic Computability, Turing Reducibility and Asymptotic Density

Jockusch, Carl G., Schupp, Paul E.

Cited by 0Open access

Abstract

Generic computability has been studied in group theory and we now study it in the context of classical computability theory. A set A of natural numbers is generically computable if there is a partial computable function f whose domain has density 1 and which agrees with the characteristic function of A on its domain. A set A is coarsely computable if there is a computable set C such that the symmetric difference of A and C has density 0. We prove that there is a c.e. set which is generically computable but not coarsely computable and vice versa. We show that every nonzero Turing degree contains a set which is not coarsely computable. We prove that there is a c.e. set of density 1 which has no computable subset of density 1. As a corollary, there is a generically computable set A such that no generic algorithm for A has computable domain. We define a general notion of generic reducibility in the spirt of Turing reducibility and show that there is a natural order-preserving embedding of the Turing degrees into the generic degrees which is not surjective.

Cite this paper

APA 7

Jockusch, C. G., & Schupp, P. E. (2010). -Generic Computability, Turing Reducibility and Asymptotic Density. arXiv (Cornell University). https://doi.org/10.48550/arxiv.1010.5212

MLA 9

Jockusch, Carl G., and Paul E. Schupp. “-Generic Computability, Turing Reducibility and Asymptotic Density.” arXiv (Cornell University), 2010, https://doi.org/10.48550/arxiv.1010.5212.

Chicago

Jockusch, Carl G., and Paul E. Schupp. 2010. “-Generic Computability, Turing Reducibility and Asymptotic Density.” arXiv (Cornell University). https://doi.org/10.48550/arxiv.1010.5212.

Harvard

Jockusch, C.G. and Schupp, P.E. (2010) ‘-Generic Computability, Turing Reducibility and Asymptotic Density’, arXiv (Cornell University). Available at: https://doi.org/10.48550/arxiv.1010.5212.

BibTeX

@misc{jockusch2010generic,
  title = {{-Generic Computability, Turing Reducibility and Asymptotic Density}},
  author = {Jockusch, Carl G. and Schupp, Paul E.},
  journal = {arXiv (Cornell University)},
  year = {2010},
  doi = {10.48550/arxiv.1010.5212}
}

Made from the index record. Check names, capitalisation and page numbers against the paper. Need another style? AI for Research has over 10,000.