Mass problems associated with effectively closed sets
algorithmic randomnessdegrees of unsolvabilityhyperarithmetical hierarchyintuitionismKolmogorov complexitymass problemsMuchnik degreesproof theoryrecursively enumerable degreesresource-bounded computational complexityunsolvable problems
Recursively (computably) enumerable sets and degrees (03D25) Other Turing degree structures (03D28) Other degrees and reducibilities in computability and recursion theory (03D30) Algorithmic randomness and dimension (03D32) Hierarchies of computability and definability (03D55) Symbolic dynamics (37B10)
In the paper recent investigations into the lattice of Muchnik degrees of nonempty effectively closed sets in Euclidean space \({\mathcal E}_{w}\) are summerized. In particular it is shown that \({\mathcal E}_{w}\) provides an elegant and useful framework for the classification of certain foundationally interesting problems which are algorithmically unsolvable. Some specific degrees in \({\mathcal E}_{w}\) which are associated with such problems are exhibited. Additionally, some structural results concerning the lattice \({\mathcal E}_{w}\) are presented. One of them gives an answer to a question which arises naturally from the Kolmogorov non-rigorous 1932 interpretation of intuitionism as a calculus of problems. It is also shown how \({\mathcal E}_{w}\) can be applied in symbolic dynamics toward the classification of tiling problems and \({\mathbb Z}^{d}\)-subshifts of finite type.
- 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 extension of the recursively enumerable Turing degrees
- An Introduction to Symbolic Dynamics and Coding
- Automorphisms of the lattice of _1⁰ 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 ^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
- scientific article; zbMATH DE number 4135927 (Why is no real title available?)
- scientific article; zbMATH DE number 5380239 (Why is no real title available?)
- scientific article; zbMATH DE number 3924748 (Why is no real title available?)
- scientific article; zbMATH DE number 4008384 (Why is no real title available?)
- scientific article; zbMATH DE number 4068856 (Why is no real title available?)
- scientific article; zbMATH DE number 4091484 (Why is no real title available?)
- scientific article; zbMATH DE number 3695455 (Why is no real title available?)
- scientific article; zbMATH DE number 3784869 (Why is no real title available?)
- scientific article; zbMATH DE number 194101 (Why is no real title available?)
- scientific article; zbMATH DE number 3577197 (Why is no real title available?)
- scientific article; zbMATH DE number 1226875 (Why is no real title available?)
- scientific article; zbMATH DE number 722611 (Why is no real title available?)
- scientific article; zbMATH DE number 1994007 (Why is no real title available?)
- scientific article; zbMATH DE number 194916 (Why is no real title available?)
- scientific article; zbMATH DE number 5791092 (Why is no real title available?)
- scientific article; zbMATH DE number 3245483 (Why is no real title available?)
- scientific article; zbMATH DE number 3291134 (Why is no real title available?)
- scientific article; zbMATH DE number 3304988 (Why is no real title available?)
- scientific article; zbMATH DE number 3316918 (Why is no real title available?)
- scientific article; zbMATH DE number 3329894 (Why is no real title available?)
- scientific article; zbMATH DE number 2236645 (Why is no real title available?)
- scientific article; zbMATH DE number 3050845 (Why is no real title available?)
- scientific article; zbMATH DE number 3103212 (Why is no real title available?)
- 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 almost everywhere domination
- MASS PROBLEMS AND HYPERARITHMETICITY
- Mass problems and initial segment complexity
- Mass problems and intuitionism
- Mass problems and measure-theoretic regularity
- Mass Problems and Randomness
- Measure theory and weak König's lemma
- Medvedev degrees of two-dimensional subshifts of finite type
- Nonrecursive tilings of the plane. II
- On a conjecture of Dobrinen and Simpson concerning almost everywhere domination
- On Computable Numbers, with an Application to the Entscheidungsproblem
- On the degree spectrum of a ^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 definition of random sequences
- The Gödel hierarchy and reverse mathematics
- 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
- Π10 classes with complex elements
- ∏ 0 1 Classes and Degrees of Theories
- Cone avoidance and randomness preservation
- 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
- Inside the Muchnik degrees. I: Discontinuity, learnability and constructivism
- Mass problems and intuitionistic higher-order logic
- Randomness, computation and mathematics
- Mass problems and density
- Turing Degrees and Muchnik Degrees of Recursively Bounded DNR Functions
- \it \Pi^0_1 Sets and Tilings
- Computability in Symbolic Dynamics
- Degrees of unsolvability: a tutorial
- Some fundamental issues concerning degrees of unsolvability
- Propagation of partial randomness
- Turing degrees of multidimensional SFTs
- Effectively closed mass problems and intuitionism
- Coding true arithmetic in the Medvedev degrees of ^0_1 classes
- Computability of Subsets of Metric Spaces
- A characterization of subshifts with computable language
- Randomness notions and reverse mathematics
- Diagonally non-computable functions and fireworks
- Deep _1⁰ classes
- Medvedev degrees of two-dimensional subshifts of finite type
- Comparing the Medvedev and Turing degrees of \(\Pi^{0}_{1}\) classes
- Pathwise-randomness and models of second-order arithmetic
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)
