La teoría algorítmica de la información, es una teoría científica de las ciencias de la computación, que en contraste con la clásica teoría de la información, se basa en la complejidad de Kolmogórov para la determinación del contenido de la información. Fue desarrollada principalmente por Gregory Chaitin, Andréi Kolmogórov y Ray Solomonoff.

Introducción

La teoría algorítmica de la información, principalmente estudios de las medidas de complejidad en las cadenas (o estructuras de datos). Como la mayoría de los objetos matemáticos pueden ser descritos en términos de cadenas, o como el límite de una secuencia de cadenas, puede ser usado para estudiar una amplia variedad de objetos matemáticos, incluyendo números enteros y números reales.

Algunos de los resultados de la teoría algorítmica de la información, como el teorema de incompletitud de Chaitin, parecen desafiar intuiciones matemáticas y filosóficas. El más notable de ellos es la construcción de la constante de Chaitin Ω, un número real que expresa la probabilidad de que una de máquina universal de Turing de auto-delimitación puede detenerse con datos de entrada generadas por lanzamientos de moneda.

Ejemplo

Según la definición clásica, de acuerdo con Claude Shannon, el contenido de la información de las siguientes secuencias binarias es la misma (sólo aplica la entropía de primer orden):

1100100001100001110111101110110011111010010000100101011110010110

1111111111111111111111111111111100000000000000000000000000000000

La primera secuencia ha sido producida por un muestreo aleatorio, en la segunda secuencia, sin embargo, se utiliza la instrucción "32x1 a continuación, y entonces 32X0". A los efectos de la teoría algorítmica de la información, la primera secuencia por tanto, tiene más información algorítmica , ya que es mucho más compleja o no se puede comprimir. Es decir, la información algorítmica es tanto mayor, cuanto menos puede ser comprimida una cadena de caracteres (entre otros, por compresión de datos). Las secuencias aleatorias y ruido blanco en general no contienen ningún patrón predecible y por tanto no son compresibles - el contenido de la información algorítmica es por tanto mayor.

Antecedentes Matemáticos

El enfoque de Andrei Kolmogorov se puede aplicar también a los algoritmos de programas arbitrarios de una máquina de Turing. Gregory Chaitin aplicando la complejidad de Kolmogorov en la teoría de las funciones recursivas (ver también µ-recursion cálculo lambda y el trabajo relacionado de Kurt Gödel), limita las aplicaciones posibles a las que se pueden ejecutar en una variante especial de la máquina universal de Turing (UTM), llamada máquina universal de Turing con autodelimitación.

Tras la demostración de Chaitin, en principio, no se puede determinar si una cadena se puede reducir aún más algoritmicamente. Por ejemplo, se han encontrado nuevos y más eficientes algoritmos de compresión, pero una secuencia aparentemente aleatoria de números puede venir de un generador pseudo-aleatorio. Debido al problema de la parada no todas las máquinas de Turing pueden ser utilizadas un tiempo finito.