On degrees of unsolvability
From MaRDI portal
Publication:2626398
DOI10.2307/1970028zbMath0119.25105OpenAlexW2057392475MaRDI QIDQ2626398
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
Related Items
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 Σ1 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 Σ20 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
