Degrees of Unsolvability: A Tutorial

DOI10.1007/978-3-319-20028-6_9zbMath1461.03036OpenAlexW1166748820MaRDI QIDQ3195683

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)

Related Items (8)

Mass problems and density ⋮ On the uniform computational content of computability theory ⋮ Turing Degrees and Muchnik Degrees of Recursively Bounded DNR Functions ⋮ On degree spectra of topological spaces ⋮ Unnamed Item ⋮ On Turing degrees of Walrasian models and a general impossibility result in the theory of decision-making ⋮ Degree spectra of structures ⋮ Weihrauch Complexity in Computable Analysis

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• 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
• Mass problems associated with effectively closed sets
• Recursive unsolvability of group theoretic problems
• Betti numbers of finitely presented groups and very rapidly growing functions.
• Mass problems and intuitionism
• Applications of sheaves. Proceedings of the research symposium on applications of sheaf theory to logic, algebra and analysis, Durham, July 9--21, 1977
• Zur Deutung der intuitionistischen Logik
• Einstein structures: Existence versus uniqueness
• The recursively enumerable degrees are dense
• Undecidability and nonperiodicity for tilings of the plane
• Degrees of members of \(\Pi_ 1^ 0\) classes
• The upper semi-lattice of degrees of recursive unsolvability
• MASS PROBLEMS AND INITIAL SEGMENT COMPLEXITY
• Mass problems and density
• Coding true arithmetic in the Medvedev and Muchnik degrees
• Kolmogorov complexity and the Recursion Theorem
• Degrees of models
• Mass Problems and Randomness
• MASS PROBLEMS AND HYPERARITHMETICITY
• Mass Problems and Measure-Theoretic Regularity
• Interpretability and Definability in the Recursively Enumerable Degrees
• A degree-theoretic definition of the ramified analytical hierarchy
• Hilbert's Tenth Problem is Unsolvable
• A splitting theorem for the Medvedev and Muchnik lattices
• Diagonally non-recursive functions and effective Hausdorff dimension
• An extension of the recursively enumerable Turing degrees
• Mass problems and almost everywhere domination
• Comparing DNR and WWKL
• FORCING WITH BUSHY TREES
• Medvedev degrees of two-dimensional subshifts of finite type
• Some undecidable problems involving elementary functions of a real variable
• The undecidability of the domino problem
• ∏ 0 1 Classes and Degrees of Theories
• Computability and Recursion
• On Computable Numbers, with an Application to the Entscheidungsproblem
• Recursively enumerable sets of positive integers and their decision problems

This page was built for publication: Degrees of Unsolvability: A Tutorial