Asymptotic density, immunity and randomness

DOI10.3233/COM-150040zbMath1337.03059arXiv1405.0022OpenAlexW3100765960MaRDI QIDQ3195648

Eric P. Astor

Publication date: 20 October 2015

Published in: Computability (Search for Journal in Brave)

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

zbMATH Keywords

asymptotic densityimmunityRice's theoremgeneric computabilityintrinsic density

Mathematics Subject Classification ID

Recursively (computably) enumerable sets and degrees (03D25) Other Turing degree structures (03D28) Algorithmic randomness and dimension (03D32)

Related Items (6)

Intermediate intrinsic density and randomness ⋮ THE COMPUTATIONAL CONTENT OF INTRINSIC DENSITY ⋮ COARSE REDUCIBILITY AND ALGORITHMIC RANDOMNESS ⋮ INTRINSIC SMALLNESS ⋮ Asymptotic density and computability ⋮ Degrees of sets having no subsets of higher m- and t t-degree

Cites Work

• Unnamed Item
• On the strongly generic undecidability of the halting problem
• Average case completeness
• Generic-case complexity, decision problems in group theory, and random walks.
• The halting problem is decidable on a set of asymptotic probability one
• Generic computability, Turing degrees, and asymptotic density
• Randomness and Computability: Open Questions
• Smoothed analysis of algorithms
• Average Case Complete Problems
• A cohesive set which is not high
• Jump equivalence of the Δ₂⁰ hyperimmune sets
• The axiomatization of randomness
• Asymptotic density and the Ershov hierarchy
• Nonexistence of minimal pairs for generic computability
• From Bi-Immunity to Absolute Undecidability
• Classes of Recursively Enumerable Sets and Their Decision Problems
• Recursively enumerable sets of positive integers and their decision problems
• Creative sets

This page was built for publication: Asymptotic density, immunity and randomness