TY - GEN A1 - Baartse, Martijn A1 - Barmpalias, George T1 - On the gap between trivial and nontrivial initial segment prefix-free complexity T2 - Theory of Computing Systems N2 - 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 Montalbán (Proc. Amer. Math. Soc. 134(5):1499–1502, 2006). Our second result is that if f is $\varDelta^{0}_{2}$ then there exists a non-empty $\varPi^{0}_{1}$ class of reals X with nontrivial prefix-free complexity which satisfy (⋆). This implies that in this case there uncountably many nontrivial reals X satisfying (⋆) in various well known classes from computability theory and algorithmic randomness; for example low for Ω, non-low for Ω and computably dominated reals. A special case of this result was independently obtained by Bienvenu, Merkle and Nies (STACS, pp. 452–463, 2011). KW - Kolmogorov complexity – Initial segment prefix-free complexity – K-triviality – Low for Ω Y1 - 2012 UR - http://www.springerlink.com/content/h0k3581g7202p574/ SN - 1433-0490 ER - TY - CHAP A1 - Zheng, Xizhong A1 - Barmpalias, George T1 - On the monotonic computability of semi-computable real numbers Y1 - 2003 ER - TY - JOUR A1 - Zheng, Xizhong A1 - Rettinger, Robert A1 - Barmpalias, George T1 - h-Monotonically computable real numbers JF - Mathematical Logic Quarterly Y1 - 2005 SN - 0942-5616 VL - 51 IS - 2 SP - 157 EP - 170 ER -