Premium
Bounded Immunity and Btt‐Reductions
Author(s) -
Fenner Stephen,
Schaefer Marcus
Publication year - 1999
Publication title -
mathematical logic quarterly
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.473
H-Index - 28
eISSN - 1521-3870
pISSN - 0942-5616
DOI - 10.1002/malq.19990450102
Subject(s) - mathematics , simple (philosophy) , set (abstract data type) , bounded function , immunity , characterization (materials science) , discrete mathematics , immune system , computer science , epistemology , mathematical analysis , immunology , biology , philosophy , materials science , programming language , nanotechnology
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.