Constante de Chaitin

En el subcampo informático de la teoría algorítmica de la información, una constante de Chaitin (número omega de Chaitin) 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 de 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 hubiera una sola. Debido a que Ω depende de la codificación del programa utilizada, a veces se denomina 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 un algoritmo para calcular sus dígitos. Cada probabilidad de detención 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 confiable.

Antecedentes

La definición de una probabilidad de parada 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 no se puede obtener ningún programa válido como una extensión adecuada de otro programa válido.

Suponga 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 y 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 llama universal si se cumple la siguiente propiedad: para cada función computable f de una sola variable hay una cadena < i>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 usar 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 sobre las que se define. Para F que son universales, tal p generalmente se puede ver como la concatenación de una parte de programa y una parte de datos, y como un solo programa para la función F.

La función F se llama sin prefijo si no hay dos elementos p, p′ en su dominio tal que p′ es 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 simple de hacer cumplir la ausencia de prefijos es usar máquinas cuyo medio de entrada sea un flujo binario desde el cual los bits se pueden leer uno a la vez. No hay marcador de final de flujo; 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í, la diferencia entre las dos nociones de programa mencionadas en el último párrafo se vuelve clara; uno es fácilmente reconocido por 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 Turing equivalente al problema de detención.

Definición

Sea P_F el dominio de una función computable universal sin prefijo F. La constante Ω_F se define entonces como

${displaystyle Omega _{F}=sum _{pin ¿Por qué?$,

Donde ${displaystyle left WordPresspright sometida}$ denota la longitud de una cadena p. Esta es una suma infinita que tiene una sola fuente para cada p en el dominio de F. El requisito de que el dominio sea libre de prefijo, junto con la desigualdad de Kraft, asegura que esta suma converge a un número real entre 0 y 1. Si F está claro desde el contexto entonces Ω_F puede ser denotado simplemente Ω, aunque diferentes funciones computables universales libres de prefijo conducen a diferentes valores de Ω.

Relación con el problema de la detención

Conociendo los primeros N bits de Ω, se podría calcular el problema de detención para todos los programas de tamaño hasta N. Deje que el programa p para el que se va a resolver el problema de detención tenga 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 conjuntamente con la probabilidad suficiente para hacer coincidir estos primeros N bits. Si el programa p no se ha detenido todavía, 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 la detención estaría resuelto para p.

Debido a que muchos problemas sobresalientes 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 encuentran uno), sabiendo 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 se puede resolver y, por lo tanto, no es posible calcular nada más que los primeros bits de la constante de Chaitin, esto solo reduce los problemas difíciles a imposibles, al igual que intentar construir una máquina de oráculo para la detención. problema seria.

Interpretación como probabilidad

El espacio de Cantor es la colección de todas las secuencias infinitas de 0 y 1. Una probabilidad de detención se puede interpretar como la medida de un cierto subconjunto del espacio de Cantor bajo la medida de probabilidad habitual en el espacio de Cantor. Es a partir 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 moneda justa, se define de modo que para cualquier cadena binaria x el conjunto de secuencias que comienza con x tiene medida 2^−|x|. Esto implica que para cada número natural n, el conjunto de sucesiones f en el espacio de Cantor tales que f(n) = 1 tiene medida 1/2, y el conjunto de sucesiones 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

${displaystyle P=p_{1},p_{2},ldots }$.

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< /i>}. Estos conjuntos son disjuntos porque P es un conjunto sin prefijos. La suma

${displaystyle sum _{pin P}2^{-priv-Upp$

representa la medida del conjunto

${displaystyle bigcup _{iin mathbb {N}S_{i}$.

De esta manera, Ω_F representa la probabilidad de que una secuencia infinita de 0s y 1s seleccionada aleatoriamente comience con una cadena de bits (de cierta longitud finita) que está en el dominio de F. Es por esta razón que Ω_F se denomina probabilidad de detención.

Propiedades

Cada constante de Chaitin Ω tiene las siguientes propiedades:

• Es algorítmicamente al azar (también conocido como Martin-Löf al azar o 1 aleatorio). Esto significa que el programa más corto para producir el primero n bits de Ω debe ser de tamaño al menos n − O(1). Esto es porque, como en el ejemplo Goldbach, esos n bits nos permiten averiguar exactamente qué programas detienen entre todos los de longitud al máximo n.
• Como consecuencia, es un número normal, lo que significa que sus dígitos están distribuidos como si fueran generados por tirar una moneda justa.
• No es un número computable; no hay función computable que enumera su expansión binaria, como se describe a continuación.
• El conjunto de números racionales q tales que q Ω es computadamente enumerable; un número real con tal propiedad se llama un número real en la teoría de la recursión.
• El conjunto de números racionales q tales que q ■ Ω no es computadamente enumerable. (Reason: cada izquierda-c.e. real con esta propiedad es computable, que Ω no es).
• Ω es un número aritmético.
• Es Turing equivalente al problema de suspensión y por lo tanto a nivel ${displaystyle Delta _{2} {0}}$ de la jerarquía aritmética.

No todos los conjuntos que son equivalentes de Turing al problema de detención son una probabilidad de detención. Se puede utilizar una relación de equivalencia más fina, equivalencia de Solovay, para caracterizar las probabilidades de detención entre la izquierda-c.e. reales 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 se deja c.e. y algorítmicamente aleatorio. Ω es uno de 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.

Incomputabilidad

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 enumera los dígitos del número real.

No se puede calcular ninguna probabilidad de parada. 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 hasta n. Dado que el problema de la 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 sea suficiente se han encontrado elementos del dominio de modo que la probabilidad que representan está dentro de 2^−(k+1) de Ω. Después de este punto, ningún programa adicional de longitud k puede estar 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 tales cadenas ya enumerado.

Aleatoriedad algorítmica

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 que un número real recursivamente enumerable es una secuencia algorítmicamente aleatoria si y solo si es un número Ω de Chaitin.

Teorema de incompletitud para detener las probabilidades

Para cada sistema axiomático consistente representado de manera efectiva para los números naturales, como la aritmética de Peano, existe una constante N tal que ningún bit de Ω después de la Nésima puede demostrarse que es 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.

Súper Omega

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 n-O(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í mismo no sea computable por un programa de detención). Entonces, hay un algoritmo corto que no se detiene 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 por límite mediante un algoritmo muy corto; no son aleatorios con respecto al conjunto de algoritmos de enumeración. Jürgen Schmidhuber (2000) construyó un "Super Ω" que, en cierto sentido, es mucho más aleatorio que el límite computable Ω original, ya que no se puede comprimir significativamente el Súper Ω mediante ningún algoritmo de enumeración sin interrupción.

Para una alternativa "Super Ω", la probabilidad de universalidad de una máquina de Turing Universal sin prefijo (UTM) – es decir, la probabilidad de que siga siendo universal incluso cuando cada entrada de ella (como una cadena binaria) está prefijada por una cadena binaria aleatoria – se puede ver como la probabilidad no-halante de una máquina con oráculo la tercera iteración del problema de suspensión (es decir,, ${displaystyle O^{(3)}}$usando la notación Turing Jump).