Searching for shortest and least programs (Q2286740)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Searching for shortest and least programs |
scientific article |
Statements
Searching for shortest and least programs (English)
0 references
22 January 2020
0 references
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.
0 references
Kolmogorov complexity
0 references
universal Turing machine
0 references
recursive coding function
0 references
shortest program
0 references
least program
0 references
Bennett-shallow set
0 references
recursion theory
0 references
algorithmic information theory
0 references
0 references