Solovay functions and their applications in algorithmic randomness (Q494057): Difference between revisions

\textit{Weak Solovay functions} \(g: \mathbb{N}\to \mathbb{N}\) are right-computable, that is, computably approximable from above functions such that \(f(n)=K(n)+O(1)\) for infinitely many values \(n\in \mathbb{N}\). Here, \(K\) denotes the prefix-free Kolmogorov complexity. A function \(g: \mathbb{N}\to \mathbb{N}\) is a \textit{Solovay function} if it is weakly Solovay and computable. The paper proves several analogies between (weak) Solovay functions and prefix-free Kolmogorov complexity \(K\). In particular, with respect to Martin Löf randomness, it shows the following: {\parindent=6mm \begin{itemize} \item[(a)] Let \(g: \mathbb{N}\to \mathbb{N}\) be a right-computable function. Then, \(g\) is a Solovay function if and only if sum \(\sum_n 2^{-g(n)}\) is finite and is a Martin-Löf random real. \item [(b)] Let \(C: \{0,1\}^*\to \mathbb{N}\) denote plain Kolmogorov complexity, \(A= x_1\cdots x_i\cdots \in \{0,1\}^\omega\) and \(f: \mathbb{N}\to \mathbb{N}\) be right-computable. Then, the conditions {\parindent=11mm\begin{itemize} \item[1.] \(C(x_1\cdots x_n)\geq n - f (n) - O(1)\) if and only if \(A\) is Martin Löf random, and \item[2.] \(f\) is a weak Solovay function \end{itemize}} are equivalent. \end{itemize}} (Here, the abstract contains erroneously a different statement.) Furthermore, the paper deals with \(K\)-trivial sequences \(A= x_1\cdots x_i\cdots\in \{0,1\}^\omega\). Recall that \(A\) is \(K\)-\textit{trivial} provided \(K(x_1\cdots x_n) <K(n) +O(1)\). Here, it is shown that {\parindent=6mm \begin{itemize} \item[(c)] \(A\) is \(K\)-trivial if and only if \(K(x_1\cdots x_n) <f(n) +O(1)\) for some weak Solovay function and any right-computable function \(f\) that makes the equivalence \(A\) is \(K\)-trivial if and only if \(K(x_1\cdots x_n) <f(n) +O(1)\) true is a weak Solovay function. \end{itemize}}