The undecidability of the recursively enumerable degrees
From MaRDI portal
Publication:3666835
DOI10.1090/S0273-0979-1982-14970-9zbMath0518.03016WikidataQ29011875 ScholiaQ29011875MaRDI QIDQ3666835
Saharon Shelah, Leo Harrington
Publication date: 1982
Published in: Bulletin of the American Mathematical Society (Search for Journal in Brave)
Undecidability and degrees of sets of sentences (03D35) Recursively (computably) enumerable sets and degrees (03D25) Other degrees and reducibilities in computability and recursion theory (03D30)
Related Items
Undecidability of \(L(F_{\infty})\) and other lattices of r.e. substructures, Intervals and sublattices of the r.e. weak truth table degrees. I: Density, The undecidability of the lattice of r. e. closed subsets of an effective topological space, Working below a high recursively enumerable degree, European Summer Meeting of the Association for Symbolic Logic, THE n-r.e. DEGREES: UNDECIDABILITY AND Σ1 SUBSTRUCTURES, The ∀∃-theory of ℛ(≤,∨,∧) is undecidable, Interpreting true arithmetic in the theory of the r.e. truth table degrees, The last question on recursively enumerable \(m\)-degrees, Annual meeting of the Association for Symbolic Logic, Notre Dame, 1993, Computational processes, observers and Turing incompleteness, The existential theory of the poset of R.E. degrees with a predicate for single jump reducibility, The undecidability of the Π4-theory for the r.e. wtt and Turing degrees, Infima in the d.r.e. degrees, Undecidability and 1-types in the recursively enumerable degrees, Incomparable prime ideals of recursively enumerable degrees, A survey of results on the d.c.e. and \(n\)-c.e. degrees, Embedding and coding below a 1-generic degree, PARAMETER DEFINABILITY IN THE RECURSIVELY ENUMERABLE DEGREES, A necessary and sufficient condition for embedding principally decomposable finite lattices into the computably enumerable degrees preserving greatest element, 1998–99 Annual Meeting of the Association for Symbolic Logic, Undecidability and initial segments of the (r.e.) tt-degrees, Turing computability: structural theory, The Role of True Finiteness in the Admissible Recursively Enumerable Degrees, On the theory of the PTIME degrees of the recursive sets, Lattice nonembeddings and initial segments of the recursively enumerable degrees, THE THEORY OF THE METARECURSIVELY ENUMERABLE DEGREES, Degree Structures: Local and Global Investigations, The $\Pi _3$-theory of the computably enumerable Turing degrees is undecidable, On the existence of a strong minimal pair, The density of the nonbranching degrees, Definability in the Recursively Enumerable Degrees, Undecidability and 1-types in intervals of the computably enumerable degrees, CUPPING AND JUMP CLASSES IN THE COMPUTABLY ENUMERABLE DEGREES, Wtt-degrees and T-degrees of r.e. sets, Splitting theorems in recursion theory
Cites Work
