Recursive Enumerability and the Jump Operator

DOI10.2307/1993604zbMath0118.25103OpenAlexW4252466355MaRDI QIDQ5729295

Gerald E. Sacks

Publication date: 1963

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

zbMATH Keywords

mathematical logic

Related Items

On the Turing degrees of minimal index sets ⋮ The ∀∃-theory of ℛ(≤,∨,∧) is undecidable ⋮ IN MEMORIAM: GERALD E. SACKS, 1933–2019 ⋮ A non-inversion theorem for the jump operator ⋮ Coding true arithmetic in the Medvedev degrees of \(\Pi^0_1\) classes ⋮ On the jumps of the degrees below a recursively enumerable degree ⋮ Inverting the Half-Jump ⋮ A bounded jump for the bounded Turing degrees ⋮ An incomplete set of shortest descriptions ⋮ Infima in the d.r.e. degrees ⋮ The nonlow computably enumerable degrees are not invariant in $\mathcal {E}$ ⋮ Completely mitotic c.e. degrees and non-jump inversion ⋮ \(r\)-maximal major subsets ⋮ Elementary differences among jump classes ⋮ Recursively enumerable sets and degrees ⋮ Limits on jump inversion for strong reducibilities ⋮ \(\Sigma_2\)-constructions and \(\text{I}\Sigma_1\) ⋮ Automorphisms of the lattice of recursively enumerable sets

Cites Work

• Unnamed Item
• Unnamed Item
• On degrees of recursive unsolvability
• On degrees of unsolvability
• The upper semi-lattice of degrees of recursive unsolvability
• A criterion for completeness of degrees of unsolvability
• TWO RECURSIVELY ENUMERABLE SETS OF INCOMPARABLE DEGREES OF UNSOLVABILITY (SOLUTION OF POST'S PROBLEM, 1944)