Constante de Chaitin

Metáfora de la constante de Chaitin: un número omega de Chaitin es una secuencia de bits que representan, en forma concentrada, la solución al problema de la parada para todos los programas de una máquina de Turing universal dada.

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.

Other Languages