@misc{BaartseBarmpalias, author = {Baartse, Martijn and Barmpalias, George}, title = {On the gap between trivial and nontrivial initial segment prefix-free complexity}, series = {Theory of Computing Systems}, journal = {Theory of Computing Systems}, issn = {1433-0490}, pages = {20}, abstract = {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{\´a}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).}, language = {en} } @inproceedings{ZhengBarmpalias, author = {Zheng, Xizhong and Barmpalias, George}, title = {On the monotonic computability of semi-computable real numbers}, language = {en} } @article{ZhengRettingerBarmpalias, author = {Zheng, Xizhong and Rettinger, Robert and Barmpalias, George}, title = {h-Monotonically computable real numbers}, series = {Mathematical Logic Quarterly}, volume = {51}, journal = {Mathematical Logic Quarterly}, number = {2}, issn = {0942-5616}, pages = {157 -- 170}, language = {en} }