Teoría algorítmica de la información

La teoría algorítmica de la información, es una teoría científica de las ciencias de la computación teórica, que en contraste con la clásica teoría de la información, se basa en la complejidad de Kolmogorov para la determinación del contenido de la información. Fue desarrollada principalmente por Gregory Chaitin, Andrey Kolmogorov y Ray Solomonoff.

Introducción

La teoría algorítmica de la información, principalmente estudios de las medidas de complejidad en las cadenas (o estructuras de datos). Como la mayoría de los objetos matemáticos pueden ser descritos en términos de cadenas, o como el límite de una secuencia de cadenas, puede ser usado para estudiar una amplia variedad de objetos matemáticos, incluyendo números enteros y números reales.

Algunos de los resultados de la teoría algorítmica de la información, como el teorema de incompletitud de Chaitin, parecen desafiar intuiciones matemáticas y filosóficas. El más notable de ellos es la construcción de la constante de Chaitin O, un número real que expresa la probabilidad de que una de máquina universal de Turing de auto-delimitación puede detenerse con datos de entrada generadas por lanzamientos de moneda.

Ejemplo

Según la definición clásica, de acuerdo con Claude Shannon, el contenido de la información de las siguientes secuencias binarias es la misma (sólo aplica la entropía de primer orden):

1000110111100101

1111111100000000

La primera secuencia ha sido producida por un muestreo aleatorio, en la segunda secuencia, sin embargo, se utiliza la instrucción "8x1 a continuación, y entonces 8X0". A los efectos de la teoría algorítmica de la información, la primera secuencia por tanto, tiene más información algorítmica , ya que es mucho más compleja o no se puede comprimir. Es decir, la información algorítmica es tanto mayor, cuanto menos puede ser comprimida una cadena de caracteres (entre otros, por compresión de datos). Las secuencias aleatorias y ruido blanco en general no contienen ningún patrón predecible y por tanto no son compresibles - el contenido de la información algorítmica es por tanto mayor.

Antecedentes Matemáticos

El enfoque de Andrei Kolmogorov se puede aplicar también a los algoritmos de programas arbitrarios de una máquina de Turing. Gregory Chaitin aplicando la complejidad de Kolmogorov en la teoría de las funciones recursivas (ver también µ-recursion cálculo lambda y el trabajo relacionado de Kurt Gödel), limita las aplicaciones posibles a las que se pueden ejecutar en una variante especial de la máquina universal de Turing (UTM), llamada máquina universal de Turing con autodelimitación.

Tras la demostración de Chaitin, en principio, no se puede determinar si una cadena se puede reducir aún más algoritmicamente. Por ejemplo, se han encontrado nuevos y más eficientes algoritmos de compresión, pero una secuencia aparentemente aleatoria de números puede venir de un generador pseudo-aleatorio. Debido al problema de el paro no todas las máquinas de Turing pueden ser utilizadas un tiempo finito.

Enlaces externos

• Cómo ejecutar algorítmica Teoría de la Información en un equipo por Gregory Chaitin(en inglés)
• Los límites de las matemáticas por Gregory Chaitin, incluyendo un intérprete para un extendido LISP para simular autolimitada UTM(en inglés)
• Mensajes de comprimido de los extranjeros idéntico al ruido
• Scholarpedia
• Günter Hotz: Algorithmic Information Theory (Parte 1) Informe Técnico FB14 -97-01 de la Universidad de Saarland, FB 14 ciencias de la computación, enero de 1997