Distancia de información

---

La distancia de información es la distancia entre dos objetos finitos (representados como archivos de computadora ) expresada como el número de bits en el programa más corto que transforma un objeto en otro o viceversa en unacomputadora universal . Ésta es una extensión de la complejidad de Kolmogorov . ^[1] La complejidad de Kolmogorov de un único objeto finito es la información de ese objeto; la distancia de información entre un par de objetos finitos es la información mínima necesaria para pasar de un objeto a otro o viceversa. La distancia de información se definió e investigó por primera vez en ^[2] basándose en la termodinámica.principios, ver también. ^[3] Posteriormente, alcanzó su forma final en. ^[4] Se aplica en la distancia de compresión normalizada y la distancia normalizada de Google .

Formalmente, la distancia de información entre y está definida por${\displaystyle ID(x,y)}$${\displaystyle x}$${\displaystyle y}$

con un programa binario finito para la computadora universal fija con como entradas cadenas binarias finitas . En ^[4] se demuestra que con${\displaystyle p}$${\displaystyle x,y}$${\displaystyle ID(x,y)=E(x,y)+O(\log \cdot \max\{K(x\mid y),K(y\mid x)\})}$

donde está la complejidad de Kolmogorov definida por ^[1] del tipo de prefijo. ^[5] Esta es la cantidad importante.${\displaystyle K(\cdot \mid \cdot )}$${\displaystyle E(x,y)}$

Sea la clase de distancias semicalculables superiores que satisfacen la condiciónde densidad .${\displaystyle \Delta}$ ${\displaystyle D(x,y)}$

Esto excluye distancias irrelevantes como por ; se encarga de que si la distancia crece, entonces crece el número de objetos dentro de esa distancia de un objeto determinado. Si entonces hasta un término aditivo constante. ^[4]Las expresiones probabilísticas de la distancia son la primera clase cohomológica en cohomología simétrica de información, ^[6] que puede concebirse como una propiedad de universalidad.${\displaystyle D(x,y)={\frac {1}{2}}}$${\displaystyle x\neq y}$${\displaystyle D\en \Delta }$${\displaystyle E(x,y)\leq D(x,y)}$

---