Pairs of words with nonmaterializable mutual information. (English. Russian original) Zbl 1025.94007

Romashchenko, A. E.

Probl. Inf. Transm. 36, No. 1, 1-18 (2000); translation from Probl. Peredachi Inf. 36, No. 1, 3-20 (2000).

Summary: Let \(\langle a,b\rangle\) be a pair of words with sufficiently large mutual information. Can we always “materialize” this information, i.e., point out a word \(c\) that can be simply computed from \(a\) and \(b\) 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 P. Gács and J. Körner [Probl. Control Inform. Theory 2, 149-162 (1973; Zbl 0317.94025)] and also give a new method for constructing pairs of words with nonmaterializable mutual information.

MSC:

94A17	Measures of information, entropy
68Q30	Algorithmic information theory (Kolmogorov complexity, etc.)

Keywords:

mutual information; Kolmogorov complexity

Citations:

Zbl 0317.94025