Teoría algorítmica de la información

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.

Contenido

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


Wikimedia foundation. 2010.

Игры ⚽ Поможем сделать НИР

Mira otros diccionarios:

  • Teoría de la computación — La teoría de la computación es una rama de la matemática y la computación que centra su interés en las limitaciones y capacidades fundamentales de las computadoras. Específicamente esta teoría busca modelos matemáticos que formalizan el concepto… …   Wikipedia Español

  • Teoría de la información — Este artículo está siendo desarrollado y forma parte de un proyecto educativo. Es posible que a causa de ello haya lagunas de contenido o deficiencias de formato. Si quieres puedes ayudar y editar, pero por favor antes de realizar correcciones… …   Wikipedia Español

  • Teorema de la invariancia (teoría de la información) — En la teoría algorítmica de la información, el teorema de invariancia, inicialmente probado por Ray Solomonoff, establece que una máquina universal de Turing proporciona un medio óptimo de la descripción, salvo una constante aditiva. Formalmente …   Wikipedia Español

  • Teoría de subasta — Esta página o sección está siendo traducida del idioma inglés a partir del artículo Auction theory, razón por la cual puede haber lagunas de contenidos, errores sintácticos o escritos sin traducir. Puedes colaborar con Wikipedia …   Wikipedia Español

  • Gregory Chaitin — Gregory J. Chaitin (nacido en Nueva York en 1947) es un matemático y científico de la computación estadounidense nacionalizado argentino. Contenido 1 Biografía 2 Bibliografía (en inglés) 3 Referencias …   Wikipedia Español

  • Teoremas de incompletitud de Gödel — Kurt Gödel a los 19 años de edad, cinco años antes de la demostración de los teoremas. Los teoremas de incompletitud de Gödel son dos célebres teoremas de lógica matemática demostrados por Kurt Gödel en 1930. Ambos están relacionados con la… …   Wikipedia Español

  • Historia de la aleatoriedad — Fresco antiguo de unos jugadores de dados En la historia antigua, los conceptos de oportunidad y azar estaban entrelazados con el del destino. Muchos pueblos antiguos tiraban dados para determinar el destino, y estos se volvieron más tarde los… …   Wikipedia Español

  • Aleatoriedad — Puntos esparcidos aleatoriamente sobre un plano bidimensional. Sus puntos más cercanos están resaltados en rojo. La aleatoriedad es un c …   Wikipedia Español

  • Andréi Kolmogórov — Andréi Kolmogórov. Andréi Nikoláyevich Kolmogórov (Андрей Николаевич Колмогоров) (Tambov, 25 de abril de 1903 Moscú, 20 de octubre de 1987) fue un matemático ruso que hizo progresos importantes en los campos de la teoría de la probabilidad y de… …   Wikipedia Español

  • Comentario (informática) — Este artículo o sección necesita referencias que aparezcan en una publicación acreditada, como revistas especializadas, monografías, prensa diaria o páginas de Internet fidedignas. Puedes añadirlas así o avisar …   Wikipedia Español

Compartir el artículo y extractos

Link directo
Do a right-click on the link above
and select “Copy Link”