La teoría algorítmica de la información (AIT) es una rama de la informática teórica que se ocupa de la relación entre el cálculo y la información de los objetos generados computablemente (a diferencia de los generados estocásticamente ), como cadenas o cualquier otra estructura de datos . En otras palabras, se muestra dentro de la teoría algorítmica de la información que la incompresibilidad computacional "imita" (excepto por una constante que solo depende del lenguaje de programación universal elegido) las relaciones o desigualdades encontradas en la teoría de la información . [1] Según Gregory Chaitin , es "el resultado de ponerLa teoría de la información de Shannon y la teoría de la computabilidad de Turing en una coctelera y agitando vigorosamente ". [2]
Además de la formalización de una medida universal para el contenido de información irreductible de objetos generados computablemente, algunos de los principales logros de AIT fueron mostrar que: de hecho, la complejidad algorítmica sigue (en el caso auto-delimitado ) las mismas desigualdades (excepto por una constante [3]). ) que la entropía lo hace, como en la teoría clásica de la información; [1] la aleatoriedad es incompresibilidad; [4] y, dentro del ámbito del software generado aleatoriamente, la probabilidad de ocurrencia de cualquier estructura de datos es del orden del programa más corto que la genera cuando se ejecuta en una máquina universal. [5]
AIT estudia principalmente medidas de contenido de información irreductible de cadenas (u otras estructuras de datos ). Dado que la mayoría de los objetos matemáticos se pueden describir en términos de cadenas, o como el límite de una secuencia de cadenas, se puede utilizar para estudiar una amplia variedad de objetos matemáticos, incluidos los números enteros . Una de las principales motivaciones detrás de AIT es el estudio mismo de la información transportada por objetos matemáticos como en el campo de las metamatemáticas , por ejemplo, como lo demuestran los resultados de incompletitud que se mencionan a continuación. Otras motivaciones principales vinieron de: superar las limitaciones de la teoría de la información clásica para objetos únicos y fijos; formalizar el concepto de aleatoriedad; y encontrar una inferencia probabilística significativa sin conocimiento previo de la distribución de probabilidad (por ejemplo, si es independiente e idénticamente distribuida , markoviana o incluso estacionaria ). De esta manera, el AIT es conocido por ser básicamente fundada sobre tres principales conceptos matemáticos y las relaciones entre ellos: la complejidad algorítmica , aleatoriedad algorítmica , y la probabilidad algorítmica . [6] [4]
La teoría algorítmica de la información estudia principalmente medidas de complejidad en cadenas (u otras estructuras de datos ). Dado que la mayoría de los objetos matemáticos se pueden describir en términos de cadenas, o como el límite de una secuencia de cadenas, se puede utilizar para estudiar una amplia variedad de objetos matemáticos, incluidos los números enteros .
De manera informal, desde el punto de vista de la teoría algorítmica de la información, el contenido de información de una cadena es equivalente a la longitud de la representación autónoma más comprimida posible de esa cadena. Una representación autónoma es esencialmente un programa —en algún lenguaje de programación universal fijo pero por lo demás irrelevante— que, cuando se ejecuta, genera la cadena original.
Desde este punto de vista, una enciclopedia de 3000 páginas en realidad contiene menos información que 3000 páginas de letras completamente aleatorias, a pesar de que la enciclopedia es mucho más útil. Esto se debe a que para reconstruir la secuencia completa de letras aleatorias, uno debe saber qué es cada letra. Por otro lado, si se eliminaran todas las vocales de la enciclopedia, alguien con un conocimiento razonable del idioma inglés podría reconstruirlas, del mismo modo que probablemente se podría reconstruir la oración "Ths sntnc hs lw nfrmtn cnt" del contexto y las consonantes presentes.