Mass Problems and Randomness

DOI10.2178/BSL/1107959497MaRDI QIDQ3370625zbMATHOpenAlexFDO

Authors Stephen G. Simpson

Publication date 8 February 2006

Published in The Bulletin of Symbolic Logic (Search for Journal in Brave)

Full work available at URL https://doi.org/10.2178/bsl/1107959497

zbMATH Keywords

degreeKolmogorov complexityrandomnessMedvedev latticemass problem

Mathematics Subject Classification ID

Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Recursively (computably) enumerable sets and degrees (03D25) Applications of computability and recursion theory (03D80) Other degrees and reducibilities in computability and recursion theory (03D30)

Recommendations

• Some fundamental issues concerning degrees of unsolvability
• Comparing the degrees of enumerability and the closed Medvedev degrees
• The upward closure of a perfect thin class
• scientific article; zbMATH DE number 1688364
• Mass problems and almost everywhere domination
• Randomness, computability, and density
• Degrees of randomized computability
• Randomness and reducibility
• MASS PROBLEMS AND HYPERARITHMETICITY
• Low upper bounds in the LR degrees

Cites work

• scientific article; zbMATH DE number 3861137 (Why is no real title available?)
• scientific article; zbMATH DE number 1226875 (Why is no real title available?)
• scientific article; zbMATH DE number 1010621 (Why is no real title available?)
• scientific article; zbMATH DE number 3291134 (Why is no real title available?)
• A classification of the ordinal recursive functions
• A splitting theorem for the Medvedev and Muchnik lattices
• Automorphisms of the lattice of \(\Pi_1^0\) classes; perfect thin classes and anc degrees
• Axiomatizable theories with few axiomatizable extensions
• Class groups of integral group rings
• Classical recursion theory. Vol. II
• Comparing DNR and WWKL
• Degrees of Unsolvability. (AM-55)
• Density of the Medvedev lattice of \(\Pi^0_1\) classes
• Embeddings into the Medvedev and Muchnik lattices of \(\Pi^0_1\) classes
• Located sets and reverse mathematics
• Lowness for the class of random sets
• Measure theory and weak König's lemma
• On relative randomness
• Recursively enumerable sets of positive integers and their decision problems
• The definition of random sequences
• Vitali's theorem and WWKL

Cited in

(45)

• Inside the Muchnik degrees. I: Discontinuity, learnability and constructivism
• Some fundamental issues concerning degrees of unsolvability
• Turing Degrees and Muchnik Degrees of Recursively Bounded DNR Functions
• A DNC function that computes no effectively bi-immune set
• MASS PROBLEMS AND HYPERARITHMETICITY
• Theory and Applications of Models of Computation
• The upward closure of a perfect thin class
• Randomness notions and reverse mathematics
• Comparing the Medvedev and Turing degrees of \(\Pi^{0}_{1}\) classes
• Mass problems and density
• The \(\forall \exists \)-theory of the effectively closed Medvedev degrees is decidable
• Intermediate logics and factors of the Medvedev lattice
• Mass problems and measure-theoretic regularity
• Mass problems associated with effectively closed sets
• Mass problems and initial segment complexity
• Computability of countable subshifts in one dimension
• Immunity for closed sets
• Inside the Muchnik degrees. II: The degree structures induced by the arithmetical hierarchy of countably continuous functions
• Relativized depth
• Highness properties close to PA completeness
• Effectively closed mass problems and intuitionism
• Classes of Polish spaces under effective Borel isomorphism
• Degrees of unsolvability: a tutorial
• Π₁⁰ classes with complex elements
• Degrees of difficulty of generalized r.e. separating classes
• Conservatively approximable functions
• The strength of the Besicovitch-Davies theorem
• A survey of Mučnik and Medvedev degrees
• choice classes
• Propagation of partial randomness
• Medvedev degrees of generalized r.e. separating classes
• Diagonally non-computable functions and bi-immunity
• On effectively closed sets of effective strong measure zero
• On the degree spectrum of a \(\Pi ^0_1\) class
• Deep \(\Pi_1^0\) classes
• Approximating Kolmogorov complexity
• Cone avoidance and randomness preservation
• On the structure of the Medvedev lattice
• Binary subtrees with few labeled paths
• Comparing the degrees of enumerability and the closed Medvedev degrees
• Muchnik degrees and cardinal characteristics
• Medvedev degrees of two-dimensional subshifts of finite type
• Effectively closed sets and enumerations
• Mass problems and almost everywhere domination
• Embedding \(\mathrm{FD}(\omega)\) into \({\mathcal{P}_s}\) densely

This page was built for publication: Mass Problems and Randomness

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3370625)