The upper semi-lattice of degrees of recursive unsolvability
From MaRDI portal
Publication:2652167
DOI10.2307/1969708zbMath0057.24703OpenAlexW1967629533WikidataQ56430698 ScholiaQ56430698MaRDI QIDQ2652167
Publication date: 1954
Published in: Annals of Mathematics. Second Series (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.2307/1969708
Related Items (97)
An Uncountable Set of Incomparable Degrees ⋮ Untersuchungen über die Struktur des Kleene-Postschen Halbverbandes der Grade der Rekursiven Unlösbarkeit ⋮ Decomposition and infima in the computably enumerable degrees ⋮ The minimum of two regressive isols ⋮ Degrees of Transducibility ⋮ Refining the taming of the reverse mathematics zoo ⋮ Separating weak \(\alpha\)-change and \(\alpha\)-change genericity ⋮ Jump embeddings in the Turing degrees ⋮ The ∀∃-theory of ℛ(≤,∨,∧) is undecidable ⋮ The Typical Constructible Object ⋮ On the embedding of α-recursive presentable lattices into the α-recursive degrees below 0′ ⋮ On complete degrees ⋮ A theorem on minimal degrees ⋮ Degrees of Unsolvability: A Tutorial ⋮ Infima of d.r.e. degrees ⋮ The Mathematical Work of S.C.Kleene ⋮ Priority constructions ⋮ Formalism and intuition in computability ⋮ The jump is definable in the structure of the degrees of unsolvability ⋮ Transducer degrees: atoms, infima and suprema ⋮ A General Framework for Priority Arguments ⋮ Computational processes, observers and Turing incompleteness ⋮ Hierarchies of number-theoretic predicates ⋮ Recursive well-orderings ⋮ Unnamed Item ⋮ Not every finite lattice is embeddable in the recursively enumerable degrees ⋮ Countable admissible ordinals and hyperdegrees ⋮ An oracle builder's toolkit ⋮ Incomparable Vγ$V_\gamma$‐degrees ⋮ The degrees below a 1-generic degree < 0′ ⋮ Unnamed Item ⋮ On the uniform computational content of computability theory ⋮ Direct construction of Scott ideals ⋮ A criterion for completeness of degrees of unsolvability ⋮ THE FIRST-ORDER LOGIC OF CZF IS INTUITIONISTIC FIRST-ORDER LOGIC ⋮ Classes of Polish spaces under effective Borel isomorphism ⋮ Measure-theoretic construction of incomparable hyperdegrees ⋮ Weakly Represented Families in Reverse Mathematics ⋮ DIRECT AND LOCAL DEFINITIONS OF THE TURING JUMP ⋮ Gödel numberings of partial recursive functions ⋮ Minimal Covers and Arithmetical Sets ⋮ A personal account of Turing's imprint on the development of computer science ⋮ The Complexity of Orbits of Computably Enumerable Sets ⋮ Degrees of models ⋮ A survey of partial degrees ⋮ Natural factors of the Medvedev lattice capturing IPC ⋮ Hierarchies in Recursive Function Theory ⋮ The Information Content of Typical Reals ⋮ Why Turing’s Thesis Is Not a Thesis ⋮ Unnamed Item ⋮ Genericity for Mathias forcing over general Turing ideals ⋮ The p-T-degrees of the recursive sets: Lattice embeddings, extensions of embeddings and the two-quantifier theory ⋮ The decision problem for recursively enumerable degrees ⋮ Embedding jump upper semilattices into the Turing degrees ⋮ On Reducibility by Recursive Functions ⋮ Banach–Mazur games, comeager sets and degrees of unsolvability ⋮ Infima of d.r.e. Degrees ⋮ Local Definitions in Degree Structures: The Turing Jump, Hyperdegrees and Beyond ⋮ Complementation in the Turing degrees ⋮ Discontinuities of provably correct operators on the provably recursive real numbers ⋮ Forcing and reducibilities ⋮ Augmented loop languages and classes of computable functions ⋮ Lattice initial segments of the hyperdegrees ⋮ Computably enumerable Turing degrees and the meet property ⋮ Goodness in the enumeration and singleton degrees ⋮ The uniform Martin’s conjecture for many-one degrees ⋮ Undecidability and initial segments of the (r.e.) tt-degrees ⋮ Strong and weak reducibility of algorithmic problems1 ⋮ Decidability and Invariant Classes for Degree Structures ⋮ Lattice nonembeddings and intervals of the recursively enumerable degrees ⋮ Naturalness in Mathematics ⋮ A Theorem on Intermediate Reducibilities ⋮ Recursive Enumerability and the Jump Operator ⋮ Recursively enumerable sets and degrees ⋮ Definable degrees and automorphisms of 𝒟 ⋮ A semantical proof of De Jongh's theorem ⋮ On the theory of the PTIME degrees of the recursive sets ⋮ Arithmetical Predicates and Function Quantifiers ⋮ Initial segments of the degrees of size \(\aleph _ 1\) ⋮ On minimal pairs of enumeration degrees ⋮ Mass problems associated with effectively closed sets ⋮ Turing oracle machines, online computing, and three displacements in computability theory ⋮ Computing degrees of unsolvability ⋮ Extensions of embeddings below computably enumerable degrees ⋮ Mass Problems and Measure-Theoretic Regularity ⋮ Degree Structures: Local and Global Investigations ⋮ Some Theorems on Classes of Recursively Enumerable Sets ⋮ On a Subrecursive Hierarchy and Primitive Recursive Degrees ⋮ On the notational independence of various hierarchies of degrees of unsolvability ⋮ Constructive Versions of Ordinal Number Classes ⋮ The density of the nonbranching degrees ⋮ Unnamed Item ⋮ Independence Results on the Global Structure of the Turing Degrees ⋮ Decidability of the “almost all” theory of degrees ⋮ Pseudo-jump operators. II: Transfinite iterations, hierarchies and minimal covers ⋮ On effectively computable realizations of choice functions ⋮ The minimum degree of recursively representable choice functions
This page was built for publication: The upper semi-lattice of degrees of recursive unsolvability
