The Halting Problem Relativized to Complements

DOI10.2307/2039138MaRDI QIDQ5661862zbMATH OpenOpenAlexFDO

Authors 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)

Cites work

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

Cited in

(2)

• A Reducibility Condition for Recursiveness
• Recursively enumerable sets and degrees

This page was built for publication: The Halting Problem Relativized to Complements

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5661862)