En el subcampo de la informática de la teoría de la información algorítmica , 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 se forman a partir de una construcción debida a Gregory Chaitin .
Aunque existen infinitas probabilidades de detención, una para cada método (universal, ver más abajo) de codificación de programas, es común utilizar la letra Ω para referirse a ellas como si sólo existiera una. Debido a que Ω depende de la codificación del programa que se utilice, a veces se la denomina construcción de Chaitin cuando no se refiere a ninguna codificación específica.
Cada probabilidad de parada es un número real normal y trascendental que no es computable , lo que significa que no hay ningún algoritmo para calcular sus dígitos. Cada probabilidad de parada es aleatoria según Martin-Löf , lo que significa que ni siquiera hay ningún algoritmo que pueda adivinar sus dígitos de manera fiable.
La definición de probabilidad de parada se basa en la existencia de una función computable universal sin prefijo. Dicha función, intuitivamente, representa un lenguaje de programación con la propiedad de que ningún programa válido puede obtenerse como extensión propia de otro programa válido.
Sin embargo, los lenguajes de programación informática generalmente consisten en una secuencia de comandos, por lo que ningún lenguaje de programación es una función computable universal libre de prefijos.
Supongamos que F es una función parcial que toma un argumento, una cadena binaria finita, y posiblemente devuelve una sola 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 solo 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 denomina universal si se cumple la siguiente propiedad: para cada función computable f de una sola variable existe 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. De manera informal, 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 puede verse generalmente como la concatenación de una parte de programa y una parte de datos, y como un único programa para la función F.
La función F se llama libre de 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 libre de prefijo (código instantáneo) en el conjunto de cadenas binarias finitas. Una forma sencilla de hacer cumplir la ausencia de prefijo es utilizar máquinas cuyo medio de entrada sea un flujo binario del que se puedan leer los bits de uno en uno. No hay un marcador de fin de flujo; el final de la entrada se determina cuando la máquina universal decide dejar de leer más bits, y los bits restantes no se consideran parte de la cadena aceptada. Aquí, la diferencia entre las dos nociones de programa mencionadas en el último párrafo se vuelve clara; una es fácilmente reconocida por alguna gramática, mientras que la otra requiere un cálculo arbitrario para reconocerla.
El dominio de cualquier función computable universal es un conjunto enumerable computacionalmente , pero nunca un conjunto computable . El dominio es siempre equivalente de Turing al problema de 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 para cada p en el dominio de F . El requisito de que el dominio esté libre de prefijos, junto con la desigualdad de Kraft , asegura que esta suma converja a un número real entre 0 y 1. Si F es claro a partir del contexto, entonces Ω F puede denotarse simplemente Ω, aunque diferentes funciones computables universales sin prefijos 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 de hasta N . Sea el programa p para el que se va a resolver el problema de detención de N bits de longitud. En forma de cola de milano , se ejecutan todos los programas de todas las longitudes, hasta que se hayan detenido suficientes para contribuir en conjunto con la probabilidad suficiente para que coincida con estos primeros N bits. Si el programa p no se ha detenido todavía, entonces nunca lo hará, ya que su contribución a la probabilidad de detención afectaría a los primeros N bits. Por lo tanto, el problema de detención se resolvería para p .
Dado que muchos problemas pendientes en la teoría de números, como la conjetura de Goldbach , son equivalentes a resolver el problema de la detención para programas especiales (que básicamente buscarían contraejemplos y se detendrían si se encontrara uno), 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 no es generalmente solucionable y, por lo tanto, calcular cualquier otro bit de la constante de Chaitin que no sea el primero no es posible en un lenguaje muy conciso, esto simplemente reduce los problemas difíciles a imposibles, de manera muy similar a lo que sería intentar construir una máquina oráculo para el problema de la detención .
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 de donde las probabilidades de detención toman su nombre.
La medida de probabilidad en el espacio de Cantor, a veces llamada medida de 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 tales que f ( n ) = 1 tiene medida 1/2, y el conjunto de secuencias cuyo n º elemento es 0 también tiene medida 1/2.
Sea F una función computable universal sin prefijo. El dominio P de F consiste en un conjunto infinito de cadenas binarias.
Cada una de estas cadenas p i determina un subconjunto S i del espacio de Cantor; el conjunto S i contiene todas las secuencias en el espacio de Cantor que comienzan con p i . Estos conjuntos son disjuntos porque P es un conjunto sin prefijo. 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 una longitud finita) que esté en el dominio de F. Es por esta razón que Ω F se denomina probabilidad de detención.
Cada constante de Chaitin Ω tiene las siguientes propiedades:
No todo conjunto que es equivalente de Turing al problema de la detención es 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 de orden izquierdista. [4] Se puede demostrar que un número real en [0,1] es una constante de Chaitin (es decir, la probabilidad de detención de alguna función computable universal sin prefijo) si y solo si es de orden izquierdista y algorítmicamente aleatorio. [4] Ω se encuentra entre los pocos números aleatorios algorítmicos definibles y es el número aleatorio algorítmico más conocido, pero no es en absoluto típico de todos los números aleatorios algorítmicos. [5]
Un número real se denomina computable si existe un algoritmo que, dado n , devuelve los primeros n dígitos del número. Esto es equivalente a la existencia de un programa que enumera los dígitos del número real.
No se puede calcular 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 de hasta n . Como el problema de detención es indecidible , Ω no se puede calcular.
El algoritmo procede de la siguiente manera. Dados los primeros n dígitos de Ω y un k ≤ n , el algoritmo enumera el dominio de F hasta que se han 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 agregaría 2 − k a la medida, lo cual es imposible. Por lo tanto, el conjunto de cadenas de longitud k en el dominio es exactamente el conjunto de tales 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 [6] que un número real recursivamente enumerable es una secuencia algorítmicamente aleatoria si y solo si es un número Ω de Chaitin.
Para cada sistema axiomático consistente y efectivamente representado específico 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 sea 1 o 0 dentro de ese sistema. La constante N depende de cómo se represente efectivamente el sistema formal y, por lo 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 corto pero que nunca se detiene, que sistemáticamente enumera y ejecuta todos los programas posibles; siempre 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 cambiarán más (no importa que este tiempo en sí no sea computable por un programa de detención). Entonces, hay 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 al límite por un algoritmo muy corto; no son aleatorios con respecto al conjunto de algoritmos de enumeración. Jürgen Schmidhuber (2000) construyó un "Super Ω" computable al límite que, en cierto sentido, es mucho más aleatorio que el Ω computable al límite original, ya que no se puede comprimir significativamente el Super Ω mediante ningún algoritmo de enumeración sin detención.
Para una "Super Ω" alternativa, la probabilidad de universalidad de una Máquina de Turing Universal (UTM) sin prefijo –es decir, la probabilidad de que siga siendo universal incluso cuando cada entrada de la misma (como una cadena binaria ) esté prefijada por una cadena binaria aleatoria– puede verse como la probabilidad de no detención de una máquina con oráculo en la tercera iteración del problema de detención (es decir, utilizando la notación de salto de Turing ). [7]
