Teoría algorítmica de la información

Mark Burgin (2023), glossaLAB, 5(1): 8288

Curador
{{#var:curador}}
Autor(s)
{{#var:autor}}

La teoría algorítmica de la información se basa en el concepto de complejidad de Kolmogorov o algorítmica de los objetos, ofreciendo métodos para la medida de la información intrínseca relacionada con los objetos a través de la longitud de su descripción algorítmica (v. también información algorítmica). Esta medida fue introducida y estudiada por tres autores: Ray Solomonoff (1964), Andrey Kolmogorov (1965) and Gregory Chaitin (1966).

Perspectivas

La aproximación algorítmica explica una propiedad fundamental de la información que la vincula con los medios empleados para acceder a ella o utilizarla. Desde esta punto de vista, la información no se considera como una propiedad inherente de diferentes objetos, sino relacionada con los algoritmos que usan, extraen o producen información. En este contexto, un sistema (persona) con algoritmos más potentes para la extracción y gestión de la información puede lograr más información desde el mismo portador de información y usa mejor esta información que el sistema que dispone de algoritmos más pobres y capacidades más limitadas. Esto se encuentra alineado a la comprensión convencional de la noción de información. Así, el sistema (persona) que dispone de un código C puede leer textos codificados en C, mientras que aquellos que no disponen de dicho código con pueden leer tales textos. Como resultado, la eficiencia o complejidad de los algoritmos se convierte en una medida de la información en contraste con la aproximación tradicional según la cual la información es tratada como incertidumbre o diversidad. Eficiencia es el problema clave y una característica fundamental de cualquier actividad. Consecuentemente, las medidas de la eficiencia y complejidad proveen medios para la medida de la información como una esencia dinámica.

La teoría algorítmica de la información ha sido aplicada a un amplio rango de áreas, incluida la teoría de la computación, combinatoria, medicina, biología, neurofisiología, física, economía, ingeniería de hardware y software, teoría de la probabilidad, estadística, razonamiento inductivo y aprendizaje automático.

Objetos y sistemas simbólicos

Los Objetos en la teoría algorítmica de la información son cadenas de símbolos, ya que la representación más habitual de la información recurre a símbolos y, por otra parte, es posible representar otras estructuras codificadas mediante cadenas de símbolos. Resulta natural interpretar dichas cadenas como caracteres o textos en algún lenguaje. Esto supone que la información es presentada y procesada en forma simbólica y todos los modelos son representados por sus modelos simbólicos (semióticos) (®símbolo). Los modelos exactos tienen una estructura matemática. La principal cuestión es cuánta información necesitamos para reconstruir (computar) una cadena determinada (palabra). Así, la aproximación tradicional en la teoría algorítmica de la información solamente trata información simbólica. Esta cuestión relaciona la información con la complejidad porque la medida de la información necesaria aparece aquí como una medida de la complejidad de la reconstrucción de la cadena.

El sentido reconstructivo de la información algorítmica

La Reconstrucción/computación de una cadena de símbolos es una acción que es realizada como un proceso. Su complejidad depende de los medios utilizados para hacer la reconstrucción. Para precisar esta idea se recurre al concepto de algoritmo. Esto es, las cadenas son reconstruidas por algoritmos. Los algoritmos operan en el dominio de cadenas y este dominio usualmente contiene todas las cadenas finitas de algún alfabeto. En este contexto, un algoritmo (también puede hablarse de autómata o computador) usa una cadena de símbolos z y eventualmente produce otra cadena x, como se representa en la siguiente figura.

Cadenas de símbolos de entrada y salida de un sistema algorítmico. x: objeto de reconstrucción, z: información necesaria para la reconstrucción de x por parte del sistema algorítmico.

La cadena de entrada es una portadora de información relativa a la cadena de salida, es decir, la cadena que vamos a reconstruir/computar. Es posible considerar la cadena de entrada z como el programa que ha sido entregado al algoritmo/máquina para la computación de x. Este programa provee información sobre x para un algoritmo (dispositivo computacional). De esta manera los investigadores llegan a la medida de la información (complejidad) de una cadena de símbolos, que constituye el concepto fundamental de la teoría. Obsérvese que con frecuencia al contenido informacional de una cadena se lo denomina complejidad de Kolmogorov. Es decir, el contenido informacional C(x) de una cadena x es la cantidad mínima de información requerida para reconstruir la cadena. En la aproximación convencional, dicha cantidad de la entrada de información es medida por el tamaño de la portadora de información y, como las portadoras son cadenas de símbolos, el volumen de una cadena z es la longitud l(z) de dicha cadena. Así, la longitud del programa más corto para el cálculo de la cadena de salida x nos indica la medida de la información necesaria para reconstruir/computar esta cadena.

Versiones de la medida de la información algorítmica

Aunque la medida de la información antes referida es la más popular en la teoría algorítmica de la información, se han introducido otras versiones de medida algorítmica de la información, siendo las más conocidas:

Complejidad uniforme KR(x) Complejidad autodelimitada (o libre de prefijo) K(x) Complejidad monótona Km(x) Complejidad condicional de Kolmogorov CD(x) Complejidad de Kolmogorov temporalmente acotada C^t(x) Complejidad de Kolmogorov espacialmente acotada C^s(x) Complejidad de Kolmogorov acotada por recursos C^t,s(x) Adicionalmente, la teoría de la información algorítmica ha sido extendida a procesos infinitos, palabras infinitas (Chaitin, 1976; 1977), ® algoritmos super-recursivos (Burgin, 1995, 2005, 2016c; Schmidhuber, 2002) y computación cuántica (Svozil, 1996; Vitanyi, 1999; 2001). Cada nuevo desarrollo de la teoría algorítmica de la información ha estado vinculada a la consideración de diferentes clases de algoritmos como medios de adquisición, procesado y utilización. En principio, solo las clases sub-recursivas (es decir, subclases de la clase de todas las máquinas de Turing, tales como la clase de todas las máquinas de Turing autolimitadas) han sido usadas con este propósito. Posteriormente, ®algoritmos super-recursivos más potentes, tales como máquinas de Turing inductivas han sido aplicadas al estudio de la información algorítmica (Burgin, 2016).

La existencia de una gran variedad de aproximaciones y medidas algorítmicas de la información ha dado lugar a la necesidad de una aproximación unificada, la cual ha sido introducida y desarrollada por Burgin bajo la denominación de teoría axiomática de la información (Burgin 1982; 1990; 2005; 2010).

Sentido de la información común vs algorítmico: objeto vs portador de información

Un problema esencia en torno a la complejidad algorítmica como medida de la información está relacionado con la información info-teorética. Se asume de un modo general que la complejidad algorítmica de una cadena binaria x mide la cantidad de información en dicha cadena. Así, de acuerdo a la teoría algorítmica de la información, las secuencias aleatorias tendrían una complejidad máxima en cuanto a que por definición una secuencia aleatoria no puede tener un algoritmo generador que sea más corto que la simple reproducción literal de la secuencia. Esto supone que el contenido informacional de una secuencia aleatoria es máxima.

Algunos físicos fueron los primeros en llamar la atención respecto a esta peculiaridad. Por ejemplo, Richard Feyman (1999) escribió:

"¿Cómo es posible que una cadena aleatoria contenga alguna información, por no hablar de que su cantidad sea máxima? ¡Seguramente debemos estar usando una definición incorrecta de ‘información’!..."

Para eliminar estas contradicciones y discrepancias frecuentes en la teoría algorítmica de la información y para resolver el problema de la comprensión correcta del significado de la función C(x), resulta más adecuado considerar C(x) y todas sus versiones como medidas de información acerca de x o la cantidad de información de x con el objetivo específico de construir o reconstruir x. Esto significa que en realidad x no sea la portadora de información medida por C(x), sino el objeto de esta información. Así, no sorprende que algunas personas o máquinas requieran más información respecto a una secuencia aleatoria con objeto de reconstruirla que acerca de una obra de arte, tal como un poema de Dante o una novela de Cervantes.

Aspector temporales y semióticos de la información algorítmica con respecto a otros sentidos de información

Con objeto de reconciliar el sentido común acerca de la información con el que proporciona la teoría algorítmica de la información, resulta fructífera la distinción temporal entre información potencial y actual introducida por Weizsäcker (1984) (Lyre, 2002). En nuestro caso, mientras la portadora z antes mencionada representa información potencial (e.d. la posibilidad de reconstruir x), el objeto de información x representa información actual cuando el sistema algorítmico la ha reconstruido en efecto. Mediante una abstracción de los recursos algorítmicos y en consecuencia vinculándolo a recursos supuestamente óptimos, se pierde la especificidad de z respecto a a un sistema algorítmico dado y solo prevalece el objetivo de reconstrucción, x. Desde este punto de vista la información algorítmica puede verse como información actual. Por el contrario, el concepto de información provisto por la Teoría Matemática de la Información (TMC), la entropía informacional, se refiere exclusivamente al grado de incertidumbre en el receptor antes de ser informado, es decir, abstrayendo el resultado de recepción específico. Esto muestra que la entropía informacional ofrece un caracter fundamentalmente potencial, complementario al de la información algorítmica.

La distinción semiótica entre aspectos sintácticos y semánticos permite captar otras diferencias relevantes entre la información algorítmica y otros sentidos del concepto de información. Según Lyre (2002) la información algorítmica - a diferencia de la información Shanonniana - refleja a la vez aspectos semánticos y sintácticos: "El contenido de información algorítmica mide la información actual bajo aspectos tanto sintácticos como semánticos" (Lyre 2002, p. 38). En nuestro contexto, x puede ser contemplado como el valor semántico de la información o proceso (obsérvese que x puede ser tanto un conjunto de operaciones con un efecto particular sobre el entorno, por ejemplo, un proceso de fabricación, por tanto, refleja no solo aspectos semánticos sino también pragmáticos), mientras que z representa su valor sintáctico. En la forma invariante de la información algorítmica, z corresponde a los recursos sintácticos mínimos para referir la semántica del objeto representado por x. Por el contrario, es bien sabido que la TMC restringe programáticamente la información a su dimensión sintáctica.

Estas mismas dimensiones son empleadas en los sentidos corrientes de información. Cuando consideramos que necesitamos información, esta es contemplada de un modo potencial. Mientras que cuando decimos que tenmos la información que alguien necesita, esta es contemplada en su valor actual, aunque de lo que realmente disponemos es de un z que eventualmente podría compartirse, y suponemos que el destinatario dispone de los recursos algorítmicos (al igual que nosotros) para reconstruir un cierto x, por el que -por algún motivo- está interesado. Así, disponer de z es prácticamente equivalente a tener x. Aunque normalmente no se formula de esa manera, resulta claro que z tiene un valor sintáctico mientras que x lo tiene semántico.

Referencias

• BURGIN, M. (1982) Generalized Kolmogorov complexity and duality in theory of computations, Soviet Math. Dokl., v.25, No. 3, pp. 19–23
• BURGIN, M. (1990) Generalized Kolmogorov Complexity and other Dual Complexity Measures, Cybernetics, No. 4, pp. 21–29
• BURGIN, M. Super-recursive algorithms, Monographs in computer science, Springer, 2005
• BURGIN, Mark (2010). Theory of Information: Fundamentality, Diversity and Unification. Singapore: World Scientific Publishing
• CHAITIN, Gregory J. (1969). "On the Simplicity and Speed of Programs for Computing Infinite Sets of Natural Numbers" (PDF). Journal of the ACM 16: 407.
• CHAITIN, G.J. Algorithmic Information Theory, Cambridge University Press, Cambridge, 1987
• KOLMOGOROV, A.N. (1965). "Three Approaches to the Quantitative Definition of Information". Problems Inform. Transmission 1 (1): 1–7.
• LYRE, H. (2002). Inforsmationstheorie. Munich: Wilhelm Fink Verlag
• SOLOMONOFF, Ray (March 1964). "A Formal Theory of Inductive Inference Part I". Information and Control 7 (1): 1–22.
• SOLOMONOFF, Ray (June 1964). "A Formal Theory of Inductive Inference Part II". Information and Control 7 (2): 224–254.
• WEIZSÄCKER, C.F. (1985). Aufbau der Physik. Munich: Hanser

Recursos Online

NA