En el subcampo informático de la teoría algorítmica de la información , una constante de Chaitin ( número omega de Chaitin ) [1] o probabilidad de detención es un número real que, informalmente hablando, representa la probabilidad de que un programa construido aleatoriamente se detenga. Estos números están formados a partir de una construcción debida a Gregory Chaitin .
Aunque existen infinitas probabilidades de detención, una para cada método de codificación de programas, es común utilizar la letra Ω para referirse a ellas como si solo existiera una. Debido a que Ω depende de la codificación del programa utilizado, a veces se le llama construcción de Chaitin cuando no se refiere a ninguna codificación específica.
Cada probabilidad de detención es un número real normal y trascendental que no es computable , lo que significa que no existe ningún algoritmo para calcular sus dígitos. Cada probabilidad de detención es aleatoria de Martin-Löf , lo que significa que ni siquiera existe ningún algoritmo que pueda adivinar de manera confiable sus dígitos.
La definición de probabilidad de detención se basa en la existencia de una función computable universal sin prefijos. Tal función, intuitivamente, representa un lenguaje de programación con la propiedad de que ningún programa válido puede obtenerse como una extensión adecuada de otro programa válido.
Supongamos que F es una función parcial que toma un argumento, una cadena binaria finita, y posiblemente devuelve una única cadena binaria como salida. La función F se llama computable si hay una máquina de Turing que la calcula, en el sentido de que para cualquier cadena binaria finita x e y, F(x) = y si y sólo si la máquina de Turing se detiene con y en su cinta cuando se le da la entrada x .
La función F se llama universal si se cumple la siguiente propiedad: para cada función computable f de una sola variable hay una cadena w tal que para todo x , F ( w x ) = f ( x ); aquí w x representa la concatenación de las dos cadenas w y x . Esto significa que F se puede utilizar para simular cualquier función computable de una variable. Informalmente, w representa un "script" para la función computable f y F representa un "intérprete" que analiza el script como un prefijo de su entrada y luego lo ejecuta en el resto de la entrada.
El dominio de F es el conjunto de todas las entradas p en las que está definido. Para F que son universales, tal p generalmente puede verse como la concatenación de una parte de programa y una parte de datos, y como un programa único para la función F.
La función F se llama sin prefijo si no hay dos elementos p , p′ en su dominio tales que p′ sea una extensión propia de p . Esto se puede reformular como: el dominio de F es un código sin prefijo (código instantáneo) en el conjunto de cadenas binarias finitas. Una forma sencilla de imponer la ausencia de prefijos es utilizar máquinas cuyo medio de entrada sea un flujo binario del que los bits se puedan leer uno a la vez. No hay ningún marcador de fin de transmisión; el final de la entrada está determinado por el momento en que la máquina universal decide dejar de leer más bits y los bits restantes no se consideran parte de la cadena aceptada. Aquí queda clara la diferencia entre las dos nociones de programa mencionadas en el último párrafo; uno se reconoce fácilmente mediante alguna gramática, mientras que el otro requiere un cálculo arbitrario para reconocerlo.
El dominio de cualquier función computable universal es un conjunto computable enumerable pero nunca un conjunto computable . El dominio es siempre el equivalente de Turing al problema de la detención .
Sea P F el dominio de una función computable universal sin prefijo F . La constante Ω F se define entonces como
donde denota la longitud de una cadena p . Esta es una suma infinita que tiene un sumando por cada p en el dominio de F. El requisito de que el dominio esté libre de prefijos, junto con la desigualdad de Kraft , garantiza que esta suma converja a un número real entre 0 y 1. Si F queda claro por el contexto, entonces Ω F puede denotarse simplemente Ω, aunque es diferente universal sin prefijos. Las funciones computables conducen a diferentes valores de Ω.
Conociendo los primeros N bits de Ω, se podría calcular el problema de detención para todos los programas de un tamaño hasta N. Sea el programa p para el cual se va a resolver el problema de detención que tenga una longitud de N bits. En forma de encaje , se ejecutan todos los programas de todas las longitudes, hasta que se hayan detenido suficientes para contribuir conjuntamente con suficiente probabilidad para hacer coincidir estos primeros N bits. Si el programa p aún no se ha detenido, entonces nunca lo hará, ya que su contribución a la probabilidad de parada afectaría a los primeros N bits. Por tanto, el problema de la detención quedaría resuelto para p .
Debido a que muchos problemas destacados en teoría de números, como la conjetura de Goldbach , son equivalentes a resolver el problema de detención para programas especiales (que básicamente buscarían contraejemplos y se detendrían si se encontrara alguno), conocer suficientes bits de la constante de Chaitin también implicaría conocer la respuesta a estos problemas. Pero como el problema de la detención generalmente no tiene solución y, por lo tanto, no es posible calcular excepto los primeros bits de la constante de Chaitin, [2] esto simplemente reduce los problemas difíciles a imposibles, muy parecido a intentar construir una máquina oráculo para el problema de la detención. sería.
El espacio de Cantor es la colección de todas las secuencias infinitas de 0 y 1. Una probabilidad de detención puede interpretarse como la medida de un determinado subconjunto del espacio de Cantor bajo la medida de probabilidad habitual en el espacio de Cantor. Es de esta interpretación que las probabilidades de detención toman su nombre.
La medida de probabilidad en el espacio de Cantor, a veces llamada medida de la moneda justa, se define de modo que para cualquier cadena binaria x , el conjunto de secuencias que comienzan con x tiene medida 2 −| x | . Esto implica que para cada número natural n , el conjunto de secuencias f en el espacio de Cantor tal que f ( n ) = 1 tiene medida 1/2, y el conjunto de secuencias cuyo nésimo elemento es 0 también tiene medida 1/2.
Sea F una función computable universal sin prefijo. El dominio P de F consta de un conjunto infinito de cadenas binarias.
Cada una de estas cadenas p i determina un subconjunto Si del espacio de Cantor; el conjunto Si contiene todas las secuencias en el espacio de Cantor que comienzan con p i . Estos conjuntos son disjuntos porque P es un conjunto sin prefijos. La suma
representa la medida del conjunto
De esta manera, Ω F representa la probabilidad de que una secuencia infinita de 0 y 1 seleccionada aleatoriamente comience con una cadena de bits (de alguna longitud finita) que esté en el dominio de F. Es por esta razón que a Ω F se le llama probabilidad de detención.
Cada constante de Chaitin Ω tiene las siguientes propiedades:
No todos los conjuntos que Turing equivalen al problema de detención son una probabilidad de detención. Se puede utilizar una relación de equivalencia más fina , la equivalencia de Solovay , para caracterizar las probabilidades de detención entre los reales del ce izquierdo. [5] Se puede demostrar que un número real en [0,1] es una constante de Chaitin (es decir, la probabilidad de interrupción de alguna función computable universal sin prefijo) si y sólo si es de izquierda y algorítmicamente aleatorio. [5] Ω se encuentra entre los pocos números algorítmicamente aleatorios definibles y es el número algorítmicamente aleatorio más conocido, pero no es en absoluto típico de todos los números algorítmicamente aleatorios. [6]
Un número real se llama computable si existe un algoritmo que, dado n , devuelve los primeros n dígitos del número. Esto equivale a la existencia de un programa que enumere los dígitos del número real.
No es computable ninguna probabilidad de detención. La prueba de este hecho se basa en un algoritmo que, dados los primeros n dígitos de Ω, resuelve el problema de detención de Turing para programas de longitud hasta n . Dado que el problema de la detención es indecidible , Ω no se puede calcular.
El algoritmo procede como sigue. Dados los primeros n dígitos de Ω y a k ≤ n , el algoritmo enumera el dominio de F hasta que se hayan encontrado suficientes elementos del dominio para que la probabilidad que representan esté dentro de 2 −( k +1) de Ω. Después de este punto, no puede haber ningún programa adicional de longitud k en el dominio, porque cada uno de ellos sumaría 2 − k a la medida, lo cual es imposible. Por tanto, el conjunto de cadenas de longitud k en el dominio es exactamente el conjunto de cadenas ya enumeradas.
Un número real es aleatorio si la secuencia binaria que representa el número real es una secuencia algorítmicamente aleatoria . Calude, Hertling, Khoussainov y Wang demostraron [7] que un número real recursivamente enumerable es una secuencia algorítmicamente aleatoria si y sólo si es un número Ω de Chaitin.
Para cada sistema axiomático específico y consistentemente representado para los números naturales , como la aritmética de Peano , existe una constante N tal que no se puede demostrar que ningún bit de Ω después del N -ésimo sea 1 o 0 dentro de ese sistema. La constante N depende de cómo se representa efectivamente el sistema formal y, por tanto, no refleja directamente la complejidad del sistema axiomático. Este resultado de incompletitud es similar al teorema de incompletitud de Gödel en el sentido de que muestra que ninguna teoría formal consistente para la aritmética puede ser completa.
Como se mencionó anteriormente, los primeros n bits de la constante Ω de Gregory Chaitin son aleatorios o incompresibles en el sentido de que no podemos calcularlos mediante un algoritmo de detención con menos de nO(1) bits. Sin embargo, considere el algoritmo breve pero nunca detenido que enumera y ejecuta sistemáticamente todos los programas posibles; cada vez que uno de ellos se detiene, su probabilidad se agrega a la salida (inicializada por cero). Después de un tiempo finito, los primeros n bits de la salida nunca más cambiarán (no importa que este tiempo en sí no sea computable mediante un programa de detención). Entonces, existe un algoritmo corto sin detención cuya salida converge (después de un tiempo finito) en los primeros n bits de Ω. En otras palabras, los primeros n bits enumerables de Ω son altamente comprimibles en el sentido de que son computables en límites mediante un algoritmo muy corto; no son aleatorios con respecto al conjunto de algoritmos enumerados. Jürgen Schmidhuber (2000) construyó un "Super Ω" computable con límites que, en cierto sentido, es mucho más aleatorio que el Ω computable con límites original, ya que no se puede comprimir significativamente el Super Ω mediante ningún algoritmo enumerativo sin detención.
Para una alternativa "Super Ω", la probabilidad de universalidad de una Máquina Universal de Turing (UTM) sin prefijos , es decir, la probabilidad de que siga siendo universal incluso cuando cada entrada de la misma (como una cadena binaria ) tiene el prefijo de una cadena binaria aleatoria. – puede verse como la probabilidad de que una máquina con Oracle no se detenga en la tercera iteración del problema de detención (es decir, usando la notación de Turing Jump ). [8]
