Résumé
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.) We define a notion of “complexity profile” of the pair of elements of
R and give (exact) upper and lower bounds for it in a particular case.