Distance d'information

Alors que la complexité de Kolmogorov (1965) est la mesure absolue acceptée du contenu informationnel dans un objet fini individuel, une notion tout aussi absolue est nécessaire pour la distance d'information entre deux objets individuels, par exemple, deux images. Nous proposons plusieurs définitions naturelles d'une métrique d'information universelle, basée sur la longueur des plus courts programmes pour des calculs ordinaires ou des calculs réversibles (sans dissipation). Il s'avère que ces définitions sont équivalentes jusqu'à un terme logarithmique additif. Nous montrons que la distance d'information est une distance universelle de similarité cognitive. Nous examinons la corrélation maximale des plus courts programmes impliqués, la décorrélation maximale des programmes (une généralisation du théorème de Slepian-Wolf de la théorie de l'information classique), et les propriétés de densité des espaces métriques discrets induits par les distances d'information. Une distance connexe mesure la quantité de non-réversibilité d'un calcul. En utilisant la théorie physique du calcul réversible, nous donnons une mesure appropriée (universelle, antisymétrique et transitive) du travail thermodynamique requis pour transformer un objet en un autre objet par le processus le plus efficace. La distance d'information entre objets individuels est nécessaire en reconnaissance de formes où l'on souhaite exprimer des notions efficaces de "similarité de motif" ou "similarité cognitive" entre des objets individuels et dans la thermodynamique du calcul où l'on souhaite analyser la dissipation d'énergie d'un calcul d'une entrée particulière à une sortie particulière.