Mass Problems and Randomness
From MaRDI portal
Publication:3370625
DOI10.2178/bsl/1107959497zbMath1090.03015OpenAlexW2135114591MaRDI QIDQ3370625
Publication date: 8 February 2006
Published in: Bulletin of Symbolic Logic (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.2178/bsl/1107959497
Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Applications of computability and recursion theory (03D80) Recursively (computably) enumerable sets and degrees (03D25) Other degrees and reducibilities in computability and recursion theory (03D30)
Related Items
A Survey of Mučnik and Medvedev Degrees, Conservatively Approximable Functions, Inside the Muchnik degrees. I: Discontinuity, learnability and constructivism, MASS PROBLEMS AND INITIAL SEGMENT COMPLEXITY, Degrees of Unsolvability: A Tutorial, The \(\forall \exists \)-theory of the effectively closed Medvedev degrees is decidable, Propagation of partial randomness, DEEP CLASSES, Approximating Kolmogorov complexity, On the structure of the Medvedev lattice, Effectively closed mass problems and intuitionism, RANDOMNESS NOTIONS AND REVERSE MATHEMATICS, choice classes, Relativized depth, Classes of Polish spaces under effective Borel isomorphism, Turing Degrees and Muchnik Degrees of Recursively Bounded DNR Functions, MASS PROBLEMS AND HYPERARITHMETICITY, Inside the Muchnik degrees. II: The degree structures induced by the arithmetical hierarchy of countably continuous functions, Binary subtrees with few labeled paths, Degrees of difficulty of generalized r.e. separating classes, Embedding \(\mathrm{FD}(\omega)\) into \({\mathcal{P}_s}\) densely, Effectively closed sets and enumerations, On effectively closed sets of effective strong measure zero, A DNC function that computes no effectively bi-immune set, Intermediate logics and factors of the Medvedev lattice, The upward closure of a perfect thin class, Medvedev degrees of two-dimensional subshifts of finite type, Immunity for Closed Sets, Computability of countable subshifts in one dimension, Medvedev Degrees of Generalized R.E. separating Classes, Comparing the Medvedev and Turing degrees of Π01 classes, On the degree spectrum of a $\Pi ^0_1$ class, Highness properties close to PA completeness, Comparing the degrees of enumerability and the closed Medvedev degrees, Mass problems associated with effectively closed sets, Π10 classes with complex elements, Cone avoidance and randomness preservation, Diagonally Non-Computable Functions and Bi-Immunity
Cites Work
- On relative randomness
- Embeddings into the Medvedev and Muchnik lattices of \(\Pi^0_1\) classes
- Classical recursion theory. Vol. II
- Vitali's theorem and WWKL
- Density of the Medvedev lattice of \(\Pi^0_1\) classes
- Measure theory and weak König's lemma
- Automorphisms of the lattice of $\Pi _1^0$ classes; perfect thin classes and anc degrees
- A splitting theorem for the Medvedev and Muchnik lattices
- Located sets and reverse mathematics
- Lowness for the class of random sets
- Comparing DNR and WWKL
- Degrees of Unsolvability. (AM-55)
- Axiomatizable theories with few axiomatizable extensions
- A classification of the ordinal recursive functions
- The definition of random sequences
- Class groups of integral group rings
- Recursively enumerable sets of positive integers and their decision problems
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
