• search hit 23 of 141
Back to Result List

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 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 nontrivialAn 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).show moreshow less

Export metadata

Additional Services

Search Google Scholar
Metadaten
Author: Martijn Baartse, George Barmpalias
URL:http://www.springerlink.com/content/h0k3581g7202p574/
ISSN:1433-0490
Title of the source (English):Theory of Computing Systems
Document Type:Scientific journal article peer-reviewed
Language:English
Year of publication:2012
Tag:Kolmogorov complexity – Initial segment prefix-free complexity – K-triviality – Low for Ω
Number of pages:20
Faculty/Chair:Fakultät 1 MINT - Mathematik, Informatik, Physik, Elektro- und Informationstechnik / FG Theoretische Informatik
Institution name at the time of publication:Fakultät für Mathematik, Naturwissenschaften und Informatik (eBTU) / LS Theoretische Informatik
Einverstanden ✔
Diese Webseite verwendet technisch erforderliche Session-Cookies. Durch die weitere Nutzung der Webseite stimmen Sie diesem zu. Unsere Datenschutzerklärung finden Sie hier.