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 el cómputo y la información de objetos generados computacionalmente (en contraposición a los generados estocásticamente ), como cadenas o cualquier otra estructura de datos . En otras palabras, se muestra dentro de la teoría de la información algorítmica que la incompresibilidad computacional "imita" (excepto por 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 poner la teoría de la información de Shannon y la teoría de 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 objetos generados computacionalmente, 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 , 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 cuando se ejecuta en una máquina universal. [5]
La AIT estudia principalmente medidas de 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 transportada por objetos matemáticos como en el campo de las metamatemáticas , por ejemplo, como lo muestran los resultados de incompletitud mencionados 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, 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 las 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 .
De manera informal, desde el punto de vista de la teoría de la información algorítmica, 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 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, de la misma manera 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 clásica de la información, la teoría algorítmica de la información 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 universal de Turing 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 hasta una constante aditiva que depende solo 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 de la información algorítmica, como el teorema de incompletitud de Chaitin , parecen desafiar las intuiciones matemáticas y filosóficas comunes. El más notable entre ellos 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 autodelimitante se detenga cuando su entrada se suministra mediante lanzamientos de una moneda justa (a veces considerada como la probabilidad de que un programa informático aleatorio finalmente se detenga). 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 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 los dígitos de Ω no se pueden determinar, se conocen muchas propiedades de Ω ; por ejemplo, es una secuencia algorítmicamente aleatoria 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 basa el campo como parte de su invención de la probabilidad algorítmica , una forma de superar los graves problemas asociados con la aplicación de las reglas de Bayes en las estadísticas. Describió por primera vez sus resultados en una conferencia en Caltech en 1960, [8] y en un informe, 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 autodelimitadores 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). El 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 esos resultados a partir de un teorema correspondiente demostrado en el contexto 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ó 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 de 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 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 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 hablar (y a menudo se hace) de las propiedades de las cadenas aleatorias como un grupo sin tener que especificar primero una máquina universal.
Una secuencia binaria infinita se dice que 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, la colección de secuencias infinitas aleatorias no depende de la elección de la máquina universal (en contraste con 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. 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 otros alfabetos además del conjunto ).
La teoría de la información algorítmica (AIT) es la teoría de la información de objetos individuales, que utiliza la ciencia informática, y se ocupa de la relación entre la computación, la información y la aleatoriedad.
El contenido de información o la complejidad de un objeto se pueden medir por la longitud de su descripción más corta. Por ejemplo, la cadena
"0101010101010101010101010101010101010101010101010101010101010101"
tiene la descripción corta "32 repeticiones de '01'", mientras que
"1100100001100001110111101110110011111010010000100101011110010110"
Probablemente no tiene una descripción simple más allá de escribir la cadena en sí.
Más formalmente, la complejidad algorítmica (CA) 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.
Un concepto estrechamente relacionado es la probabilidad de que una computadora universal genere una cadena x cuando se le aplica un programa elegido al azar. Esta probabilidad algorítmica de "Solomonoff" (PA) es clave para abordar el viejo problema filosófico de la inducción de manera formal.
La principal desventaja de AC y AP es su incomputabilidad. La complejidad "Levin" limitada en el tiempo penaliza a un programa lento añadiendo el logaritmo de su tiempo de ejecución a su longitud. Esto conduce a variantes computables de AC y AP, y la búsqueda "Levin" universal (US) resuelve todos los problemas de inversión en un tiempo óptimo (aparte de alguna constante multiplicativa irrealmente grande).
La CA y la AP también permiten una definición formal y rigurosa de la aleatoriedad de cadenas individuales que no depende de intuiciones físicas o filosóficas sobre el no determinismo o la probabilidad. En términos generales, una cadena es aleatoria algorítmicamente "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 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}}: CS1 maint: varios nombres: lista de autores ( enlace )