On the Gap Between Trivial and Nontrivial Initial Segment Prefix-Free Complexity
An infinite sequence X is said to have trivial (prefix-free) initial segment complexity if the prefix-free Kolmogorov complexity of each initial segment of X is the same as the complexity of the sequence of 0s of the same length, up to a constant. We study the gap between the minimum complexity K(0 n ) and the initial segment complexity of a nontrivial sequence, and in particular the nondecreasing unbounded functions f such that (?) for a nontrivial sequence X, where K denotes the prefix-free complexity. Our first result is that there exists a \(\varDelta^{0}_{3}\) unbounded nondecreasing function f which does not have this property. It is known that such functions cannot be \(\varDelta^{0}_{2}\) hence this is an optimal bound on their arithmetical complexity. Moreover it improves the bound \(\varDelta^{0}_{4}\) that was known from Csima and Montalbn (Proc. Amer. Math. Soc. 134(5):14991502, 2006).
initial segment prefix-free complexity kolmogorov complexity k-triviality low for ?