Teoría de la información algorítmica

La teoría de la información algorítmica ( TIA ) es una rama de la informática teórica que se ocupa de la relación entre la computación y la información de objetos generados computacionalmente (a diferencia de los generados estocásticamente ), como cadenas o cualquier otra estructura de datos . En otras palabras, dentro de la teoría de la información algorítmica se demuestra que la incompresibilidad computacional "imita" (salvo una constante que solo depende del lenguaje de programación universal elegido) las relaciones o desigualdades que se encuentran en la teoría de la información . ^{[ 1 ]} Según Gregory Chaitin , es "el resultado de mezclar vigorosamente la teoría de la información de Shannon y la teoría de la computabilidad de Turing ". ^{[ 2 ]}

Además de la formalización de una medida universal para el contenido de información irreducible de objetos generados computacionalmente, algunos de los principales logros de la AIT fueron demostrar que: de hecho, la complejidad algorítmica sigue (en el caso autodelimitado ) las mismas desigualdades (excepto por una constante ^{[ 3 ]} ) que la entropía , como en la teoría de la información clásica; ^{[ 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 al ejecutarse en una máquina universal. ^{[ 5 ]}

La AIT estudia principalmente medidas del contenido de información irreducible de cadenas (u otras estructuras de datos ). Dado que la mayoría de los objetos matemáticos pueden describirse en términos de cadenas, o como el límite de una secuencia de cadenas, puede utilizarse para estudiar una amplia variedad de objetos matemáticos, incluidos los enteros . Una de las principales motivaciones de la AIT es el estudio mismo de la información que portan los objetos matemáticos, como en el campo de la metamatemática , por ejemplo, como lo demuestran los resultados de incompletitud mencionados a continuación. Otras motivaciones principales surgieron 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, se sabe que la AIT se fundamenta básicamente en tres conceptos matemáticos principales y las relaciones entre ellos: complejidad algorítmica , aleatoriedad algorítmica y probabilidad algorítmica . ^{[ 6 ] [ 4 ]}

La teoría de la información algorítmica estudia principalmente las medidas de complejidad en estructuras de datos , sobre todo cadenas de caracteres . Dado que la mayoría de los objetos matemáticos pueden describirse en términos de cadenas de caracteres, o como el límite de una secuencia de cadenas, puede utilizarse 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 de la información algorítmica, el contenido informativo de una cadena equivale a la longitud de la representación autocontenida más comprimida posible de dicha cadena. Una representación autocontenida es esencialmente un programa —escrito en un lenguaje de programación universal fijo pero irrelevante— que, al ejecutarse, genera la cadena original.

Desde este punto de vista, una enciclopedia de 3000 páginas contiene en realidad menos información que 3000 páginas de letras completamente aleatorias, a pesar de que la enciclopedia resulta mucho más útil. Esto se debe a que, para reconstruir la secuencia completa de letras aleatorias, habría que conocer cada una de ellas. Por otro lado, si se eliminaran todas las vocales de la enciclopedia, alguien con un conocimiento razonable del idioma inglés podría reconstruirla, del mismo modo que probablemente se podría reconstruir la frase "Ths sntnc hs lw nfrmtn cntnt" a partir del contexto y las consonantes presentes.

A diferencia de la teoría de la información clásica, la teoría de la información algorítmica proporciona definiciones formales y rigurosas de una cadena aleatoria y una secuencia infinita aleatoria que no dependen de intuiciones físicas o filosóficas sobre el no determinismo o la probabilidad . (El conjunto de cadenas aleatorias depende de la elección de la máquina de Turing universal utilizada para definir la complejidad de Kolmogorov , pero cualquier elección proporciona resultados asintóticos idénticos porque la complejidad de Kolmogorov de una cadena es invariante salvo por una constante aditiva que depende únicamente de la elección de la máquina de Turing universal. Por esta razón, el conjunto de secuencias infinitas aleatorias es independiente de la elección de la máquina universal).

Algunos resultados de la teoría de la información algorítmica, como el teorema de incompletitud de Chaitin , parecen desafiar las intuiciones matemáticas y filosóficas comunes. Entre ellos, destaca la construcción de la constante Ω de Chaitin , un número real que expresa la probabilidad de que una máquina de Turing universal autolimitante se detenga cuando su entrada se proporciona mediante lanzamientos de una moneda justa (a veces considerada como la probabilidad de que un programa informático aleatorio se detenga finalmente). Aunque Ω se define fácilmente, en cualquier teoría axiomatizable consistente solo se pueden calcular un número finito de dígitos de Ω , por lo que es, en cierto sentido , incognoscible , proporcionando un límite absoluto al conocimiento que recuerda a los teoremas de incompletitud de Gödel . Aunque los dígitos de Ω no se pueden determinar, se conocen muchas de sus propiedades ; por ejemplo, es una secuencia aleatoria algorítmica y, por lo tanto, sus dígitos binarios están distribuidos uniformemente (de hecho, es normal ).

La teoría de la información algorítmica fue fundada por Ray Solomonoff , ^{[ 7 ]} quien publicó las ideas básicas en las que se fundamenta el campo como parte de su invención de la probabilidad algorítmica , una forma de superar serios problemas asociados con la aplicación de las reglas de Bayes en estadística. Describió por primera vez sus resultados en una conferencia en Caltech en 1960, ^{[ 8 ]} y en un informe de febrero de 1960, "Un informe preliminar sobre una teoría general de la inferencia inductiva". ^{[ 9 ]} La teoría de la información algorítmica fue desarrollada posteriormente de forma independiente por Andrey Kolmogorov , en 1965, y Gregory Chaitin , alrededor de 1966.

Existen varias variantes de la complejidad de Kolmogorov o información algorítmica; la más utilizada se basa en programas autodelimitantes y se debe principalmente a Leonid Levin (1974). Per Martin-Löf también contribuyó significativamente a la teoría de la información de secuencias infinitas. Mark Burgin introdujo un enfoque axiomático de la teoría de la información algorítmica basado en los axiomas de Blum (Blum, 1967) en un artículo presentado para su publicación por Andrey Kolmogorov (Burgin, 1982). Este enfoque axiomático abarca otros enfoques de la teoría de la información algorítmica. Es posible tratar diferentes medidas de información algorítmica como casos particulares de medidas de información algorítmica definidas axiomáticamente. En lugar de demostrar teoremas similares, como el teorema de invariancia básica, para cada medida particular, es posible deducir fácilmente todos estos resultados a partir de un teorema correspondiente demostrado en el marco axiomático. Esta es una ventaja general del enfoque axiomático en matemáticas. El enfoque axiomático de la teoría de la información algorítmica se desarrolló aún más en el libro (Burgin 2005) y se aplicó a las métricas de software (Burgin y Debnath, 2003; Debnath y Burgin, 2003).

Se dice que una cadena binaria es aleatoria si su complejidad de Kolmogorov es al menos igual a su longitud. Un simple argumento de conteo demuestra que algunas cadenas de cualquier longitud son aleatorias, y casi todas se aproximan mucho a serlo. Dado que la complejidad de Kolmogorov depende de una máquina de Turing universal fija (o, informalmente, un lenguaje de descripción fijo en el que se proporcionan las descripciones), el conjunto de cadenas aleatorias sí depende de dicha máquina universal. Sin embargo, el conjunto de cadenas aleatorias, en su conjunto, posee propiedades similares independientemente de la máquina fija, por lo que se puede (y a menudo se hace) hablar de las propiedades de las cadenas aleatorias como un grupo sin necesidad de especificar previamente una máquina universal.

Se dice que una secuencia binaria infinita es aleatoria si, para alguna constante c , para todo n , la complejidad de Kolmogorov del segmento inicial de longitud n de la secuencia es al menos n  − c . Se puede demostrar que casi toda secuencia (desde el punto de vista de la medida estándar —«moneda justa» o medida de Lebesgue— en el espacio de secuencias binarias infinitas) es aleatoria. Además, dado que se puede demostrar que la complejidad de Kolmogorov relativa a dos máquinas universales diferentes difiere como máximo en una constante, el conjunto de secuencias infinitas aleatorias no depende de la elección de la máquina universal (a diferencia de las cadenas finitas). Esta definición de aleatoriedad se suele denominar aleatoriedad de Martin-Löf , en honor a Per Martin-Löf , para distinguirla de otras nociones similares de aleatoriedad. También se la denomina a veces 1-aleatoriedad para distinguirla de otras nociones más fuertes de aleatoriedad (2-aleatoriedad, 3-aleatoriedad, etc.). Además de los conceptos de aleatoriedad de Martin-Löf, también existen la aleatoriedad recursiva, la aleatoriedad de Schnorr y la aleatoriedad de Kurtz, etc. Yongge Wang demostró ^{[ 10 ]} que todos estos conceptos de aleatoriedad son diferentes. 

(Se pueden hacer definiciones relacionadas para alfabetos distintos del conjunto${\displaystyle \{0,1\}}$.)

La teoría de la información algorítmica (TIA) es la teoría de la información de los objetos individuales, que utiliza la informática, y se ocupa de la relación entre computación, información y aleatoriedad.

El contenido informativo o la complejidad de un objeto se puede medir por la longitud de su descripción más corta. Por ejemplo, la cadena

"0101010101010101010101010101010101010101010101010101010101010101"

tiene la breve descripción "32 repeticiones de '01'", mientras que

"1100100001100001110111101110110011111010010000100101011110010110"

Presumiblemente no tiene otra descripción sencilla que escribir la cadena de caracteres en sí.

De manera más formal, la complejidad algorítmica (CA) de una cadena x se define como la longitud del programa más corto que calcula o produce x , donde el programa se ejecuta en una computadora universal de referencia fija.

Un concepto estrechamente relacionado es la probabilidad de que una computadora universal genere una cadena x al ser alimentada con un programa elegido al azar. Esta probabilidad algorítmica de Solomonoff (PA) es fundamental para abordar formalmente el antiguo problema filosófico de la inducción.

El principal inconveniente de AC y AP es su incomputabilidad. La complejidad de Levin, limitada en tiempo, penaliza un programa lento sumando el logaritmo de su tiempo de ejecución a su longitud. Esto da lugar a variantes computables de AC y AP, y la búsqueda universal de Levin (US) resuelve todos los problemas de inversión en tiempo óptimo (salvo alguna constante multiplicativa irrealmente grande).

AC y AP también permiten una definición formal y rigurosa de la aleatoriedad de las cadenas individuales, sin depender de intuiciones físicas o filosóficas sobre el no determinismo o la probabilidad. En términos generales, una cadena es aleatoria "Martin-Löf" (AR) si es incompresible, en el sentido de que su complejidad algorítmica es igual a su longitud.

AC, AP y AR son las subdisciplinas centrales de AIT, pero AIT se extiende a muchas otras áreas. Sirve como base del principio de Longitud Mínima de Descripción (MDL), puede simplificar demostraciones en la teoría de la complejidad computacional , se ha utilizado para definir una métrica de similitud universal entre objetos, resuelve el problema del demonio de Maxwell y muchos otros.

• Teoría de la información algorítmica en Scholarpedia
• El relato de Chaitin sobre la historia de AIT .