. Proof, For some i, the prefix w is of the form w = z 1 . . . z i?1 v i , with v i a prefix of z i . Let ? = (1/?) · (3?) We consider two cases: Case 1: v i is long

K. Then and |. (-v-i-|-x-i?1-y-i?1-)-?-|v-i-|-?-3?-·-n-i-?-|v-i, ? ?)|v i |. This implies K(v i | z 1 . . . z i?1 ) > (1 ? ?) · |v i | ? O(1) ? (1 ? 2?)|v i |, because each z j can be constructed from x j and y j . By induction, it follows that K(z 1 z 2 . . . z i?1 v i ) ? (1 ? 3?)|z 1 z 2 . . . z i?1 v i |. For the induction step, the argument goes as follows: K(z 1 z 2 . . . z i?1 v i ) ? K(z 1 . . . z i?1 ) + K(v i | z 1 . . . z i?1 ) ?O(log(m 1 + . . . + m i?1 ) + log

R. Bienvenu, D. Doty, and F. Stephan, Constructive Dimension and Weak Truth-Table Degrees, Computation and Logic in the Real World -Third Conference of Computability in Europe, pp.63-721, 2005.
DOI : 10.1007/978-3-540-73001-9_7
URL : https://hal.archives-ouvertes.fr/hal-00191125

S. Cristian, M. Calude, and . Zimand, Algorithmically independent sequences, Developments in Language Theory, pp.183-195, 2008.

L. Fortnow, J. Hitchcock, A. Pavan, N. V. Vinodchandran, F. J. Wang et al., Extracting Kolmogorov complexity with applications to dimension zero-one laws Extracting information is hard Manuscript, http://www A lower cone in the wtt degrees of non-integral effective dimension Extractors with weak random seeds Computability and fractal dimension Generating quasi-random sequences from semi-random sources, Proceedings of the 33rd International Colloquium on Automata, Languages, and Programming Lecture Notes in Computer Science #4051. [Mil08] J. Miller Proceedings of IMS workshop on Computational Prospects of Infinity STOCVaz87] Umesh V. Vazirani. Strong communication complexity or generating quasirandom sequences from two communicating semi-random sources. Combinatorica, pp.335-345, 1986.

K. Nikolai, M. V. Vereshchagin, and . Vyugin, Independent minimum length programs to translate between given strings, Theor. Comput. Sci, vol.271, issue.12, pp.131-143, 2002.

M. Zimand, Two Sources Are Better Than One for Increasing the Kolmogorov Complexity of Infinite Sequences, Lecture Notes in Computer Science, vol.5010, pp.326-338
DOI : 10.1007/978-3-540-79709-8_33