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

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

Cited In (23)

• Pathwise-randomness and models of second-order arithmetic
• Turing degrees of multidimensional SFTs
• RANDOMNESS NOTIONS AND REVERSE MATHEMATICS
• 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
• Degrees of Unsolvability: A Tutorial
• $\it \Pi^0_1$ Sets and Tilings
• On effectively closed sets of effective strong measure zero
• Inside the Muchnik degrees. I: Discontinuity, learnability and constructivism
• Comparing the Medvedev and Turing degrees of Π⁰₁ classes
• Randomness, Computation and Mathematics
• Mass problems and intuitionistic higher-order logic
• Title not available (Why is that?)
• Cone avoidance and randomness preservation
• Some fundamental issues concerning degrees of unsolvability
• Turing Degrees and Muchnik Degrees of Recursively Bounded DNR Functions
• DEEP CLASSES
• 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)