• DocumentCode
    2237265
  • Title

    Independent minimum length programs to translate between given strings

  • Author

    Vereshchagin, Nikolai K. ; Vyugin, Michael V.

  • Author_Institution
    Moscow State Univ., Russia
  • fYear
    2000
  • fDate
    2000
  • Firstpage
    138
  • Lastpage
    144
  • Abstract
    A string p is called a program to compute y given x if U(p, x)=y, where U denotes universal programming language. Kolmogorov complexity K(y|z) of y relative to x is defined as minimum length of a program to compute y given x. Let K(x) denote K(x|empty string) (Kolmogorov complexity of x) and let I(x: y)=K(x)+K(y)-K(⟨x, y⟩) (the amount of mutual information in x, y). In the present paper we answer in negative the following question posed previously: Is it true that for any strings x, y there are independent minimum length programs p, q to translate between x, y, that is, is it true that for any x, y there are p, q such that U(p, x)=y, U(q, y)=x, the length of p is K(y|z), the length of q is K(z|y), and I(p:q)=O (where the last three equalities hold up to an additive O(log(K(x|y)+K(y|z))) term)?
  • Keywords
    computational complexity; computational geometry; Kolmogorov complexity; independent minimum length programs; mutual information; strings; universal programming language; Bismuth; Computer languages; DC generators; Electrical capacitance tomography; Mutual information;
  • fLanguage
    English
  • Publisher
    ieee
  • Conference_Titel
    Computational Complexity, 2000. Proceedings. 15th Annual IEEE Conference on
  • Conference_Location
    Florence
  • ISSN
    1093-0159
  • Print_ISBN
    0-7695-0674-7
  • Type

    conf

  • DOI
    10.1109/CCC.2000.856744
  • Filename
    856744