Bounded Immunity and Btt-Reductions

DOI10.1002/malq.19990450102zbMath0921.03046MaRDI 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

computability; recursion theory; simple sets; hyperimmune sets; immune sets; Kolmogorov random strings; retraceable sets; bounded reducibilities; btt-cuppable; introenumerable sets; introreducible sets; minimal indices of a Gödel numbering; regressive sets

Mathematics Subject Classification ID

03D25: Recursively (computably) enumerable sets and degrees

03D30: Other degrees and reducibilities in computability and recursion theory

Related Items

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

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