Bounded Immunity and Btt‐Reductions

Mathematical Logic Quarterly 45 (1):3-21 (1999)
  Copy   BIBTEX


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



    Upload a copy of this work     Papers currently archived: 93,031

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

Similar books and articles


Added to PP

25 (#654,023)

6 months
4 (#863,607)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

A guided tour of minimal indices and shortest descriptions.Marcus Schaefer - 1998 - Archive for Mathematical Logic 37 (8):521-548.
An incomplete set of shortest descriptions.Frank Stephan & Jason Teutsch - 2012 - Journal of Symbolic Logic 77 (1):291-307.
On the Turing degrees of minimal index sets.Jason Teutsch - 2007 - Annals of Pure and Applied Logic 148 (1):63-80.
Cuppability of Simple and Hypersimple Sets.Martin Kummer & Marcus Schaefer - 2007 - Notre Dame Journal of Formal Logic 48 (3):349-369.

Add more citations

References found in this work

Classical recursion theory: the theory of functions and sets of natural numbers.Piergiorgio Odifreddi - 1989 - New York, N.Y., USA: Sole distributors for the USA and Canada, Elsevier Science Pub. Co..
Computability and recursion.Robert I. Soare - 1996 - Bulletin of Symbolic Logic 2 (3):284-321.
Uniformly introreducible sets.Carl G. Jockusch - 1968 - Journal of Symbolic Logic 33 (4):521-536.
A note on universal sets.A. H. Lachlan - 1966 - Journal of Symbolic Logic 31 (4):573-574.

Add more references