Asymptotic density and the theory of computability: a partial survey

DOI10.1007/978-3-319-50062-1_30MaRDI QIDQ2970976zbMATH OpenOpenAlexFDO

Authors Carl G. jun. Jockusch, Paul E. Schupp

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

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

Abstract: 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.

Recommendations

• ASYMPTOTIC DENSITY AND COMPUTABLY ENUMERABLE SETS
• Generic computability, Turing degrees, and asymptotic density
• Asymptotic densities in number theory. I: A survey
• Asymptotic density and the Ershov hierarchy
• Asymptotic density and computability

Cites work

• scientific article; zbMATH DE number 5982274 (Why is no real title available?)
• scientific article; zbMATH DE number 706263 (Why is no real title available?)
• A unifying approach to the Gamma question
• A variant of a recursively unsolvable problem
• ASYMPTOTIC DENSITY AND COMPUTABLY ENUMERABLE SETS
• Algorithmic randomness and complexity.
• Algorithmically finite groups.
• Asymptotic density and the Ershov hierarchy
• Asymptotic density and the coarse computability bound
• Asymptotic density, computable traceability, and 1-randomness
• Average Case Complete Problems
• Average case completeness
• Coarse reducibility and algorithmic randomness
• Cogrowth of groups and simple random walks
• Computability and Randomness
• Computational randomness and lowness
• Density-1-bounding and quasiminimality in the generic degrees
• From bi-immunity to absolute undecidability
• Generic complexity of undecidable problems
• Generic computability, Turing degrees, and asymptotic density
• Generic-case complexity, decision problems in group theory, and random walks.
• Indifferent Sets
• Introduction to algorithms
• Nonexistence of minimal pairs for generic computability
• Notions of robust information coding
• Notions of weak genericity
• On a frequency solution to the problem of occurrence in a recursively enumerable set
• The degrees of bi‐immune sets
• The generic degrees of density-1 sets, and a characterization of the hyperarithmetic reals

Cited in

(7)

• Generically Computable abelian groups
• Generically and coarsely computable isomorphisms
• Computability theory. Abstracts from the workshop held April 25 -- May 1, 2021 (hybrid meeting)
• ASYMPTOTIC DENSITY AND COMPUTABLY ENUMERABLE SETS
• Asymptotic density and the coarse computability bound
• A minimal pair in the generic degrees
• Asymptotic density and computability

This page was built for publication: Asymptotic density and the theory of computability: a partial survey

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2970976)