Bounded Immunity and Btt‐Reductions

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

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

Links

PhilArchive



    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

Analytics

Added to PP
2013-12-01

Downloads
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