Randomness for computable measures and initial segment complexity (Q508835): Difference between revisions

The paper studies the growth rates of the Kolmogorov complexity of initial segments of proper sequences, i.e. sequences that are random with respect to some computable measure on \(2^{\omega}\). There are four main results: {\parindent=7mm \begin{itemize}\item[(1)] the initial segment complexity of a proper sequence \(X\) is bounded from below by a computable function iff \(X\) is random with respect to some computable, continuous measure; \item[(2)] there is a family of complex sequences that are random with respect to a single computable measure such that for every computable, continuous measure \(\mu\), some sequence in this family fails to be random with respect to \(\mu\); \item[(3)] there are proper sequences with extremely slow-growing initial segment complexity; \item[(4)] various facts about the Turing degrees of proper sequences. \end{itemize}} All results are properly explained and proved in detail.