In this paper we construct a structure R that is a “finite version” of the semi-lattice of Turing degrees. Its elements are strings (technically, sequences of strings) and x `<=` y means that K(x|y)=(conditional Kolmogorov complexity of x relative to y) is small. We construct two elements in R that do not have greatest lower bound. We give a series of examples that show how natural algebraic constructions give two elements that have lower bound 0 (minimal element) but significant mutual information. (A first example of that kind was constructed by Gács–Körner(Problems Control Inform. Theory 2 (1973) 149) using a completely different technique.) Wede4ne a notion of “complexity profile” of the pair of elements of R and give (exact) upper andlower bounds for it in a particular case.
|Number of pages||27|
|Journal||Theoretical Computer Science|
|Publication status||Published - 28 Jan 2002|
- Kolmogorov complexity
- common information
- conditional complexity