« NetProLogo = NetLogo … « || Inicio || » Novedades en Yutzu »

Teoría Algorítmica de la Información

Última modificación: 3 de Diciembre de 2016, y ha tenido 265 vistas

Etiquetas utilizadas: || || || || ||

(Extraído del Prefacio escrito por G. Chaitin para la segunda edición del libro "Information and Randomness: An Algorithmic Perspective" de C. Calude)

La Teoría Algorítmica de la Información (AIT) 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 agitar vigorosamente. La idea básica consiste en medir la complejidad de un objeto por el tamaño en bits del menor programa que lo calcula.

La complejidad de longitud de programa (que es como a veces se llama a lo anterior) es un concepto mucho más profundo que la complejidad de tiempo de ejecución que, sin embargo, es de una gran importancia práctica en el diseño de algoritmos eficientes.

Las principales aplicaciones de la AIT se encuentran fundamentalmente en 2 áreas. En primer lugar, para dar una definición matemática de lo que significa que una cadena de bits no tenga patrones, sea aleatoria o no tenga estructura. De hecho, la mayoría de las cadenas de bits son algorítmicamente irreducibles, y por tanto aleatorias. Y, lo que es incluso más importante, la AIT arroja nueva luz sobre el fenómeno de incompletitud descubierto por Gödel. La AIT hace esto situando límites de Teoría de la Información sobre la potencia de cualquier Teoría Axiomática Formal. El nuevo punto de vista que proporciona la AIT sugiere que la incompletitud es natural y omnipresente, y que no puede ser eliminada del trabajo matemático de cada día.

Hay también conexiones entre la AIT y la física.

La medida de complejidad de longitud de programa es análoga al concepto de entropía de Boltzmann, que juega un papel clave en la mecánica estadística. Y los trabajos de Chaitin acerca del 10º problema de Hilbert haciendo uso de la AIT prueban no solo que Dios juega a los dados en la mecánica cuántica y en la dinámica no lineal, sino incluso en la Teoría de Números elemental. De esta forma, la AIT juega un papel determinante en los recientes esfuerzos de construir un puente entre las Ciencias de la Computación Teóricas y la Física Teórica.
En este sentido, una Máquina Universal de Turing es, desde un punto de vista físico, simplemente un sistema físico con un repertorio tan rico de posibles comportamientos que puede simular cualquier otro sistema físico. Este puente está también conectado con los recientes esfuerzos por parte de los físicos teóricos de comprender sistemas físicos complejos tales como los que podemos encontrar en la Biología.

« NetProLogo = NetLogo … « || Inicio || » Novedades en Yutzu »