Constante de Chaitin

Constante de Chaitin

La constante de Chaitin es la probabilidad de que un programa elegido al azar detenga correctamente una máquina de Turing determinada. Al ser una probabilidad ha de ser un número entre 0 y 1.

Sea P el conjunto de todos los programas que se detienen, y |p| el tamaño en bits de un programa p, Ω está definida de la siguiente manera:

\Omega = \sum_{p \in P} 2^{-|p|}

Historia

Chaitin, en la década de los 60 del Siglo XX y casi a la vez que Kolmogórov, estableció la siguiente definición de objeto algorítmicamente aleatorio: aquel imposible de ser generado por un programa más corto que sí mismo. También demostró que todo número algorítmicamente aleatorio era normal (en su desarrollo decimal, sea cual sea la base elegida, todos los dígitos aparecen con igual frecuencia).

Recordemos que una máquina de Turing es un ordenador simple, pero que con ella se pueden computar todas las tareas computables.

Propiedades

Esta constante no es computable. Es posible conocer los primeros dígitos, pero a partir de cierto decimal (que depende de la codificación elegida) no es posible obtener más.

Una de las características más importantes de este número es que es algorítmicamente aleatorio. Esto es decir bastante más de lo que parece a simple vista. Supone que no puede comprimirse en un programa más breve que él mismo. Un número irracional como π o e, a pesar de tener infinitos decimales no periódicos, puede ser generado correctamente hasta el decimal enésimo por un programa de muy pocas líneas que, ejecutado en un ordenador, vaya escribiendo los sucesivos decimales. Por lo tanto es comprimible, y no es algorítmicamente aleatorio.

No solamente no se puede calcular este número, sino que nunca se pueden saber cuáles son sus bits, porque esa información, como dijo Chaitin, "es matemáticamente incompresible e incomprensible, las palabras son muy semejantes. Para obtener los n primeros bits de Ω se necesita una teoría de n bits, de complejidad igual al fenómeno que se quiere estudiar. Eso significa que no se gana nada razonando".

Existen programas muy cortos que generan π con sus infinitos decimales, luego la complejidad intrínseca ( inherente y propia del elemento) de π es pequeña; no es algorítmicamente aleatorio. El conjunto de Mandelbrot, con sus recovecos infinitos y volutas bellísimas es generable también por programas muy cortos, por lo tanto posee muy poca complejidad en el sentido de Kolmogórov.

Nuestro Ω no tiene estructura: es puro azar a pesar de estar perfectamente definido.

Kolmogórov ha ideado el concepto de complejidad (cantidad de información) de un objeto como el número de bits del programa más conciso capaz de generarlo.

Véase también


Wikimedia foundation. 2010.

Игры ⚽ Нужно решить контрольную?

Mira otros diccionarios:

  • Constante de Chaitin — Oméga de Chaitin Dans le sous domaine de l’informatique qu’est la théorie algorithmique de l’information, une constante Oméga de Chaitin est un nombre réel, associé à un modèle de calcul ou à un langage de programmation donné, défini comme étant… …   Wikipédia en Français

  • Constante de Chaitin — La constante de Chaitin es un número entre 0 y 1. Es la probabilidad que un programa elegido al azar detenga correctamente a una máquina de Turing determinada. Sea P el conjunto de todos los programas que se detienen, y |p| el tamaño en bits de… …   Enciclopedia Universal

  • Chaitin — Gregory Chaitin Gregory Chaitin (1947 ) est un mathématicien et informaticien argentino américain. C est un spécialiste de l algorithmique. Biographie Dès la fin des années 1960, Chaitin fit d importantes contributions à la théorie algorithmique… …   Wikipédia en Français

  • Constante mathématique — Table de constantes mathématiques Cet article donne une liste de certaines constantes mathématiques. Typiquement, une constante en mathématique est un élément du corps des nombres réels ou des nombres complexes. À la différence des constantes… …   Wikipédia en Français

  • Constante Oméga — En mathématiques, la constante oméga, notée Ω, est une constante définie comme étant une valeur particulière de la fonction W de Lambert. Il ne faut pas la confondre avec l Oméga de Chaitin, constante mathématique en théorie algorithmique de… …   Wikipédia en Français

  • Constante omega — Constante oméga En mathématiques, la constante oméga, notée Ω, est une constante définie comme étant une valeur particulière de la fonction W de Lambert. Il ne faut pas la confondre avec l Oméga de Chaitin, constante mathématique en théorie… …   Wikipédia en Français

  • Constante oméga — En mathématiques, la constante oméga, notée Ω, est une constante définie comme étant une valeur particulière de la fonction W de Lambert. Il ne faut pas la confondre avec l Oméga de Chaitin, constante mathématique en théorie algorithmique de… …   Wikipédia en Français

  • Omega de Chaitin — Oméga de Chaitin Dans le sous domaine de l’informatique qu’est la théorie algorithmique de l’information, une constante Oméga de Chaitin est un nombre réel, associé à un modèle de calcul ou à un langage de programmation donné, défini comme étant… …   Wikipédia en Français

  • Oméga de chaitin — Dans le sous domaine de l’informatique qu’est la théorie algorithmique de l’information, une constante Oméga de Chaitin est un nombre réel, associé à un modèle de calcul ou à un langage de programmation donné, défini comme étant la probabilité… …   Wikipédia en Français

  • 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

Compartir el artículo y extractos

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