1. On the Turing degrees of minimal index sets
- Author
-
Jason Teutsch
- Subjects
Shortest descriptions ,Discrete mathematics ,Minimal indices ,Turing degree ,Degree (graph theory) ,Logic ,Hyperarithmetical theory ,Turing degrees ,Computability theory ,MIN ,Numbering ,Combinatorics ,Post's theorem ,symbols.namesake ,Truth-table degrees ,symbols ,Shortest programs ,Kolmogorov numberings ,Turing ,computer ,Mathematics ,computer.programming_language - Abstract
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.
- Published
- 2007