Constante de Chaitin
De Wikipedia, la enciclopedia libre
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 un programa p, Ω está definida de la siguiente manera:
Esta constante no es computable. Es posible conocer los primeros decimales, pero a partir de cierto decimal (que depende de la codificación elegida) no es posible saber más decimales.
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 interior 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 Kolmogorov.
Nuestro Ω no tiene estructura: es puro azar a pesar de estar perfectamente definido.
Kolmogorov 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.
Chaitin definió un objeto es algorítmicamente aleatorio como aquel imposible de generar por un programa más corto que sí mismo en la década de los 60 del siglo pasado, prácticamente a la vez que Kolmogorov. Demostró que todo número algorítmicamente aleatorio era normal (sus dígitos aparecían con igual frecuencia en el desarrollo decimal, y en cualquier base).
Recordemos que una máquina de Turing es un ordenador simple, pero que con ella se pueden computar todas las tareas computables.
