Asymptotic density and computability

DOI10.3103/S1066369X21100017zbMath1496.03168OpenAlexW3216082958MaRDI QIDQ2066410

I. I. Batyrshin

Publication date: 14 January 2022

Published in: Russian Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.3103/s1066369x21100017

zbMATH Keywords

asymptotic densityTuring degreesgeneric complexitybi-immune setweakly 1-generic set

Mathematics Subject Classification ID

Recursively (computably) enumerable sets and degrees (03D25) Other degrees and reducibilities in computability and recursion theory (03D30) Other Turing degree structures (03D28)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The gamma question for many-one degrees
• A small simplification in hyperbolic groups
• Generic-case complexity, decision problems in group theory, and random walks.
• On a hierarchy of sets. III
• 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
• Asymptotic Density and the Theory of Computability: A Partial Survey
• COARSE REDUCIBILITY AND ALGORITHMIC RANDOMNESS
• Asymptotic density, computable traceability, and 1-randomness
• Asymptotic density, immunity and randomness
• Notions of weak genericity
• Generic complexity of undecidable problems
• Smoothed analysis of algorithms
• Average Case Complete Problems
• ALMOST EVERY GROUP IS HYPERBOLIC
• A Unifying Approach to the Gamma Question
• Reducibility among Combinatorial Problems
• A MINIMAL PAIR IN THE GENERIC DEGREES
• An answer to the Gamma question
• Dense computability, upper cones, and minimal pairs
• 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
• ASYMPTOTIC DENSITY AND COMPUTABLY ENUMERABLE SETS
• From Bi-Immunity to Absolute Undecidability
• The complexity of theorem-proving procedures
• The word problem

This page was built for publication: Asymptotic density and computability