Mass Problems and Randomness

DOI10.2178/BSL/1107959497zbMATH Open1090.03015OpenAlexW2135114591MaRDI QIDQ3370625FDOQ3370625

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

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
• Publication:2762505
• 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

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)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• The definition of random sequences
• Classical recursion theory. Vol. II
• Measure theory and weak König's lemma
• Title not available (Why is that?)
• A classification of the ordinal recursive functions
• Lowness for the class of random sets
• Title not available (Why is that?)
• Comparing DNR and WWKL
• Recursively enumerable sets of positive integers and their decision problems
• Density of the Medvedev lattice of \(\Pi^0_1\) classes
• A splitting theorem for the Medvedev and Muchnik lattices
• Located sets and reverse mathematics
• Embeddings into the Medvedev and Muchnik lattices of \(\Pi^0_1\) classes
• Degrees of Unsolvability. (AM-55)
• On relative randomness
• Vitali's theorem and WWKL
• 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

Cited In (43)

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

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)