-Generic Computability, Turing Reducibility and Asymptotic Density

Details -Generic Computability, Turing Reducibility and Asymptotic Density -Generic Computability, Turing Reducibility and Asymptotic Density

2010-10-25

arxiv.org/abs/1010.5212v1

Mathematics

Group Theory

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

-Generic Computability, Turing Reducibility and Asymptotic Density does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with -Generic Computability, Turing Reducibility and Asymptotic Density, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and -Generic Computability, Turing Reducibility and Asymptotic Density will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-94561