Asymptotic Density and the Theory of Computability: A Partial Survey

DOI10.1007/978-3-319-50062-1_30zbMath1485.03159arXiv1610.06504OpenAlexW2536989590MaRDI QIDQ2970976

Paul E. Schupp, Carl G. jun. Jockusch

Publication date: 4 April 2017

Published in: Computability and Complexity (Search for Journal in Brave)

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

zbMATH Keywords

asymptotic densitygeneric-case complexitycoarse computabilitygeneric computability

Mathematics Subject Classification ID

Word problems, etc. in computability and recursion theory (03D40) Recursively (computably) enumerable sets and degrees (03D25) Other degrees and reducibilities in computability and recursion theory (03D30) Other Turing degree structures (03D28) Algorithmic randomness and dimension (03D32)

Related Items

Generically and coarsely computable isomorphisms, A MINIMAL PAIR IN THE GENERIC DEGREES, Generically Computable abelian groups, Computability theory. Abstracts from the workshop held April 25 -- May 1, 2021 (hybrid meeting), Asymptotic density and computability

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Algorithmically finite groups.
• Cogrowth of groups and simple random walks
• Average case completeness
• On a frequency solution to the problem of occurrence in a recursively enumerable set
• Generic-case complexity, decision problems in group theory, and random walks.
• Computational randomness and lowness
• THE GENERIC DEGREES OF DENSITY-1 SETS, AND A CHARACTERIZATION OF THE HYPERARITHMETIC REALS
• Asymptotic density and the coarse computability bound
• Generic computability, Turing degrees, and asymptotic density
• COARSE REDUCIBILITY AND ALGORITHMIC RANDOMNESS
• Algorithmic Randomness and Complexity
• Asymptotic density, computable traceability, and 1-randomness
• Notions of weak genericity
• Generic complexity of undecidable problems
• Indifferent Sets
• Average Case Complete Problems
• A Unifying Approach to the Gamma Question
• Asymptotic density and the Ershov hierarchy
• Notions of robust information coding
• Nonexistence of minimal pairs for generic computability
• DENSITY-1-BOUNDING AND QUASIMINIMALITY IN THE GENERIC DEGREES
• Computability and Randomness
• ASYMPTOTIC DENSITY AND COMPUTABLY ENUMERABLE SETS
• From Bi-Immunity to Absolute Undecidability
• The degrees of bi‐immune sets
• A variant of a recursively unsolvable problem