A guided tour of minimal indices and shortest descriptions (Q1127831)

The set of minimal indices of a Gödel numbering \(f\) is defined as MIN \(= \{e: (\forall i < e)[f_i\) is different from \(f_e]\}\). It has been known since 1972 that MIN is Turing equivalent to \(0''\), but beyond this MIN has remained mostly uninvestigated. This article collects the scarce results on MIN from the literature and supplements these with a detailed study of recursion-theoretic properties of MIN. For example it is shown that MIN is autoreducible, but neither regressive nor \((1,2)\)-computable. We also present results about several variants of MIN that have been defined in the literature such as size-minimal indices, shortest descriptions, and minimal indices of decision tables. Some challenging open problems are left for the adventurous reader.