Information distance

Information distance is the distance between two finite objects (represented as computer files) expressed as the number of bits in the shortest program which transforms one object into the other one or vice versa on a universal computer. This is an extension of Kolmogorov complexity.[1] The Kolmogorov complexity of a single finite object is the information in that object; the information distance between a pair of finite objects is the minimum information required to go from one object to the other or vice versa. Information distance was first defined and investigated in [2] based on thermodynamic principles, see also.[3] Subsequently, it achieved final form in.[4] It is applied in the normalized compression distance and the normalized Google distance.

  1. ^ A.N. Kolmogorov, Three approaches to the quantitative definition of information, Problems Inform. Transmission, 1:1(1965), 1–7
  2. ^ M. Li, P.M.B. Vitanyi, Theory of Thermodynamics of Computation, Proc. IEEE Physics of Computation Workshop, Dallas, Texas, USA, 1992, 42–46
  3. ^ M. Li, P.M.B. Vitanyi, Reversibility and Adiabatic Computation: Trading Time and Space for Energy, Proc. R. Soc. Lond. A 9 April 1996 vol. 452 no. 1947 769–789
  4. ^ C.H. Bennett, P. Gacs, M. Li, P.M.B. Vitanyi, W. Zurek, Information distance, IEEE Transactions on Information Theory, 44:4(1998), 1407–1423