• A
  • A
  • A
  • ABC
  • ABC
  • ABC
  • А
  • А
  • А
  • А
  • А
Regular version of the site

Article

Proofs of conservation inequalities for Levin's notion of mutual information of 1974

Theoretical Computer Science. 2021. Vol. 856. P. 14-20.

In this paper we consider Levin's notion of mutual information in infinite 0-1-sequences, as defined in Levin (1974) [6]. The respective information conservation inequalities were stated in that paper without proofs. Later some proofs appeared in the literature, however no proof of the probabilistic conservation inequality has been published yet. In this paper we prove that inequality and for the sake of completeness we present also short proofs of other properties of the said notion.