Asymptotic density and the theory of computability: a partial survey

DOI10.1007/978-3-319-50062-1_30zbMATH Open1485.03159arXiv1610.06504OpenAlexW2536989590MaRDI QIDQ2970976FDOQ2970976

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

Publication date: 4 April 2017

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

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.

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

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

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)

Cites Work

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

Cited In (7)

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

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)