Generic computability, Turing degrees, and asymptotic density

DOI10.1112/JLMS/JDR051zbMath1247.03076arXiv1010.5212OpenAlexW3091923320MaRDI QIDQ2880398

Carl G. jun. Jockusch, Paul E. Schupp

Publication date: 13 April 2012

Published in: Journal of the London Mathematical Society (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1010.5212

zbMATH Keywords

asymptotic densitycomputability theoryTuring degreecoarse computabilitygeneric decidability

Mathematics Subject Classification ID

Recursively (computably) enumerable sets and degrees (03D25) Other Turing degree structures (03D28)

Related Items (33)

Intermediate intrinsic density and randomness ⋮ A generic relation on recursively enumerable sets ⋮ Notions of robust information coding ⋮ Asymptotic density, computable traceability, and 1-randomness ⋮ Nonexistence of minimal pairs for generic computability ⋮ Generically and coarsely computable isomorphisms ⋮ Generic complexity of the membership problem for semigroups of integer matrices ⋮ Computability theory. Abstracts from the workshop held February 5--11, 2012. ⋮ Asymptotic density, immunity and randomness ⋮ Følner functions and the generic word problem for finitely generated amenable groups ⋮ THE COMPUTATIONAL CONTENT OF INTRINSIC DENSITY ⋮ Dimension 1 sequences are close to randoms ⋮ A NOTE ON THE LEARNING-THEORETIC CHARACTERIZATIONS OF RANDOMNESS AND CONVERGENCE ⋮ Approximating Kolmogorov complexity ⋮ A MINIMAL PAIR IN THE GENERIC DEGREES ⋮ Generically Computable abelian groups ⋮ DENSITY-1-BOUNDING AND QUASIMINIMALITY IN THE GENERIC DEGREES ⋮ Computability theory. Abstracts from the workshop held April 25 -- May 1, 2021 (hybrid meeting) ⋮ Asymptotic Density and the Theory of Computability: A Partial Survey ⋮ Absolutely no free lunches! ⋮ Some Questions in Computable Mathematics ⋮ COARSE REDUCIBILITY AND ALGORITHMIC RANDOMNESS ⋮ Generic amplification of recursively enumerable sets ⋮ ASYMPTOTIC DENSITY AND COMPUTABLY ENUMERABLE SETS ⋮ Computing sets from all infinite subsets ⋮ INTRINSIC SMALLNESS ⋮ The gamma question for many-one degrees ⋮ THE GENERIC DEGREES OF DENSITY-1 SETS, AND A CHARACTERIZATION OF THE HYPERARITHMETIC REALS ⋮ Asymptotic density and the coarse computability bound ⋮ Generic case completeness ⋮ Asymptotic density and computability ⋮ Asymptotic density and the Ershov hierarchy ⋮ Effectivizing Lusin’s Theorem

This page was built for publication: Generic computability, Turing degrees, and asymptotic density