On degrees of unsolvability

DOI10.2307/1970028zbMath0119.25105OpenAlexW2057392475MaRDI QIDQ2626398

J. R. Shoenfield

Publication date: 1959

Published in: Annals of Mathematics. Second Series (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.2307/1970028

zbMATH Keywords

mathematical logic

Related Items (74)

Recursion and topology on \(2^{\leq\omega}\) for possibly infinite computations ⋮ On the sizes of DPDAs, PDAs, LBAs ⋮ The degrees of hyperhyperimmune sets ⋮ Real numbers and functions in the Kleene hierarchy and limits of recursive, rational functions ⋮ Algebraic simulations ⋮ THE n-r.e. DEGREES: UNDECIDABILITY AND Σ₁ SUBSTRUCTURES ⋮ Inside the Muchnik degrees. I: Discontinuity, learnability and constructivism ⋮ Jumps of quasi-minimal enumeration degrees ⋮ Lower bounds on degrees of game-theoretic structures ⋮ THE STRENGTH OF RAMSEY’S THEOREM FOR COLORING RELATIVELY LARGE SETS ⋮ Infinitary self-reference in learning theory ⋮ A non-inversion theorem for the jump operator ⋮ Dominating the Erdős-Moser theorem in reverse mathematics ⋮ Degree theory on \(\aleph_\omega\) ⋮ Machine learning of higher-order programs ⋮ Reflection in membership equational logic, many-sorted equational logic, Horn logic with equality, and rewriting logic ⋮ Recursively enumerable sets which are uniform for finite extensions ⋮ OPEN QUESTIONS ABOUT RAMSEY-TYPE STATEMENTS IN REVERSE MATHEMATICS ⋮ New barriers in complexity theory: on the solvability complexity index and the towers of algorithms ⋮ SELF-REFERENCE UPFRONT: A STUDY OF SELF-REFERENTIAL GÖDEL NUMBERINGS ⋮ Antibasis theorems for \({\Pi^0_1}\) classes and the jump hierarchy ⋮ The enumeration degrees: Local and global structural interactions ⋮ Computable elements and functions in effectively enumerable topological spaces ⋮ Fixed-parameter decidability: Extending parameterized complexity analysis ⋮ \(\mu\)-recursion and infinite limits. ⋮ Superefficiency from the vantage point of computability ⋮ Several results in program size complexity ⋮ Extending and interpreting Post's programme ⋮ Generalization of Shapiro's theorem to higher arities and noninjective notations ⋮ Ramsey's theorem and recursion theory ⋮ THE STRENGTH OF THE TREE THEOREM FOR PAIRS IN REVERSE MATHEMATICS ⋮ A minimal degree less than 0’ ⋮ Degrees of models ⋮ A bounded jump for the bounded Turing degrees ⋮ A basis theorem for Π₁⁰ classes of positive measure and jump inversion for random reals ⋮ Domination, forcing, array nonrecursiveness and relative recursive enumerability ⋮ Anomalous learning helps succinctness ⋮ The weakness of being cohesive, thin or free in reverse mathematics ⋮ Jump inversions inside effectively closed sets and applications to randomness ⋮ On Turing degrees of Walrasian models and a general impossibility result in the theory of decision-making ⋮ On degrees of unsolvability and complexity properties ⋮ The Halting Problem Relativized to Complements ⋮ Structures of Some Strong Reducibilities ⋮ RECOGNIZING STRONG RANDOM REALS ⋮ C-quasi-minimal enumeration degrees below \(\mathbf c'\) ⋮ Forcing and reducibilities ⋮ Kolmogorov complexity for possibly infinite computations ⋮ Function operators spanning the arithmetical and the polynomial hierarchy ⋮ Upper semi-lattice of binary strings with the relation ``\(x\) is simple conditional to \(y\) ⋮ The distribution of properly Σ₂⁰ e-degrees ⋮ Unnamed Item ⋮ Putnam’s Theorem on the Complexity of Models ⋮ On the First Order Theory of the Arithmetical Degrees ⋮ Recursive Enumerability and the Jump Operator ⋮ Thin set theorems and cone avoidance ⋮ Recursively enumerable sets and degrees ⋮ Some strongly undecidable natural arithmetical problems, with an application to intuitionistic theories ⋮ Fixed point theorems for precomplete numberings ⋮ Probability 1 computation with chemical reaction networks ⋮ Double jumps of minimal degrees ⋮ Turing oracle machines, online computing, and three displacements in computability theory ⋮ On \(m\)-degrees of recursively enumerable sets ⋮ Limits on jump inversion for strong reducibilities ⋮ Extensions of embeddings below computably enumerable degrees ⋮ The Turing closure of an Archimedean field ⋮ Equality is a jump ⋮ The upper semilattice of degrees ≤ 0′ is complemented ⋮ Computation of recursive functionals using minimal initial segments ⋮ Undecidability and 1-types in intervals of the computably enumerable degrees ⋮ Maximality and collapse in the hierarchy of α-c.a. degrees ⋮ Sets of Formulas Valid in Finite Structures ⋮ Reflection in conditional rewriting logic ⋮ The rhombus classes of degrees of unsolvability. I. The jump properties ⋮ Mathematics based on incremental learning -- excluded middle and inductive inference

This page was built for publication: On degrees of unsolvability