On the Turing degrees of minimal index sets

We study generalizations of shortest programs as they pertain to Schaefer’s MIN ∗ problem. We identify sets of m -minimal and T -minimal indices and characterize their truth-table and Turing degrees. In particular, we show MIN m ⊕ 0̸ ″ ≡ T 0̸ ‴ , MIN T ( n ) ⊕ 0̸ ( n + 2 ) ≡ T 0̸ ( n + 4 ) , and that there exists a Kolmogorov numbering ψ satisfying both MIN ψ m ≡ tt 0̸ ‴ and MIN ψ T ( n ) ≡ T 0̸ ( n + 4 ) . This Kolmogorov numbering also achieves maximal truth-table degree for other sets of minimal indices. Finally, we show that the set of shortest descriptions, SD , is 2-c.e. but not co-2-c.e. Some open problems are left for the reader.