La constante de Chaitin es normal?

Según esta fuente, la constante Chaitin es normal.$\Omega$

Cada probabilidad de detención es un número real normal y trascendental que no es computable, lo que significa que no hay un algoritmo para calcular sus dígitos. De hecho, cada probabilidad de detención es aleatoria de Martin-Löf, lo que significa que ni siquiera hay un algoritmo que pueda adivinar sus dígitos de manera confiable.

Fuente (Wikipedia)

Además, la definición de normal es que cada dígito ocurre con igual probabilidad . Y que cada dueto de dígitos ocurre con probabilidad y cada triplete ocurre con probabilidad y así sucesivamente.$1/b$$1/b^2$$1/b^3$

Omega de Chaitin se calcula a través de

$\Omega = \sum_{p \in halts} 2^{-|p|}$

Escribiendo en binario, obtenemos una lista de 0 y 1. Por ejemplo,$\Omega$

2^-1=0.1 +
2^-2=0.01 +
2^-3=0.001 +
~skip 2^-4 as it does not halt
2^-5=0.00001 +
...
=\Omega
=0.11101...

Claramente, podemos ver que la posición de cada bit corresponde al estado de detención del programa de longitud correspondiente al bit.

Aquí es con lo que estoy luchando

Si es realmente normal, significa que exactamente el 50% de los programas se detienen y exactamente el 50% no. Esto parece muy contrario a la intuición.$\Omega$

Por ejemplo, supongamos que genero programas java concatenando aleatoriamente caracteres individuales. La mayoría de ellos, supongo que más del 99.99% ni siquiera compilaría. ¿No implica esto que al menos el 99,99% de ellos no se detendrá? ¿Cómo justificamos que exactamente la mitad se detendrá y exactamente la mitad no, en virtud de que es normal?$\Omega$

¿O es wikipedia incorrecto acerca de que es normal?$\Omega$

A diferencia de su ejemplo, la constante de Chaitin no se define de la siguiente manera:

En cambio, hay un conjunto $\Pi \subseteq \{0,1\}^*$de programas permitidos que no tiene prefijo (ninguna cadena es un prefijo de otra cadena). Cada uno de los programas en$\Pi$es legal (esto niega su ejemplo de Java). Si los programas están codificando en unario, entonces es cierto que el$n$el programa tiene duración $n$y luego tu definición de $\Omega$trabajos. Pero para otras codificaciones, la definición de$\Omega$ es

La constante de Chaitin es algorítmicamente aleatoria : la complejidad de Kolmogorov (prefijo) de la primera$n$ bits es $n - O(1)$. Para mostrar esto, tenga en cuenta primero que$\Omega_n$, el primero $n$ pedazos de $\Omega$, es suficiente para determinar si un programa de duración $n$ (debajo de la codificación $\Pi$) se detiene o no. De hecho, como una fracción,$\Omega_n \leq \Omega < \Omega_n + 2^{-n}$. Ejecute todos los programas en paralelo, y siempre que$p$ paradas, agregar $2^{-|p|}$ a algún mostrador $C$(inicializado en cero). Finalmente$C \geq \Omega_n$ (ya que $C \to \Omega$desde abajo). En este punto, si el programa de entrada de longitud$n$ no se detuvo, entonces sabes que no se detiene, ya que de lo contrario $\Omega \geq C + 2^{-n} \geq \Omega_n + 2^{-n}$.

Dado esto, supongamos que para algunos $K>0$ e infinitamente muchos $n$, podrías calcular $\Omega_n$ utilizando $n - K$bits Para cada uno$n$, puede encontrar una cadena cuya complejidad de Kolmogorov sea mayor que $n$, al considerar la salida de todos los programas de detención de longitud como máximo $n$. Para lo suficientemente grande$K$, el resultado es un programa de duración como máximo $n$ para calcular una cadena cuya complejidad de Kolmogorov es más que $n$. Esta contradicción prueba que para algunos$K$, la complejidad de Kolmogorov de $\Omega_n$ Por lo menos $n-K$.

Aleatoriedad algorítmica de $\Omega$implica, en particular, que la frecuencia de 0s y 1s en su expansión binaria tiende a 1/2. De hecho, supongamos que para algunos (racional)$\epsilon > 0$ existen infinitamente muchos $n$ tal que la fracción de 1s en $\Omega_n$ es a lo sumo $1/2-\epsilon$. Como solo hay a lo sumo$2^{h(1/2-\epsilon)n}$ cadenas con como máximo $1/2-\epsilon$ muchos 1s, podemos comprimir $\Omega_n$ medir $h(1/2-\epsilon)n + 2\log n + C_\epsilon$ (el constante $C_\epsilon$ depende de $\epsilon$ ya que el programa necesita saber $\epsilon$) Sin embargo, esto es$n - \omega(1)$, contradiciendo la aleatoriedad algorítmica de $\Omega$.

Su error está en la siguiente línea:

Si $\Omega$ es realmente normal, entonces significa que exactamente el 50% de los programas se detienen y exactamente el 50% no.

No Eso no es lo que significa "normal". O, para decirlo de otra manera: definir$d_0(n)$ ser el número de bits que son un 0, en el primer $n$ bits de la expansión de base-2 de $\Omega$. Diciendo que$\Omega$es normal implica que

En otras palabras, "normal" es una noción asintótica. Significa que a medida que miras lo suficiente en los pedazos de$\Omega$, en promedio, aproximadamente la mitad de ellos serán ceros. (Del mismo modo, aproximadamente la mitad con be 1's).

Sin embargo, esto no dice nada acerca de los primeros bits de $\Omega$. Por ejemplo, no hay implicación de que la expansión binaria$\Omega$ comienza como 0.01 ... o en cualquier otra cosa, y no hay implicación de que $\Omega$ está cerca de 1/2. $\Omega$puede estar cerca de 0, o cerca de 1, o en cualquier punto intermedio; eso no contradice ser normal, y ser normal no implica nada sobre qué tan grande$\Omega$ es.