T-Degrees, Jump Classes, and Strong Reducibilities

DOI10.2307/2000330zbMath0638.03039OpenAlexW4244794038MaRDI QIDQ3778736

Carl G. jun. Jockusch, Rodney G. Downey

Publication date: 1987

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

zbMATH Keywords

Turing reducibilityr.e. degreesreducibilities1-topped degrees

Mathematics Subject Classification ID

Recursively (computably) enumerable sets and degrees (03D25) Other degrees and reducibilities in computability and recursion theory (03D30)

Related Items (17)

Nonlowness is independent from fickleness ⋮ Completely mitotic r. e. degrees ⋮ Intervals and sublattices of the r.e. weak truth table degrees. I: Density ⋮ Intervals and sublattices of the r.e. weak truth table degrees. II: Nonbounding ⋮ Recursively enumerable \(m\)- and \(tt\)-degrees. II: The distribution of singular degrees ⋮ Localization of a theorem of Ambos-Spies and the strong anti-splitting property ⋮ Lowness, Randomness, and Computable Analysis ⋮ Some reducibilities and splittings of recursively enumerable sets ⋮ Tabular degrees in \(\alpha\)-recursion theory ⋮ A HIERARCHY OF COMPUTABLY ENUMERABLE DEGREES ⋮ Recursive Linear Orders with Incomplete Successivities ⋮ Hierarchy of Computably Enumerable Degrees II ⋮ Two Theorems on Truth Table Degrees ⋮ Splitting theorems in recursion theory ⋮ Classes bounded by incomplete sets ⋮ Bounded Immunity and Btt-Reductions ⋮ \(Q\)-reducibility and \(m\)-reducibility on computably enumerable sets

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Structural interactions of the recursively enumerable T- and W-degrees
• \(\Delta\)\( ^ 0_ 2\) degrees and transfer theorems
• Classical recursion theory. Vol. II
• Hereditary sets and tabular reducibility
• Interpolation and embedding in the recursively enumerable degrees
• An Algebraic Decomposition of the Recursively Enumerable Degrees and the Coincidence of Several Degree Classes with the Promptly Simple Degrees
• The upper semilattice of degrees ≤ 0′ is complemented
• Wtt-degrees and T-degrees of r.e. sets
• The Degrees of R.E. Sets Without the Universal Splitting Property
• The universal splitting property. II
• Pairs without infimum in the recursively enumerable weak truth table degrees
• Degree theoretical splitting properties of recursively enumerable sets
• Reducibility and Completeness for Sets of Integers
• Bounding minimal pairs
• Strong reducibilities
• A Completely Mitotic Nonrecursive R.E. Degree
• Minimal pairs and high recursively enumerable degrees
• w tt-Complete Sets are not Necessarily tt-Complete
• The weak truth table degrees of recursively enumerable sets
• Computational complexity, speedable and levelable sets
• Lower Bounds for Pairs of Recursively Enumerable Degrees
• Recursion Theory and Dedekind Cuts
• On the Degrees of Index Sets. II
• Relationships Between Reducibilities
• Degrees in Which the Recursive Sets are Uniformly Recursive
• A Theorem on Hypersimple Sets
• Recursively enumerable sets of positive integers and their decision problems

This page was built for publication: T-Degrees, Jump Classes, and Strong Reducibilities