Pairs of Words with Nonmaterializable Mutual Information

Let there be a pair of words $\langle a,b\rangle$ with sufficiently large mutual information. Can we always “materialize” this information, i.e., point out a word $c$ that can be computed from $a$ and $b$ simply and whose Kolmogorov complexity equals the mutual information between $a$ and $b$? In this paper, we propose a better estimate for the amount of mutual information which may be materialized for words from the construction of Gács and Körner, and also give a new method for constructing pairs of words with nonmaterializable mutual information.