Investigación: Teoría Algorítmica de la Información

Introducción

La Teoría Algoritmica de la Información (AIT) es la teoría de la información de objetos individuales, haciendo uso de ciencias de la computación, y que se sitúa en relación con la computación, información y aleatoriedad.

El contenido informativo, o complejidad, de un objeto puede ser medido por la longitud de su menor descripción. Por ejemplo, la cadena

"0101010101010101010101010101010101010101010101010101010101010101"

tiene una descripción más corta que es "32 repeticiones de 01'", mientras que 

"1100100001100001110111101110110011111010010000100101011110010110"

presumiblemente no tiene una descripción más corta que la de dar la propia cadena. Más formalmente, la Complejidad Algorítmica de Kolmogorov (AC) de una cadena x se define como la longitud del menor programa que la calcula, o cuyo resultado es x, donde el programa se supone que corre sobre una instancia prefijada de máquina universal (u ordenador).

Una noción muy relacionada es la de la probabilidad de que una máquina universal devuelva x cuando recibe como entrada un programa elegido al azar. Esta Probabilidad Algorítmica de Solomonoff (AP) es clave para abordar el viejo problema filosófico de la inducción de una manera formal.

La principal desventaja que tienen la AC y la AP son su incomputabilidad. La complejidad de Tiempo Acotado de Levin penaliza los programas lentos añadiendo el logaritmo de su tiempo de ejecución a su longitud, lo que proporciona variantes computables de AC y AP, así como la Búsqueda Universal de Levin (US), que resuelve todos los problemas de inversión en tiempo óptimo (salvo una constante multiplicativa irrealísticamente enorme).

AC y AP también permiten un definición formal y rigurosa de aleatoriedad de cadenas individuales, que no depende de intuiciones físicas ni filosóficas sobre el no determinismo o similares. De manera informal, una cadena es Algorítmicamente Aleatoria según Martin-Loef (AR) si es incomprimible en el sentido de que su complejidad algorítmica es igual a su longitud.

AC, AP, y AR son las subdisciplinas nucleares de la AIT, pero ésta se divide en muchas otras áreas. Sirve como fundamento del Principio de Descripción de Longitud Mínima (MDL), que puede simplificar demostraciones en Teoría de la Complejidad Computacional, y ha sido usada para definir una métrica de similitud universal entre objetos, resolver el problema del Demonio de Maxwell y muchos otros..

Complejidad Algorítmica de "Kolmogorov" (AC)

La Complejidad Algorítmica formaliza las nociones de simplicidad y complejidad. Intuitivamente, una cadena es simple si se puede describir en pocas palabras, algo así como "la cadena de un millón de 1's", y es compleja si no tiene una descripción así, como una cadena aleatoria, cuya mejor descripción consiste en dar cada bit literalmente. Normalmente, uno está interesado únicamente en aquellas descrpiciones, o codificaciones,  que son efectivas en el sentido de que los decodificadores son algoritmos sobre algún ordenador. La Máquina de Turing Universal es un modelo abstracto estándar de un ordenador de propósito general en Ciencias de la Computación Teórica. Decimos que un programa p es una descripción de una cadena, x, si ejecutando p en U (máquina de Turing Universal) se obtiene x, es decir \(U(p)=x\). La longitud de la menor descripción se denota por \[K(x)=min \{l(p):U(p)=x\}\]

donde l(p) es la longitud de p medida en bits. Se puede proba que esta definición es independiente de la elección de U en el sentido de que K(x) cambia a lo sumo por una constante aditiva independiente de x.

Puedes encontrar más información aquí.