Degrees of Unsolvability. (AM-55)

DOI10.1515/9781400881840zbMath0143.25302OpenAlexW2565632284MaRDI QIDQ5519129

Gerald E. Sacks

Publication date: 1963

Full work available at URL: https://doi.org/10.1515/9781400881840

zbMATH Keywords

mathematical logic

Related Items (99)

Reductions among polynomial isomorphism types ⋮ An extension of the nondiamond theorem in classical and α-recursion theory ⋮ Computational depth and reducibility ⋮ An Algebraic Decomposition of the Recursively Enumerable Degrees and the Coincidence of Several Degree Classes with the Promptly Simple Degrees ⋮ Large Turing independent sets ⋮ On the Turing degrees of minimal index sets ⋮ Measure theory and weak König's lemma ⋮ Program Size Complexity of Correction Grammars in the Ershov Hierarchy ⋮ Bounded truth table does not reduce the one-query tautologies to a random oracle ⋮ DEGREES OF RANDOMIZED COMPUTABILITY ⋮ IN MEMORIAM: GERALD E. SACKS, 1933–2019 ⋮ Cupping with random sets ⋮ Minimal complements for degrees below 0′ ⋮ A theorem on minimal degrees ⋮ Index sets and presentations of complexity classes ⋮ On the Degrees of Index Sets ⋮ Deficiency Sets and Bounded Information Reducibilities ⋮ On a Problem of G. E. Sacks ⋮ Separating families and order dimension of Turing degrees ⋮ Initial segments of the degrees of unsolvability Part II: minimal degrees ⋮ PERMUTATIONS OF THE INTEGERS INDUCE ONLY THE TRIVIAL AUTOMORPHISM OF THE TURING DEGREES ⋮ Some contrasts between degrees and the arithmetical hierarchy ⋮ Recursively enumerable sets which are uniform for finite extensions ⋮ A General Framework for Priority Arguments ⋮ DEEP CLASSES ⋮ Continuous randomness via transformations of 2-random sequences ⋮ Mass problems and density ⋮ The enumeration degrees: Local and global structural interactions ⋮ Randomness, lowness and degrees ⋮ Sets of real numbers closed under Turing equivalence: applications to fields, orders and automorphisms ⋮ Some theorems on R-maximal sets and major subsets of recursively enumerable sets ⋮ On initial segment complexity and degrees of randomness ⋮ Elementary Differences Between the Isols and the Co-Simple Isols ⋮ \(A\)-computable graphs ⋮ On the Degrees of Index Sets. II ⋮ Isomorphism Types in Wreath Products and Effective Embeddings of Periodic Groups ⋮ Hierarchies of Effective Descriptive Set Theory ⋮ Martin's axiom and embeddings of upper semi-lattices into the Turing degrees ⋮ Some elementary degree-theoretic reasons why structures need similarity types ⋮ Permutations of the Integers Induce only the Trivial Automorphism of the Turing Degrees ⋮ A measure-theoretic proof of Turing incomparability ⋮ Semirecursive Sets and Positive Reducibility ⋮ Minimal Covers and Arithmetical Sets ⋮ Measure-Theoretic Uniformity in Recursion Theory and Set Theory ⋮ Derandomization in game-theoretic probability ⋮ Higher-Order Indecomposable Isols ⋮ There is no degree invariant half-jump ⋮ A minimal degree not realizing least possible jump ⋮ Bounded enumeration reducibility and its degree structure ⋮ Branching Degrees above low Degrees ⋮ The Information Content of Typical Reals ⋮ Cofinal maximal chains in the Turing degrees ⋮ Jump inversions inside effectively closed sets and applications to randomness ⋮ Does truth-table of linear norm reduce the one-query tautologies to a random oracle? ⋮ The decision problem for recursively enumerable degrees ⋮ Trivial Reals ⋮ Two existence theorems for computable numerations ⋮ WCS-analysis of the context-sensitive ⋮ On degrees of recursively enumerable sets ⋮ Augmented loop languages and classes of computable functions ⋮ Über die Reduzierbarkeit berechenbarer Numerierungen ⋮ Additive structure in uncountable models for a fixed completion of P ⋮ An operator embedding theorem for complexity classes of recursive functions ⋮ Polynomial and abstract subrecursive classes ⋮ Lattice initial segments of the hyperdegrees ⋮ The importance of Π₁⁰ classes in effective randomness ⋮ Maximal chains in the Turing degrees ⋮ Goodness in the enumeration and singleton degrees ⋮ The Role of True Finiteness in the Admissible Recursively Enumerable Degrees ⋮ Mass Problems and Randomness ⋮ A note on the consistency operator ⋮ Ivan Soskov: a life in computability ⋮ Unnamed Item ⋮ Model-theoretic properties of Turing degrees in the Ershov difference hierarchy ⋮ Recursively enumerable sets and degrees ⋮ Measure-theoretic applications of higher Demuth’s Theorem ⋮ Jump operator and Yates Degrees ⋮ Intuitionistically provable recursive well-orderings ⋮ FINDING THE LIMIT OF INCOMPLETENESS I ⋮ Complete sets and closeness to complexity classes ⋮ Measure theory aspects of locally countable orderings ⋮ Lowness and nullsets ⋮ Degree Structures: Local and Global Investigations ⋮ Calibrating Randomness ⋮ The $\Pi _3$-theory of the computably enumerable Turing degrees is undecidable ⋮ Measure and cupping in the Turing degrees ⋮ Measures and their random reals ⋮ On the existence of a strong minimal pair ⋮ Lowness properties and randomness ⋮ Automorphisms of the lattice of recursively enumerable sets ⋮ A minimal pair of recursively enumerable degrees ⋮ Effective randomness for continuous measures ⋮ Random reals as measures of natural open sets ⋮ Probabilistic computability and choice ⋮ Sets of Formulas Valid in Finite Structures ⋮ Relativization of the Theory of Computational Complexity ⋮ Arithmetic transfinite induction and recursive well-orderings ⋮ Independence Results on the Global Structure of the Turing Degrees ⋮ Determining Automorphisms of the Recursively Enumerable Sets

This page was built for publication: Degrees of Unsolvability. (AM-55)