Computing degrees of unsolvability

DOI10.1007/BF01342939zbMath0086.01101OpenAlexW2913148016MaRDI QIDQ770790

Hartley jun. Rogers

Publication date: 1959

Published in: Mathematische Annalen (Search for Journal in Brave)

Full work available at URL: https://eudml.org/doc/160704

zbMATH Keywords

philosophy and foundations of mathematics

Related Items

There exists a maximal 3-c.e. enumeration degree ⋮ Index sets and presentations of complexity classes ⋮ On the Degrees of Index Sets ⋮ Index sets related to prompt simplicity ⋮ The Kleene Hierarchy Classification of Recursively Random Sequences ⋮ Elementary Differences Between the Isols and the Co-Simple Isols ⋮ A discrete chain of degrees of index sets ⋮ Kleene index sets and functional m-degrees ⋮ Calculable enumerations and equivalence relations ⋮ Recursively enumerable sets and degrees ⋮ On index sets ⋮ The use of lists in the study of undecidable problems in automata theory ⋮ The index sets of m-degrees ⋮ Unnamed Item ⋮ Constructive Analogues of the Group of Permutations of the Natural Numbers

Cites Work

• Unnamed Item
• On degrees of recursive unsolvability
• The upper semi-lattice of degrees of recursive unsolvability
• Examples of sets definable by means of two and three quantifiers
• Degrees of Computability
• Arithmetical representation of recursively enumerable sets
• TWO RECURSIVELY ENUMERABLE SETS OF INCOMPARABLE DEGREES OF UNSOLVABILITY (SOLUTION OF POST'S PROBLEM, 1944)
• Gödel numberings of partial recursive functions
• Reducibility and Completeness for Sets of Integers
• On Computable Numbers, with an Application to the Entscheidungsproblem
• On definable sets of positive integers
• A Theorem on Hypersimple Sets
• Recursive Predicates and Quantifiers
• Recursively enumerable sets of positive integers and their decision problems
• Creative sets