On the Turing degrees of minimal index sets (Q2382278)

The author considers the problem MIN*, studied by \textit{M. Schaefer} in [Arch. Math. Logic 37, No. 8, 521--548 (1998; Zbl 0910.03037)]. He gives a generalization of Schaefer's MIN* shortest program and obtains analogous results by characterizing the Turing degrees for four sets of indices, called minimal index sets. Some results about complexity of the set of shortest descriptions are proved and it is shown that it will be difficult to prove the optimality of the previous results. As a particular case, the author shows that there exists a Kolmogorov numbering for which all the minimal index sets simultaneously achieve maximum possible truth-table or Turing degree. At the end some open questions are presented.