On the Turing degrees of minimal index sets (Q2382278)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | On the Turing degrees of minimal index sets |
scientific article |
Statements
On the Turing degrees of minimal index sets (English)
0 references
28 September 2007
0 references
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.
0 references
Turing degrees
0 references
minimal indices
0 references
shortest programs
0 references
shortest descriptions
0 references
Kolmogorov numberings
0 references
truth-table degrees
0 references
0 references
0 references