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 (...) by identifying an acceptable set of domain-random strings within each degree. (shrink)

The set of minimal indices of a Gödel numbering $\varphi$ is defined as ${\rm MIN}_{\varphi} = \{e: (\forall i < e)[\varphi_i \neq \varphi_e]\}$ . It has been known since 1972 that ${\rm MIN}_{\varphi} \equiv_{\mathrm{T}} \emptyset^{\prime \prime }$ , but beyond this ${\rm MIN}_{\varphi}$ has remained mostly uninvestigated. This paper collects the scarce results on ${\rm MIN}_{\varphi}$ from the literature and adds some new observations including that ${\rm MIN}_{\varphi}$ is autoreducible, but neither regressive nor (1,2)-computable. We also study several variants of (...) ${\rm MIN}_{\varphi}$ that have been defined in the literature like size-minimal indices, shortest descriptions, and minimal indices of decision tables. Some challenging open problems are left for the adventurous reader. (shrink)