Bounded Immunity and Btt-Reductions

DOI10.1002/malq.19990450102zbMath0921.03046OpenAlexW2038415779MaRDI QIDQ4238422

Marcus Schaefer, Stephen A. 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

computabilityrecursion theorysimple setshyperimmune setsimmune setsKolmogorov random stringsretraceable setsbounded reducibilitiesbtt-cuppableintroenumerable setsintroreducible setsminimal indices of a Gödel numberingregressive sets

Mathematics Subject Classification ID

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

Related Items (3)

On the Turing degrees of minimal index sets ⋮ An incomplete set of shortest descriptions ⋮ Working with strong reducibilities above totally $\omega $-c.e. and array computable degrees

Cites Work

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

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