La condición es que $d$ debería ser óptimo. Formalmente: Una máquina sin prefijos es una función computable parcial $M:2^{< \omega } \rightarrow 2^{< \omega }$ de tal manera que $M( \sigma )$ La detención implica $M( \tau )$ no se detiene por ningún $ \tau $ comparable con $ \sigma $ . Para una máquina así $M$ Definamos $K_M( \sigma )$ para ser $ \min \{| \tau | : M( \tau ) = \sigma\ }$
Una máquina sin prefijos $U$ es óptimo si para cualquier máquina sin prefijos $M$ hay una constante $c$ de tal manera que por cada $ \sigma $ tenemos $K_U( \sigma ) \leq K_M( \sigma ) + c$ .
Luego $$ \Omega = \sum_ {U( \sigma ) \text { halts}} 2^{-| \sigma |}$$ es un número normal en todas las bases, y mucho más: Es Martin-Löf al azar, es decir, hay una constante $c$ de tal manera que para cada prefijo $ \sigma $ de $ \Omega $ (visto como un elemento de $2^{ \omega }$ ), tenemos $K_U( \sigma ) \geq | \sigma | - c$ . Significa que $U$ no puede comprimir los prefijos de $ \Omega $ . Por la optimización de $U$ significa que ningún algoritmo libre de prefijos puede comprimir los prefijos de $ \Omega $ .
El punto clave de la demostración radica en el hecho de que desde el $n$ los primeros pedazos de $ \Omega $ se puede decidir de manera uniforme si $U$ se detiene o no en cuerdas de longitud inferior a $n$ : Corre $U$ en cada cuerda en paralelo y aproximado $ \Omega $ desde abajo añadiendo $2^{-| \sigma |}$ cada vez $U$ se detiene en $ \sigma $ . En algún momento nuestra aproximación coincidirá con la $n$ los primeros pedazos de $ \Omega $ y entonces sabemos si $U$ se detiene o no en cuerdas de longitud inferior a $n$ .
Supongamos ahora por contradicción que por cada $c$ existe $n$ de tal manera que $K_U( \Omega \upharpoonright n) < n - c$ . Podemos construir la máquina libre de prefijos $M$ que en $ \sigma $ hace lo siguiente: $M$ dirige $U( \sigma )$ hasta que produzca algo de $ \tau $ (los casos interesantes son cuando $U( \sigma ) = \Omega \upharpoonright n$ para algunos $n$ ). Luego $M$ trata de decidir cuáles son las cuerdas $ \rho $ de longitud menor que $| \tau |$ de tal manera que $U( \rho )$ se detiene, por el algoritmo descrito anteriormente. Si $M$ logra decidirlo (o cree que lo logra), entonces produce una cadena diferente de $U( \rho )$ para cualquier cadena de este tipo $ \rho $ .
Tenga en cuenta que mientras $U( \sigma ) = \Omega \upharpoonright n$ debemos entonces tener $K_U(M( \sigma )) \geq n$ por diseño. Pero hasta alguna constante también tenemos $K_U(M( \sigma )) \leq K_M(M( \sigma )) \leq | \sigma |$ (por la optimización de $U$ y la definición de $K_M$ ). En particular $| \sigma | \geq n$ hasta alguna constante. Tenga en cuenta que la constante depende de la máquina $M$ sólo y no en $ \sigma $ o $n$ . Ahora por hipótesis, la diferencia entre $| \sigma |$ y $n$ para las cuerdas $ \sigma $ de tal manera que $U( \sigma ) = \Omega \upharpoonright n$ puede hacerse tan grande como queramos (con n > $| \sigma |$ ). Cuando esta diferencia es lo suficientemente grande (mayor que nuestra constante), obtenemos una contradicción.
Actualización : La prueba de que una máquina tan óptima $U$ existe va de la siguiente manera: Suponga que tiene una lista efectiva $\{M_e\}_{e \in \mathbb {N}}$ de todas las máquinas sin prefijo. Luego se define $U(1^e 0 \tau )$ para ser $M_e( \tau )$ . Tenga en cuenta que $U$ es libre de prefijos. El problema ahora es conseguir esa lista, de una lista efectiva $\{N_e\}_{e \in \mathbb {N}}$ de (no necesariamente libre de prefijos) máquinas (que tenemos): Para ello, reemplace cada máquina $N_e$ con una máquina $M_e$ que en la entrada $ \tau $ ejecuta $N_e( \tau )$ . Si obtenemos una respuesta en $t$ paso de computación (suponemos $t > | \tau |$ ), $M_e$ entonces verifica que $N_e$ no se detiene también en menos de $t$ pasos, en una cadena de longitudes menores que $t$ y comparable con $ \tau $ . Luego $M_e$ adapta su respuesta para mantener la libertad de prefijos. Todo lo que importa es que $M_e$ se comporta como $N_e$ si $N_e$ ya está libre de prefijos, lo cual conseguimos, por diseño.
Por último, nótese que en el "mundo real", las máquinas no llevan prefijo, por ejemplo, en cualquier sistema de archivos, se debe saber dónde comienza y dónde termina un archivo.
