La teoría de la información algorítmica es un campo de la informática que intenta capturar la esencia de la complejidad utilizando herramientas de la informática teórica. La idea principal es definir la complejidad (o complejidad descriptiva, complejidad de Kolmogorov, complejidad de Kolmogorov-Khaitin ) de una cadena como la longitud del programa más corto que genera una cadena determinada. Las líneas que pueden ser emitidas por programas cortos se consideran no muy complejas. Esta notación es sorprendentemente profunda y se puede utilizar para enunciar y probar la imposibilidad de ciertos resultados de la misma manera que lo hacen el teorema de incompletitud de Gödel y el problema colgante de Turing .
Esta región fue desarrollada por Kolmogorov , Ray Solomonoff y Gregory Khaitin a fines de década de 1960 Hay varias variantes de la complejidad de Kolmogorov o información algorítmica. El más utilizado se basa en programas autodelimitantes y sigue mayoritariamente a Leonid Levin (1974).
El principio de longitud mínima del mensaje (MLM para la inferencia estadística e inductiva y el aprendizaje automático fue desarrollado en 1968 por Wallace y DM Boulton MDS - Probabilidad bayesiana (incluye opiniones previas) e información-teórica. Tiene las propiedades deseadas de invariancia estadística (la inferencia se transforma con reparametrización, por ejemplo, de la misma manera que se realiza la conversión de coordenadas polares a coordenadas cartesianas), consistencia estadística (incluso para problemas muy complejos, el MDS convergerá a cualquier modelo subyacente ), y eficiencia (el modelo MDS convergerá a cualquier modelo subyacente verdadero lo más rápido posible). Christopher Wallace y DL Dowe mostraron una conexión formal entre MDS y la teoría algorítmica de la información (o complejidad de Kolmogorov) en 1999 .