Bounded Immunity and Btt-Reductions

DOI10.1002/MALQ.19990450102MaRDI QIDQ4238422zbMATH OpenOpenAlexFDO

Authors Marcus Schaefer, S. Fenner

Publication date 21 September 1999

Published in Mathematical Logic Quarterly (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1002/malq.19990450102

zbMATH Keywords

bounded reducibilitiesbtt-cuppablecomputabilityhyperimmune setsimmune setsintroenumerable setsintroreducible setsKolmogorov random stringsminimal indices of a Gödel numberingrecursion theoryregressive setsretraceable setssimple sets

Mathematics Subject Classification ID

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

Recommendations

• Immunity, Relativizations, and Nondeterminism
• A note on balanced immunity
• Immunity properties and strong positive reducibilities
• Bi-immune sets for complexity classes

Cites work

• A note on universal sets
• btt-reducibility
• Classical recursion theory. The theory of functions and sets of natural numbers
• On complete btt-degrees
• On Properties of Regressive Sets
• On the complexity of random strings
• Post's program and incomplete recursively enumerable sets.
• Program size in restricted programming languages
• T-Degrees, Jump Classes, and Strong Reducibilities
• Uniformly introreducible sets

Cited in

(5)

• Bi-immunity over different size alphabets
• On the Turing degrees of minimal index sets
• A note on balanced immunity
• Working with strong reducibilities above totally -c.e. and array computable degrees
• An incomplete set of shortest descriptions

This page was built for publication: Bounded Immunity and Btt-Reductions

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