Asymptotic Density and the Theory of Computability: A partial survey
In this article we survey the development of generic and coarse computability and the main results on how classical asymptotic density interacts with the theory of computability.
Source author record
Carl G. Jockusch Jr.
Carl G. Jockusch Jr. appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.
ResearcherUnclaimed source record
Catalog footprint
What is connected
4works
2topics
4close collaborators
Research graph
See the researcher in context
Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.
Building this map preview
BZPEER is loading the nearby papers, people, topics and institutions for this page.
Published work
4 published item(s)
preprint2015arXiv
Coarse Reducibility and Algorithmic Randomness
A coarse description of a subset A of omega is a subset D of omega such that the symmetric difference of A and D has asymptotic density 0. We study the extent to which noncomputable information can be effectively recovered from all coarse descriptions of a given set A, especially when A is effectively random in some sense. We show that if A is 1-random and B is computable from every coarse description D of A, then B is K-trivial, which implies that if A is in fact weakly 2-random then B is computable. Our main tool is a kind of compactness theorem for cone-avoiding descriptions, which also allows us to prove the same result for 1-genericity in place of weak 2-randomness. In the other direction, we show that if A is a 1-random set which Turing-reduces to 0', then there is a noncomputable c.e. set computable from every coarse description of A, but that not all K-trivial sets are computable from every coarse description of some 1-random set. We study both uniform and nonuniform notions of coarse reducibility. A set Y is uniformly coarsely reducible to X if there is a Turing functional Phi such that if D is a coarse description of X, then Phi^D is a coarse description of Y. A set B is nonuniformly coarsely reducible to A if every coarse description of A computes a coarse description of B. We show that a certain natural embedding of the Turing degrees into the coarse degrees (both uniform and nonuniform) is not surjective. We also show that if two sets are mutually weakly 3-random, then their coarse degrees form a minimal pair, in both the uniform and nonuniform cases, but that the same is not true of every pair of relatively 2-random sets, at least in the nonuniform coarse degrees.
0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv
Asymptotic Density and Computably Enumerable Sets
We study connections between classical asymptotic density and c.e. sets. We prove that a c.e. Turing degree d is not low if and only if d contains a c.e. set A of density 1 which has no computable subsets of density 1, giving a natural characterization of non-low c.e. degrees. In contrast, we prove that every nonzero c.e. degree contains a set which is generically computable but not coarsely computable. There is a very close connection between the computational complexity of a set and the computational complexity of its density as a real number where we measure complexity of real numbers as the position of their left Dedekind cuts in the Arithmetic Hierarchy. We characterize the lower densities, upper densities and densities of both computable and computably enumerable sets. We also study "computable at density r" where r is an arbitrary real number in the unit interval. Finally, we study connections between density and classical smallness notions such as immunity and cohesiveness.
0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv
-Generic Computability, Turing Reducibility and Asymptotic Density
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.
0 citations0 reviewsNo code linkedOpen access