Mass problems associated with effectively closed sets

DOI10.2748/TMJ/1325886278zbMATH Open1246.03064OpenAlexW2157282589MaRDI QIDQ765664FDOQ765664

Authors: 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

Recommendations

• Mass problems and density
• Effectively closed mass problems and intuitionism
• Degrees of unsolvability: a tutorial
• Mass problems and intuitionism
• Some fundamental issues concerning degrees of unsolvability

zbMATH Keywords

proof theoryKolmogorov complexityalgorithmic randomnessintuitionismMuchnik degreesmass problemsdegrees of unsolvabilityrecursively enumerable degreeshyperarithmetical hierarchyresource-bounded computational complexityunsolvable problems

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (24)

• Pathwise-randomness and models of second-order arithmetic
• Turing degrees of multidimensional SFTs
• Inside the Muchnik degrees. II: The degree structures induced by the arithmetical hierarchy of countably continuous functions
• Medvedev degrees of two-dimensional subshifts of finite type
• Effectively closed mass problems and intuitionism
• Coding true arithmetic in the Medvedev degrees of \(\Pi^0_1\) classes
• Computability of Subsets of Metric Spaces
• Computability in Symbolic Dynamics
• Deep \(\Pi_1^0\) classes
• $\it \Pi^0_1$ Sets and Tilings
• On effectively closed sets of effective strong measure zero
• Randomness, computation and mathematics
• Randomness notions and reverse mathematics
• Mass problems and density
• Inside the Muchnik degrees. I: Discontinuity, learnability and constructivism
• Mass problems and intuitionistic higher-order logic
• Title not available (Why is that?)
• Cone avoidance and randomness preservation
• Comparing the Medvedev and Turing degrees of \(\Pi^{0}_{1}\) classes
• Some fundamental issues concerning degrees of unsolvability
• Turing Degrees and Muchnik Degrees of Recursively Bounded DNR Functions
• Degrees of unsolvability: a tutorial
• Propagation of partial randomness
• Diagonally non-computable functions and fireworks

This page was built for publication: Mass problems associated with effectively closed sets

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