Bounded Immunity and Btt‐Reductions
Stephen Fenner, Marcus Schaefer · Mathematical logic quarterly · 1999
Abstract We define and study a new notion called k‐immunity that lies between immunity and hyperimmunity in strength. Our interest in k‐immunity is justified by the result that θ does not k‐tt reduce to a k‐immune set, which improves a previous result by Kobzev [7]. We apply the result to show that Φ′ does not btt‐reduce to MIN, the set of minimal programs. Other applications include the set of Kolmogorov random strings, and retraceable and regressive sets. We also give a new characterization of effectively simple sets and show that simple sets are not btt‐cuppable.