Antes de comentar sobre el tema, quiero hablar sobre esta susodicha constante.
Albert Einstein una vez dijo: Dios no juega a los dados. En si A. Einstein no le gustaba el azar, y creía en la existencia de variables ocultas, que es otra forma de decir que lo que parece azar no es sino falta de información por nuestra parte. En una visión superficial del asunto, alguien podría decir que la matemática acepta desde siempre el azar; al fin y al cabo tenemos la teoría de probabilidades aceptada y bien establecida desde hace mucho tiempo. Pero la cosa no es tan sencilla. La teoría de la probabilidad actual parte de la axiomatización de Kolmogorov, auxiliada por la teoría de la medida, y es un edificio muy bien construido; eso es cierto. Sin embargo, nada dice de el origen del azar, ni de la posibilidad de que tal azar sea desconocimiento por nuestra parte, existencia de variables ocultas, o que por el contrario sea parte integrante de la estructura de las cosas.
Cuando Hilbert formuló esta pregunta: Todo problema matemático tendría una solución algorítmica? En 1931, el matemático austríaco-alemán Kurt Gödel dio un paso fundamental para dar una respuesta cuando demuestra el celebrado Teorema de Incompletitud , ya hemos hablado de ello en este blog. Y fue Alan Turing en 1936 quien consigue dar la respuesta definitiva a la pregunta de Hilbert: No todo problema matemático tiene solución algorítmica. Para demostrarlo inventó la noción matemática de computadora de propósito general. Básicamente, Turing define la computadora y plantea un problema sobre ella para el cual demuestra que no hay ningún algoritmo que lo resuelva. Es el problema de la detención (en Inglés se llama “Halting problem”); informalmente ya lo conocen: es el problema de saber si un programa “se cuelga” cuando corre en la computadora. El problema de la detención es indecidible, como demostró Turing.
Ahora bien, Un matemático norteamericano de ascendencia argentina, Gregory Chaitin, pensó en este asunto en términos de azar. ¿Dónde entra el azar en todo esto? Pues muy fácil. De la imposibilidad dada por el teorema de Turing de resolver el problema de la detención, pasamos a preguntarnos por la probabilidad de parada de un algoritmo. Cada algoritmo es en definitiva una lista finita de ceros y unos. Con unos programas (los bien constituidos), la máquina se detendrá convenientemente, y con otros se quedará colgada. Supongamos que escribimos un programa a base de n ceros y unos tirando una moneda al aire n veces, existen 2^n programas posibles. Por lo tanto la probabilidad de obtener un programa concreto de n bits es 2^(-n). De todos estos programas, una parte muy pequeña acabarán en la instrucción “FIN DE PROGRAMA” correctamente. Y si extendemos a todos los programas posibles finitos obtenemos la constante Omega de Chaitin que figura al comienzo.
Donde P es el conjunto de todos los programas que finalizan correctamente y |p| es el tamaño en bits de esos programas. Esta constante es no computable. (ya que involucra al problema de la parada) pero es posible conocer sus primeros decimales. 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. 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 XX, 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). 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, Ω no tiene estructura: es puro azar a pesar de estar perfectamente definido.
Albert Einstein una vez dijo: Dios no juega a los dados. En si A. Einstein no le gustaba el azar, y creía en la existencia de variables ocultas, que es otra forma de decir que lo que parece azar no es sino falta de información por nuestra parte. En una visión superficial del asunto, alguien podría decir que la matemática acepta desde siempre el azar; al fin y al cabo tenemos la teoría de probabilidades aceptada y bien establecida desde hace mucho tiempo. Pero la cosa no es tan sencilla. La teoría de la probabilidad actual parte de la axiomatización de Kolmogorov, auxiliada por la teoría de la medida, y es un edificio muy bien construido; eso es cierto. Sin embargo, nada dice de el origen del azar, ni de la posibilidad de que tal azar sea desconocimiento por nuestra parte, existencia de variables ocultas, o que por el contrario sea parte integrante de la estructura de las cosas.
Cuando Hilbert formuló esta pregunta: Todo problema matemático tendría una solución algorítmica? En 1931, el matemático austríaco-alemán Kurt Gödel dio un paso fundamental para dar una respuesta cuando demuestra el celebrado Teorema de Incompletitud , ya hemos hablado de ello en este blog. Y fue Alan Turing en 1936 quien consigue dar la respuesta definitiva a la pregunta de Hilbert: No todo problema matemático tiene solución algorítmica. Para demostrarlo inventó la noción matemática de computadora de propósito general. Básicamente, Turing define la computadora y plantea un problema sobre ella para el cual demuestra que no hay ningún algoritmo que lo resuelva. Es el problema de la detención (en Inglés se llama “Halting problem”); informalmente ya lo conocen: es el problema de saber si un programa “se cuelga” cuando corre en la computadora. El problema de la detención es indecidible, como demostró Turing.
Ahora bien, Un matemático norteamericano de ascendencia argentina, Gregory Chaitin, pensó en este asunto en términos de azar. ¿Dónde entra el azar en todo esto? Pues muy fácil. De la imposibilidad dada por el teorema de Turing de resolver el problema de la detención, pasamos a preguntarnos por la probabilidad de parada de un algoritmo. Cada algoritmo es en definitiva una lista finita de ceros y unos. Con unos programas (los bien constituidos), la máquina se detendrá convenientemente, y con otros se quedará colgada. Supongamos que escribimos un programa a base de n ceros y unos tirando una moneda al aire n veces, existen 2^n programas posibles. Por lo tanto la probabilidad de obtener un programa concreto de n bits es 2^(-n). De todos estos programas, una parte muy pequeña acabarán en la instrucción “FIN DE PROGRAMA” correctamente. Y si extendemos a todos los programas posibles finitos obtenemos la constante Omega de Chaitin que figura al comienzo.
Donde P es el conjunto de todos los programas que finalizan correctamente y |p| es el tamaño en bits de esos programas. Esta constante es no computable. (ya que involucra al problema de la parada) pero es posible conocer sus primeros decimales. 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. 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 XX, 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). 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, Ω no tiene estructura: es puro azar a pesar de estar perfectamente definido.
