La constante de Chaitin (o número omega de Chaitin o probabilidad de parada) 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:
Historia
Gregory Chaitin, en los años 1960 y casi a la vez que Andréi 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 (sea cual sea la base elegida, todos los dígitos aparecen con igual frecuencia, como si hubieran sido generados mediante sucesivos lanzamientos de un dado).
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 u obtener los primeros dígitos, pero a partir de cierto decimal (que depende de la codificación elegida) no es posible conocer u obtener más.
Es un número real b-normal y algorítmicamente incompresible, o en una terminología equivalente es un número e 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.
constante, chaitin, constante, chaitin, número, omega, chaitin, probabilidad, parada, probabilidad, programa, elegido, azar, detenga, correctamente, máquina, turing, determinada, probabilidad, número, entre, conjunto, todos, programas, detienen, tamaño, bits, . La constante de Chaitin o numero omega de Chaitin o probabilidad de parada es la probabilidad de que un programa elegido al azar detenga correctamente una maquina de Turing determinada Al ser una probabilidad ha de ser un numero entre 0 y 1 Sea P el conjunto de todos los programas que se detienen y p el tamano en bits de un programa p W esta definida de la siguiente manera W p P 2 p displaystyle Omega sum p in P 2 p Historia EditarGregory Chaitin en los anos 1960 y casi a la vez que Andrei Kolmogorov establecio la siguiente definicion de objeto algoritmicamente aleatorio aquel imposible de ser generado por un programa mas corto que si mismo Tambien demostro que todo numero algoritmicamente aleatorio era normal sea cual sea la base elegida todos los digitos aparecen con igual frecuencia como si hubieran sido generados mediante sucesivos lanzamientos de un dado Recordemos que una maquina de Turing es un ordenador simple pero que con ella se pueden computar todas las tareas computables Propiedades EditarEsta constante no es computable Es posible conocer u obtener los primeros digitos pero a partir de cierto decimal que depende de la codificacion elegida no es posible conocer u obtener mas Es un numero real b normal y algoritmicamente incompresible o en una terminologia equivalente es un numero e algoritmicamente aleatorio Esto es decir bastante mas de lo que parece a simple vista Supone que no puede comprimirse en un programa mas breve que el mismo Un numero irracional como p o e a pesar de tener infinitos decimales no periodicos puede ser generado correctamente hasta el decimal enesimo por un programa de muy pocas lineas que ejecutado en un ordenador vaya escribiendo los sucesivos decimales Por lo tanto es comprimible y no es algoritmicamente aleatorio No solamente no se puede calcular este numero sino que nunca se pueden saber cuales son sus bits porque esa informacion como dijo Chaitin es matematicamente incompresible e incomprensible las palabras son muy semejantes Para obtener los n primeros bits de W se necesita una teoria de n bits de complejidad igual al fenomeno que se quiere estudiar Eso significa que no se gana nada razonando Existen programas muy cortos que generan p displaystyle pi con sus infinitos decimales luego la complejidad intrinseca inherente y propia del elemento de p es pequena no es algoritmicamente aleatorio El conjunto de Mandelbrot con sus recovecos infinitos y volutas bellisimas es generable tambien por programas muy cortos por lo tanto posee muy poca complejidad en el sentido de Kolmogorov Nuestro W no tiene estructura es puro azar a pesar de estar perfectamente definido Kolmogorov ha ideado el concepto de complejidad cantidad de informacion de un objeto como el numero de bits del programa mas conciso capaz de generarlo Vease tambien Editar Portal Matematica Contenido relacionado con Matematica Teoria de la computabilidad Complejidad computacional Maquina de Turing Datos Q735775Obtenido de https es wikipedia org w index php title Constante de Chaitin amp oldid 120774479, wikipedia, wiki, leyendo, leer, libro, biblioteca,
