1. A guided tour of minimal indices and shortest descriptions.Marcus Schaefer - 1998 - Archive for Mathematical Logic 37 (8):521-548.
    The set of minimal indices of a Gödel numbering $\varphi$ is defined as ${\rm MIN}_{\varphi} = \{e: (\forall i < e)[\varphi_i \neq \varphi_e]\}$ . It has been known since 1972 that ${\rm MIN}_{\varphi} \equiv_{\mathrm{T}} \emptyset^{\prime \prime }$ , but beyond this ${\rm MIN}_{\varphi}$ has remained mostly uninvestigated. This paper collects the scarce results on ${\rm MIN}_{\varphi}$ from the literature and adds some new observations including that ${\rm MIN}_{\varphi}$ is autoreducible, but neither regressive nor (1,2)-computable. We also study several variants of (...)
    Direct download (3 more)  
    Export citation  
    Bookmark   5 citations  
  2.  25
    Bounded Immunity and Btt‐Reductions.Stephen Fenner & Marcus Schaefer - 1999 - Mathematical Logic Quarterly 45 (1):3-21.
    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 (...)
    No categories
    Direct download  
    Export citation  
    Bookmark   4 citations  
  3.  29
    Cuppability of Simple and Hypersimple Sets.Martin Kummer & Marcus Schaefer - 2007 - Notre Dame Journal of Formal Logic 48 (3):349-369.
    An incomplete degree is cuppable if it can be joined by an incomplete degree to a complete degree. For sets fulfilling some type of simplicity property one can now ask whether these sets are cuppable with respect to a certain type of reducibilities. Several such results are known. In this paper we settle all the remaining cases for the standard notions of simplicity and all the main strong reducibilities.
    Direct download (4 more)  
    Export citation