Bounded Immunity and Btt-Reductions
From MaRDI portal
Publication:4238422
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
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
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