La teoría de la información algorítmica (AIT) 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 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 una constante que sólo 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 poner la teoría de la información de Shannon y la teoría de la computabilidad de Turing en una coctelera y agitarla vigorosamente". [2]
Además de la formalización de una medida universal para el contenido de información irreducible de los objetos generados computablemente, algunos de los principales logros de la AIT fueron mostrar que: de hecho, la complejidad algorítmica sigue (en el caso autodelimitado ) las mismas desigualdades (excepto por una constante [3] ) que la entropía sí, 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 que ocurra 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 del contenido de información irreducible de cadenas (u otras estructuras de datos ). Debido a 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 la AIT es el estudio mismo de la información que contienen los objetos matemáticos como en el campo de las metamatemáticas , por ejemplo, como lo muestran los resultados de incompletitud que se mencionan 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 estacionario ). De esta manera, se sabe que la AIT se basa 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 medidas de complejidad en cadenas (u otras estructuras de datos ). Debido a 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 .
Informalmente, 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 irrelevante ) que, cuando se ejecuta, 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 es mucho más útil. Esto se debe a que para reconstruir la secuencia completa de letras aleatorias, es necesario 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 cntnt" a partir del contexto y las consonantes presentes.
A diferencia de la teoría de la información clásica, la teoría algorítmica de la información ofrece definiciones formales y rigurosas de una cadena aleatoria y una secuencia aleatoria infinita 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 universal de Turing utilizada para definir la complejidad de Kolmogorov , pero cualquier elección da resultados asintóticos idénticos porque la complejidad Kolmogorov de una cadena es invariante hasta una constante aditiva que depende únicamente de la elección de la máquina universal de Turing. Por esta razón el conjunto de secuencias infinitas aleatorias es independiente de la elección de la máquina universal).
Algunos de los resultados de la teoría algorítmica de la información, como el teorema de incompletitud de Chaitin , parecen desafiar las intuiciones matemáticas y filosóficas comunes. La más notable entre ellas es la construcción de la constante Ω de Chaitin , un número real que expresa la probabilidad de que una máquina de Turing universal autodelimitada se detenga cuando su entrada sea suministrada por el lanzamiento de una moneda justa (a veces considerada como la probabilidad de que una máquina aleatoria el programa informático eventualmente se detendrá). Aunque Ω se define fácilmente, en cualquier teoría axiomatizable consistente sólo se pueden calcular un número finito de dígitos de Ω , por lo que en cierto sentido es incognoscible , lo que proporciona un límite absoluto al conocimiento que recuerda a los teoremas de incompletitud de Gödel . Aunque no se pueden determinar los dígitos de Ω , se conocen muchas propiedades de Ω ; por ejemplo, es una secuencia algorítmicamente aleatoria y, por tanto, sus dígitos binarios están distribuidos uniformemente (de hecho, es normal ).
La teoría algorítmica de la información fue fundada por Ray Solomonoff , [7] quien publicó las ideas básicas en las que se basa 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ó sus resultados por primera vez 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 algorítmica de la información 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; el más utilizado 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 algorítmica de la información basado en los axiomas de Blum (Blum 1967) en un artículo presentado para su publicación por Andrey Kolmogorov (Burgin 1982). El enfoque axiomático abarca otros enfoques de la teoría algorítmica de la información. 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 básico de invariancia, para cada medida particular, es posible deducir fácilmente todos esos resultados a partir de un teorema correspondiente demostrado en el marco axiomático. Ésta es una ventaja general del enfoque axiomático en matemáticas. El enfoque axiomático de la teoría algorítmica de la información se desarrolló 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 la complejidad Kolmogorov de la cadena es al menos la longitud de la cadena. Un argumento de conteo simple muestra que algunas cadenas de cualquier longitud dada son aleatorias, y casi todas las cadenas están muy cerca de ser aleatorias. Dado que la complejidad de Kolmogorov depende de una elección fija de la máquina universal de Turing (informalmente, un "lenguaje de descripción" fijo en el que se dan las "descripciones"), la colección de cadenas aleatorias sí depende de la elección de la máquina universal fija. Sin embargo, la colección de cadenas aleatorias, en su conjunto, tiene 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 tener que especificar primero 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 infinitas secuencias binarias) 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, la colección 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 suele denominarse aleatoriedad de Martin-Löf , en honor a Per Martin-Löf , para distinguirla de otras nociones similares de aleatoriedad. A veces también se le llama 1-aleatoriedad para distinguirlo 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 aleatoriedad recursiva, aleatoriedad de Schnorr y 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 ).
La teoría algorítmica de la información (AIT) es la teoría de la información de objetos individuales, que utiliza la informática y se ocupa de la relación entre computación, información y aleatoriedad.
El contenido de información 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 una descripción simple más que escribir la cadena misma.
Más formalmente, la complejidad algorítmica (AC) de una cadena x se define como la longitud del programa más corto que calcula o genera x , donde el programa se ejecuta en alguna computadora universal de referencia fija.
Una noción estrechamente relacionada es la probabilidad de que una computadora universal genere alguna cadena x cuando se alimenta con un programa elegido al azar. Esta probabilidad algorítmica "Solomonoff" (AP) es clave para abordar el viejo problema filosófico de la inducción de una manera formal.
El principal inconveniente de AC y AP es su incomputabilidad. La complejidad "Levin" limitada en el tiempo penaliza un programa lento sumando el logaritmo de su tiempo de ejecución a su duración. Esto conduce a variantes computables de AC y AP, y la búsqueda universal "Levin" (US) resuelve todos los problemas de inversión en un tiempo óptimo (aparte de alguna constante multiplicativa irrealmente grande).
AC y AP también permiten una definición formal y rigurosa de aleatoriedad de cadenas individuales para no depender de intuiciones físicas o filosóficas sobre el no determinismo o la probabilidad. En términos generales, una cadena es algorítmica 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 principales 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 las pruebas 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.
{{cite journal}}: Mantenimiento CS1: varios nombres: lista de autores ( enlace )