Asymptotic density, immunity and randomness
From MaRDI portal
Publication:3195648
DOI10.3233/COM-150040zbMath1337.03059arXiv1405.0022OpenAlexW3100765960MaRDI QIDQ3195648
Publication date: 20 October 2015
Published in: Computability (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1405.0022
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 Δ20 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
