Degrees of unsolvability: a tutorial

DOI10.1007/978-3-319-20028-6_9MaRDI QIDQ3195683zbMATH OpenOpenAlexFDO

Authors Stephen G. Simpson

Publication date 20 October 2015

Published in Evolving Computability (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-319-20028-6_9

Mathematics Subject Classification ID

Other degrees and reducibilities in computability and recursion theory (03D30)

Recommendations

• Mass problems associated with effectively closed sets
• Effectively closed mass problems and intuitionism
• Some fundamental issues concerning degrees of unsolvability
• scientific article; zbMATH DE number 3861137
• scientific article; zbMATH DE number 3914306

Cites work

• A degree-theoretic definition of the ramified analytical hierarchy
• A framework for priority arguments
• A splitting theorem for the Medvedev and Muchnik lattices
• An extension of the recursively enumerable Turing degrees
• Applications of sheaves. Proceedings of the research symposium on applications of sheaf theory to logic, algebra and analysis, Durham, July 9--21, 1977
• Betti numbers of finitely presented groups and very rapidly growing functions.
• Coding true arithmetic in the Medvedev and Muchnik degrees
• Comparing DNR and WWKL
• Computability and Recursion
• Degrees of members of \(\Pi_ 1^ 0\) classes
• Degrees of models
• Diagonally non-recursive functions and effective Hausdorff dimension
• 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
• Forcing with bushy trees
• Hilbert's Tenth Problem is Unsolvable
• scientific article; zbMATH DE number 3645093 (Why is no real title available?)
• scientific article; zbMATH DE number 3861137 (Why is no real title available?)
• scientific article; zbMATH DE number 4135927 (Why is no real title available?)
• scientific article; zbMATH DE number 5504384 (Why is no real title available?)
• scientific article; zbMATH DE number 3784869 (Why is no real title available?)
• scientific article; zbMATH DE number 1226875 (Why is no real title available?)
• scientific article; zbMATH DE number 3250567 (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 3387326 (Why is no real title available?)
• scientific article; zbMATH DE number 3110190 (Why is no real title available?)
• Interpretability and Definability in the Recursively Enumerable Degrees
• Intuitionistic logic and Muchnik degrees
• Mass problems and almost everywhere domination
• Mass problems and density
• MASS PROBLEMS AND HYPERARITHMETICITY
• Mass problems and initial segment complexity
• Mass problems and intuitionism
• Mass problems and measure-theoretic regularity
• Mass Problems and Randomness
• Mass problems associated with effectively closed sets
• Medvedev degrees of two-dimensional subshifts of finite type
• On Computable Numbers, with an Application to the Entscheidungsproblem
• Recursive unsolvability of group theoretic problems
• Recursively enumerable sets of positive integers and their decision problems
• Some undecidable problems involving elementary functions of a real variable
• The recursively enumerable degrees are dense
• The undecidability of the domino problem
• The upper semi-lattice of degrees of recursive unsolvability
• Undecidability and nonperiodicity for tilings of the plane
• Zur Deutung der intuitionistischen Logik
• ∏ 0 1 Classes and Degrees of Theories

Cited in

(15)

• On Turing degrees of Walrasian models and a general impossibility result in the theory of decision-making
• The rhombus classes of degrees of unsolvability. I. The jump properties
• On the uniform computational content of computability theory
• Degree spectra of structures
• On degree spectra of topological spaces
• Mass problems and intuitionistic higher-order logic
• Mass problems and density
• Turing Degrees and Muchnik Degrees of Recursively Bounded DNR Functions
• Some fundamental issues concerning degrees of unsolvability
• scientific article; zbMATH DE number 3926899 (Why is no real title available?)
• scientific article; zbMATH DE number 512805 (Why is no real title available?)
• The information content of typical reals
• Weihrauch Complexity in Computable Analysis
• Stashing and parallelization pentagons
• Mass problems associated with effectively closed sets

This page was built for publication: Degrees of unsolvability: a tutorial

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