Switch to: Citations

Add references

You must login to add references.
  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  
  • Recursive Enumerability and the Jump Operator.Gerald E. Sacks - 1964 - Journal of Symbolic Logic 29 (4):204-204.
  • On btt‐Degrees of Sets of Minimal Numbers in Gödel Numberings.Jefim Kinber - 1976 - Mathematical Logic Quarterly 23 (13‐15):201-212.
  • On btt-Degrees of Sets of Minimal Numbers in Gödel Numberings.Jefim Kinber - 1977 - Zeitschrift fur mathematische Logik und Grundlagen der Mathematik 23 (13-15):201-212.
  • Recursively enumerable sets modulo iterated jumps and extensions of Arslanov's completeness criterion.C. G. Jockusch, M. Lerman, R. I. Soare & R. M. Solovay - 1989 - Journal of Symbolic Logic 54 (4):1288-1323.
  • Two Recursively Enumerable Sets of Incomparable Degrees of Unsolvability.R. M. Friedberg - 1958 - Journal of Symbolic Logic 23 (2):225-226.
  • 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  
  • A Theorem on Hypersimple Sets.J. C. E. Dekker - 1956 - Journal of Symbolic Logic 21 (1):100-100.
  • Recursively Enumerable Sets and Retracting Functions.C. E. M. Yates - 1967 - Journal of Symbolic Logic 32 (3):394-394.