Searching for shortest and least programs (Q2286740)

Inspired by the existence of Solovay functions, the authors investigate coding functions. I.e. partial functions \(p\) so that \(M(p(x))=x\) for some Turing machine \(M\) and every \(x\) in the domain of \(p\). Then it is proved that for any plain or prefix-free universal machine \(U\), there is a recursive coding function \(f\) so that \(f(x)\) maps infinitely many strings to their least programs. They also look at some interesting properties. For example, a set is Bennett-deep for plain complexity in case for every recursive upper bound \(g\) for plain complexity \(C\) (or prefix-free complexity \(K\)), \(\lim_n g(A \upharpoonright n)-C(A \upharpoonright n)=\infty\) (or \(\lim_n g(A \upharpoonright n)-K(A \upharpoonright n)=\infty\)). They use recursive coding functions to characterize such sets.