The Halting Problem Relativized to Complements

DOI10.2307/2039138zbMath0248.02044OpenAlexW4237756549MaRDI QIDQ5661862

Louise Hay

Publication date: 1973

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

Mathematics Subject Classification ID

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

Related Items

Recursively enumerable sets and degrees, A Reducibility Condition for Recursiveness

Cites Work

• The class of recursively enumerable subsets of a recursively enumerabl e set
• Interpolation and embedding in the recursively enumerable degrees
• On degrees of unsolvability
• Retraceable Sets
• Relativized Halting Problems
• Decidability of the “almost all” theory of degrees
• The degrees of bi‐immune sets
• Applications of Forcing to the Degree-Theory of the Arithmetical Hierarchy