Mass problems associated with effectively closed sets

DOI10.2748/tmj/1325886278zbMath1246.03064OpenAlexW2157282589MaRDI QIDQ765664

Stephen G. Simpson

Publication date: 21 March 2012

Published in: Tôhoku Mathematical Journal. Second Series (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.2748/tmj/1325886278

zbMATH Keywords

Kolmogorov complexityproof theoryalgorithmic randomnessintuitionismMuchnik degreesmass problemsdegrees of unsolvabilityrecursively enumerable degreeshyperarithmetical hierarchyresource-bounded computational complexityunsolvable problems

Mathematics Subject Classification ID

Symbolic dynamics (37B10) Recursively (computably) enumerable sets and degrees (03D25) Other degrees and reducibilities in computability and recursion theory (03D30) Other Turing degree structures (03D28) Algorithmic randomness and dimension (03D32) Hierarchies of computability and definability (03D55)

Related Items

Randomness, Computation and Mathematics, Inside the Muchnik degrees. I: Discontinuity, learnability and constructivism, Computability in Symbolic Dynamics, Degrees of Unsolvability: A Tutorial, Propagation of partial randomness, Turing degrees of multidimensional SFTs, DEEP CLASSES, Coding true arithmetic in the Medvedev degrees of \(\Pi^0_1\) classes, RANDOMNESS NOTIONS AND REVERSE MATHEMATICS, Turing Degrees and Muchnik Degrees of Recursively Bounded DNR Functions, Inside the Muchnik degrees. II: The degree structures induced by the arithmetical hierarchy of countably continuous functions, On effectively closed sets of effective strong measure zero, $\it \Pi^0_1$ Sets and Tilings, Diagonally non-computable functions and fireworks, Medvedev degrees of two-dimensional subshifts of finite type, Comparing the Medvedev and Turing degrees of Π⁰₁ classes, Unnamed Item, Mass problems and intuitionistic higher-order logic, Cone avoidance and randomness preservation, Computability of Subsets of Metric Spaces

Cites Work

• Intuitionistic logic and Muchnik degrees
• Fixed-point tile sets and their applications
• Extracting information is hard: a Turing degree of non-integral effective Hausdorff dimension
• Embeddings into the Medvedev and Muchnik lattices of \(\Pi^0_1\) classes
• Recursive unsolvability of group theoretic problems
• Betti numbers of finitely presented groups and very rapidly growing functions.
• Mass problems and intuitionism
• A characterization of the entropies of multidimensional shifts of finite type
• Recursion theory week. Proceedings of a Conference held in Oberwolfach, West Germany, April 15-21, 1984
• Proof theory. 2nd ed
• Descriptive set theory
• Constructivism in mathematics. An introduction. Volume II
• Sheaves in geometry and logic: a first introduction to topos theory
• Vitali's theorem and WWKL
• Zur Deutung der intuitionistischen Logik
• Defining the Turing jump
• Tilings, substitution systems and dynamical systems generated by them
• Einstein structures: Existence versus uniqueness
• Hyperimmunity in \(2^{\mathbb N}\)
• Small \(\Pi^{0}_{1}\) classes
• The recursively enumerable degrees are dense
• Undecidability and nonperiodicity for tilings of the plane
• Degrees of members of \(\Pi_ 1^ 0\) classes
• Lowness properties and randomness
• Measure theory and weak König's lemma
• Undecidable theories
• The upper semi-lattice of degrees of recursive unsolvability
• Automorphisms of the lattice of $\Pi _1^0$ classes; perfect thin classes and anc degrees
• Randomness for non-computable measures
• Lowness notions, measure and domination
• MASS PROBLEMS AND INITIAL SEGMENT COMPLEXITY
• On the degree spectrum of a $\Pi ^0_1$ class
• Kolmogorov complexity and the Recursion Theorem
• Algorithmic Randomness and Complexity
• Mass Problems and Randomness
• Invariance in ℰ* and ℰ_{Π}
• Uniform almost everywhere domination
• MASS PROBLEMS AND HYPERARITHMETICITY
• A fixed-point-free minimal degree
• Mass Problems and Measure-Theoretic Regularity
• Pseudo Jump Operators. I: The R. E. Case
• Degrees joining to 0′
• Pseudo-jump operators. II: Transfinite iterations, hierarchies and minimal covers
• Interpretability and Definability in the Recursively Enumerable Degrees
• Nonrecursive tilings of the plane. II
• A degree-theoretic definition of the ramified analytical hierarchy
• Descending sequences of degrees
• Hilbert's Tenth Problem is Unsolvable
• A splitting theorem for the Medvedev and Muchnik lattices
• Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme I
• An Introduction to Symbolic Dynamics and Coding
• An extension of the recursively enumerable Turing degrees
• Almost everywhere domination and superhighness
• Mass problems and almost everywhere domination
• Low for random reals and positive-measure domination
• Almost everywhere domination
• Comparing DNR and WWKL
• Medvedev degrees of two-dimensional subshifts of finite type
• On a conjecture of Dobrinen and Simpson concerning almost everywhere domination
• Π₁⁰ classes with complex elements
• Deduction-preserving "Recursive Isomorphisms" between theories
• Some undecidable problems involving elementary functions of a real variable
• The undecidability of the domino problem
• A classification of the ordinal recursive functions
• The definition of random sequences
• ∏ 0 1 Classes and Degrees of Theories
• On Computable Numbers, with an Application to the Entscheidungsproblem
• Theory and Applications of Models of Computation
• Computational Complexity
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item