Switch to: References

Add citations

You must login to add citations.
  1. An Incomplete Set of Shortest Descriptions.Frank Stephan & Jason Teutsch - 2012 - Journal of Symbolic Logic 77 (1):291-307.
    The truth-table degree of the set of shortest programs remains an outstanding problem in recursion theory. We examine two related sets, the set of shortest descriptions and the set of domain-random strings, and show that the truth-table degrees of these sets depend on the underlying acceptable numbering. We achieve some additional properties for the truth-table incomplete versions of these sets, namely retraceability and approximability. We give priority-free constructions of bounded truth-table chains and bounded truth-table antichains inside the truth-table complete degree (...)
    Direct download (7 more)  
     
    Export citation  
     
    Bookmark  
  • On the Turing Degrees of Minimal Index Sets.Jason Teutsch - 2007 - Annals of Pure and Applied Logic 148 (1):63-80.
    We study generalizations of shortest programs as they pertain to Schaefer’s problem. We identify sets of -minimal and -minimal indices and characterize their truth-table and Turing degrees. In particular, we show , , and that there exists a Kolmogorov numbering ψ satisfying both and . This Kolmogorov numbering also achieves maximal truth-table degree for other sets of minimal indices. Finally, we show that the set of shortest descriptions, , is 2-c.e. but not co-2-c.e. Some open problems are left for the (...)
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   1 citation