Degrees of Unsolvability: A Tutorial

DOI10.1007/978-3-319-20028-6_9zbMath1461.03036MaRDI 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

03D30: Other degrees and reducibilities in computability and recursion theory

Related Items

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

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