3. Tamaño de Programa

Abril 29, 2012

Índice

Ordenadores y Medidas de Complejidad

Propiedades algorítmicas de las medidas de complejidad

Estimaciones Cuantitativas

Probabilidades De Parada


Una forma de medir el contenido de información de un texto es determinar el tamaño de la menor cadena a partir de la cual un ordenador puede reproducir el texto original. Esta idea ha sido formalizada independientemente de distintos modos por Solomonoff, Kolmogorov y Chaitin.

Ordenadores y Medidas de Complejidad

Definición: $\text{string}_Q(n)$ es la cadena sobre un alfabeto de $Q$ letras que ocupa el lugar $n$, en el orden casi-lexicográfico.

Definición: Una función parcial $\varphi:\mathbb N\overset{o}{\to} \mathbb N$ es computable (función p.c.) si existe un conjunto finito de instrucciones tales que, dada como entrada $x\in \text{dom}(\varphi)$, produce como salida, después de un número finito de pasos, $\varphi(x)$, y si $x$ no pertenece al dominio el algoritmo no para.

Definición: Una función parcial $\varphi: A^*\overset{o}{\to} A^*$ es computable si existe una función p.c. $f:\mathbb N \overset{o}{\to} \mathbb N$ tal que $$\varphi(x)=\text{string}(f(\text{string}^{-1}(x))),$$ para todo $x\in A^*$ (en el sentido que ambas tienen el mismo dominio y en él coinciden).

Definición: Un ordenador es una función parcial computable: $$\varphi: A^*\times A^* \overset{o}{\to} A^*$$

Definición: Un ordenador de Chaitin es un ordenador $C$ tal que para todo $v\in A^*$, el dominio de $C_v$ es libre de prefijo, donde $C_v:A^*\overset{o}{\to} A^*$ es la sección $C_v(x)=C(x,v)$ para todo $x\in A^*$.

Nota: Si $C(x,v)<\infty$ y $y<_p x$, entonces $C(y,v)<\infty$ implica que $y=x$.

Definición: Un ordenador $\psi$ es universal si para todo ordenador $\varphi$ existe una constante $c$ (que depende sólo de $\psi,\varphi$) con la siguiente propiedad: si $\varphi(x,v)<\infty$, entonces existe una cadena $x'$ tal que $\psi(x',v)=\varphi(x,v)$ y $|x'|\leq |x|+c.$

Definición: Un ordenador de Chaitin $\psi$ es universal si para todo computador de Chaitin $C$, existe una constante $c$ (que depende de $\psi,C$) con la siguiente propiedad: si $C(x,v)<\infty$, entonces existe una cadena $x'$ tal que $\psi(x',v)=C(x,v)$ y $|x'|\leq |x|+c.$

Teorema: Existe un ordenador universal.

Teorema: Existe un ordenador universal de Chaitin.

Demostración: Sea $F:\mathbb N\times A^*\times A^*\overset{o}{\to} A^*$ una función universal p. c. para la clase de todas las funciones p. c. $C:A^*\times A^*\overset{o}{\to}A^*$ tales que para todo $v\in A^*$ el conjunto $\{u\in A^*: C(u,v)<\infty\}$ es libre de prefijo. Definimos el ordenador universal de Chaitin del siguiente modo: $$U(a_1^ia_2u,v)=F(i,u,v).$$

Nota: \textbf{ Fijamos en este momento un ordenador universal $\psi$ y un ordenador universal de Chaitin $U$. }

Definición: La complejidad absoluta (Kolmogorov-Chaitin) asociada al ordenador $\varphi$ es la función parcial $K_\varphi:A^*\overset{o}{\to} \mathbb N$, definida por $$K_\varphi(x)=\min\{|u|: u\in A^*, \varphi(u,\lambda)=x\}.$$

Nota: Si $\varphi=\psi$ ponemos $K=K_\phi$.

Definición: La complejidad absoluta autodelimitante (Chaitin) asociada al ordenador de Chaitin $C$ es la función parcial $H_C:A^*\overset{o}{\to} \mathbb N$, definida por $$H_C(x)=\min\{|u|: u\in A^*, C(u,\lambda)=x\}.$$

Nota: Si $C=U$ ponemos $H=H_U$.

Definición: El programa canónico definido respecto de $U$ es $$x^*=\min\{u\in A^*: U(u,\lambda)=x\},$$ donde el mínimo se toma de acuerdo con el orden casi-lexicográfico de $A^*$ inducido por el orden del alfabeto $a_1<\dots<a_Q.$

Nota: $x^*$ es el modo más compacto de computar $x$ utilizando $U$.

Teorema: Para cada ordenador $\varphi$: $K(x)\leq K_\varphi(x)+O(1)$.

Demostración: Está clara por la universalidad de $\psi$.

Teorema: Para cada ordenador de Chaitin $C$: $H(x)\leq H_C(x)+O(1)$.

Demostración: Está clara por la universalidad de $U$.

Teorema: Las secciones $\psi_y, U_y$ son sobreyectivas, para todo $y$.

Demostración: Probemos el resultado para $U$.
Sea $y\in A^*$ y $z\in A^*$ cualquiera. La función $C:A^*\times A^*\to A^*$ que asigna $z$ al par $(\lambda, y)$ (para todo $y\in A^*$) y no está definida en el resto, es p.c. y además es un ordenador de Chaitin. Como $U$ es un ordenador universal de Chaitin y $C(\lambda,y)<\infty$, existe $x'\in A^*$ tal que $U(x',y)=C(\lambda,y)=z$ y $|x'|\leq 0+c$ donde $c$ es una constante que sólo depende de $U$ (que ya está fijo) y de $C$.

Teorema: Para todo $x\in A^*$ existe $x^*$ y $x^*\neq \lambda$, $x=U(x^*,\lambda)$, $H(x)=|x^*|.$

Demostración: Por el teorema anterior la función $U_\lambda$ es sobreyectiva, luego debe existir algún $y$ tal que $U(y,\lambda)=x$. Ahora bien, siendo $U_\lambda$ sobreyectiva y siendo el dominio de $U_\lambda$ libre de prefijo, no puede ser que $y=\lambda$, pues de lo contrario el rango de la sección $U_\lambda$ sería un único punto $U(\lambda,\lambda)$. Así que $y$ no puede ser $\lambda$. Basta ahora tomar el mínimo respecto del orden casi-lexicográfico del conjunto no vacío $\{y\in A^*: U(x^*,\lambda)=x\}$. Ese mínimo es $x^*.$

Definición: La complejidad condicionada de Kolmogorov-Chaitin inducida por el ordenador $\varphi$ se define por la fórmula: $$K_\varphi(x|v)=\min\{|y|: y\in A^*, \varphi(y,v)=x\}.$$

Nota: Pongamos $K(x|v)=K_\varphi (x|v).$

Definición: La complejidad condicionada autodelimitante de Chaitin inducida por el ordenador de Chaitin $C$ se define por la fórmula: $$H_C (x|v)=\min\{|y|: y\in A^*, C(y,v^*)=x\}.$$

Nota: Pongamos $H(x|v)=H_U (x|v).$

Teorema: Para cada ordenador $\varphi$: $$K(x|v)\leq K_\varphi(x|v)+O(1).$$

Demostración: Está clara por la universalidad de $\psi$.

Teorema: Para cada ordenador de Chaitin $C$: $$H(x|v)\leq H_C(x|v)+O(1).$$

Demostración: Está clara por la universalidad de $U$.

Nota: Dados dos ordenadores universales $\psi,\omega$ existe una constante $c$ tal que para todo $x\in A^*$ y para todo $y\in A^*$:
$$
\begin{aligned}
|K_\psi(x)-K_\omega(x)|&\leq c,\\
|K_\psi(x|y)-K_\omega(x|y)|&\leq c,
\end{aligned}$$
luego las complejidades absolutas y condicionadas son asintóticamente independientes del ordenador universal usado.

Teorema: Para todo par de cadenas $x,v\in A^*$ $$0\leq K(x|v)<\infty, 0<H(x|v)<\infty.$$

Demostración: Las secciones $U_v$, $\psi_v$ son sobreyectivas.

Fijemos una biyección computable $\langle \cdot, \cdot \rangle: A^*\times A^*\to A^*.$ Sean $(\cdot)_1$ y $(\cdot)_2$ las funciones componentes de la función inversa.

Definición: $H_C(x,y)=H_C(\langle x,y\rangle)$

Nota: Pongamos $H(x,y)=H_U(\langle x,y\rangle).$

Teorema: $H(x,y)=H(y,x)+O(1).$

Demostración: Si $U$ es el ordenador universal de Chaitin, definimos el ordenador de Chaitin $$C(u,\lambda)=\langle (U(u,\lambda))_2,(U(u,\lambda))_1\rangle$$

Tenemos
$$
\begin{aligned}
H(x,y)&=H(\langle x,y\rangle)\\
&\leq H_C(\langle x,y\rangle)+c\\
&=\min\{|u|: C(u,\lambda)=\langle x,y\rangle \}+c\\
&=\min\{|u|: \langle (U(u,\lambda))_2,(U(u,\lambda))_1\rangle =\langle x,y\rangle \}+c\\
&=\min\{|u|: (U(u,\lambda))_2=x, (U(u,\lambda))_1=y\}+c\\
&=\min\{|u|: U(u,\lambda) =\langle y,x\rangle \}+c\\
&=H(y,x)+c.
\end{aligned}
$$

Nota: Si $f:A^*\to A^*$ es una biyección computable, entonces $H(f(x))=H(x)+O(1)$. En efecto, basta usar el ordenador de Chaitin $C(u,\lambda)=f(U(u,\lambda))$. En la prueba del teorema anterior usamos la función $f(x)=\langle (x)_2,(x)_1\rangle.$

Teorema: 

  1. $H(x|x)=O(1)$
  2. $H(\text{string}(H(x))|x)=O(1).$

Demostración: 

  1.  Para el ordenador de Chaitin $$C(\lambda,u)=U(u,\lambda), u\in A^*$$ se tiene que $$C(\lambda,x^*)=U(x^*,\lambda)=x$$ luego $H_C(x|x)=0$. Esto prueba la primera fórmula.
  2. Consideremos el ordenador de Chaitin $$D(\lambda,u)=\text{string}(|u|), \text{ si } U(u,\lambda)<\infty.$$ Para $u=x^*$: $$D(\lambda,x^*)=\text{string}(|x^*|)=\text{string}(H(x)),$$ luego $$H_D(\text{string}(H(x))|x)=0.$$

Teorema: Existe una constante $c>0$ tal que para todo $x,y\in A^*$

  1. $H(x)\leq H(x,y)+c$.
  2. $H(x|y)\leq H(x)+c$.
  3. $H(x,y)\leq H(x) +H(y|x)+c$
  4. $H(x,y)\leq H(x)+H(y)+c.$

Demostración: 

1. Definimos el ordenador de Chaitin $C(u,\lambda)=(U(u,\lambda))_1$. Entonces
$$
\begin{aligned}
H(x)&\leq H_C(x)+c\\
& =\min\{|u|: (U(u,\lambda))_1=x \}+c\\
&\leq \min\{|u|: (U(u,\lambda))_1=x, (U(u,\lambda))_2=y \}+c\\
&=H(x,y)+c.
\end{aligned}
$$

2. Definimos el ordenador de Chaitin
$D(u,v)=U(u,\lambda)$. Ahora
$$H_D(x|y)=\min\{|u|: D(u,y^*)=x\}=\min\{|u|: U(u,\lambda)=x\}=H(x).$$
Como $H(x|y)\leq H_D(x|y)+c$, (2) está probado.

3. Tenemos que demostrar que $H(x,y)\leq H(x)+H(y|x)+c$. Para ello vamos a construir un ordenador de Chaitin que cumpla la siguiente propiedad:
$$\text{si } U(u,x^*)=y, \text{ entonces } C(x^*u,\lambda)=\langle x,y\rangle.$$

Supongamos que ya está construido y veamos cómo probar (3). Supóngase que $H(y|x)=|u|$ con $U(u,x^*)=y$. Existe una constante $c$ tal que

$$
\begin{aligned}
H(x,y)&=H(\langle x, y \rangle)\\
&\leq H_C(\langle x,y \rangle) +c\\
&\leq |x^*u|+c\\
&=H(x)+H(y|x)+c.
\end{aligned}
$$

Falta demostrar la existencia de $C$. Para ello usaremos el conjunto infinito c.e. $V=\text{dom}(U_\lambda)$. La computación de $C$ sobre un input $(x,\lambda)$ se produce del siguiente modo:

  • Genera todos los elementos de $V$ hasta que encontremos, si es posible, una cadena $v\in V$ tal que $v<_p x.$
  • Computa $w\in A^*$ tal que $x=vw$ y trata de calcular $U(w,v)$.
  • Si $U(w,v)<\infty$, entonces $C(x,\lambda)=\langle U(v,\lambda),U(w,v) \rangle$

La función $C$ es p.c. con $C(u,v)=\infty$ si $v\neq \lambda$. Tenemos que probar que $\text{dom}(C_\lambda)$ es libre de prefijo. Para ello, supóngase que existen $x<_p y$, $x,y\in \text{dom}(C_\lambda)$. Existen cuatro cadenas $u_x,y_y\in \text{dom}(U_\lambda),$ $w_x\in \text{dom}(U_{u_x}) ,w_y\in \text{dom}(U_{u_y}),$ tales que
$$x=u_xw_x, y=u_yw_y.$$
Dado que $u_x,u_y$ son prefijos de $y$ y pertenecen al dominio de $U_\lambda$, ambos deben ser iguales $u=u_x=u_y$. Más aún, $w_x,w_y$ pertenecen al dominio de $U_{u}=U_{u_x}=U_{u_y}$, que es libre de prefijo, y $uw_x,uw_y$ son prefijos de $y$, luego $w_x=w_y$ y de aquí que $x=y$. Así queda demostrado que $C$ es un ordenador de Chaitin. Por otro lado, supóngase que $v=x^*u$ y que $U(u,x^*)=y$. Obviamente $x^*\in \text{dom}(U_\lambda)$; durnte el primer paso de la computación de $C(x^*u,\lambda)$ vamos a encontrar $x^*$; en el siguiente calcularemos $u$ y $U(u,x^*)=y<\infty$. De acuerdo con lo establecido en el tercer paso de la computación de $C$:
$$C(x^* u,\lambda)=\langle U(x^*,\lambda),U(u,x^*)\rangle=\langle x,y\rangle.$$
4. Obsérvese que
$$H(x,y)\leq H(x)+H(y|x)+c\leq H(x)+H(y)+c'$$
utilizando (3) y (2).

Teorema: [Subaditividad] $$H(xy)\leq H(x)+H(y)+O(1).$$

Demostración: Considérese el ordenador de Chaitin $$C(\omega,\lambda)=(U(\omega,\lambda))_1(U(\omega,\lambda))_2.$$

Por (4) en el teorema anterior tenemos:

$$\begin{aligned} H(xy)&\leq H_C(xy)+c\\ &=\min\{|\omega|: C(\omega,\lambda)=xy\}+c\\ &=\min\{|\omega|: (U(\omega,\lambda))_1(U(\omega,\lambda))_2=xy\}+c\\ &\leq \min\{|\omega|:  U(\omega,\lambda))_1=x, (U(\omega,\lambda))_2=y\}+c\\ &\leq\min\{|\omega|: U(\omega,\lambda)=\langle x,y\rangle\}+c\\ &\leq H(\langle x, y\rangle)+c\\ &\leq H(x)+H(y)+c'. \end{aligned}$$

Nota: Hemos demostrado en la prueba del teorema anterior que $$H(xy)\leq H(\langle x,y\rangle)+c.$$Definición: La información algorítmica mutua de dos cadenas $x$ e $y$, de acuerdo con el ordenador de Chaitin $C$ es $$H_C(x:y)=H_C(y)-H_C(y|x).$$

Nota: Para $C=U$, $H(x:y)=H_U(x:y).$

Teorema: Existe una constante $c>0$ tal que:

  1. $H(x:y)\geq -c$.
  2. $H(x:y)\leq H(x)+H(y)-H(x,y)+c.$

Demostración:

  1. Ya sabemos que $H(y|x)\leq H(y)+c$, luego $$H(x:y)=H(y)-H(y|x)\geq H(y)-H(y)-c=c$$ y (1) está probado.
  2. Sabemos que $H(x,y)\leq H(x)+H(y|x)+c$, y de aquí $-H(y|x)\leq H(x)-H(x,y)+c$, luego $$H(x:y)=H(y)-H(y|x)\leq H(y)+H(x)-H(x,y)+c.$$

Teorema: Se cumplen las siguientes fórmulas:

  1. $H(x:x)=H(x)+O(1).$
  2. $H(x:\lambda)=O(1)$.
  3. $H(\lambda:x)=O(1).$

Demostración: 

  1. $H(x:x)=H(x)-H(x|x)$ y como $H(x|x)=O(1)$, este apartado ya está demostrado.
  2. Ya sabemos que $H(x:\lambda)\geq -c$ para una cierta constante positiva. Por otra parte $$ \begin{aligned} H(x:\lambda)&\leq H(x)+H(\lambda)-H(x,\lambda)+c'\\ &\leq H(x)-H(x,\lambda)+c''\\ \end{aligned} $$ Ahora  bien, si $C(u,\lambda)=(U(u,\lambda))_1$: $$ \begin{aligned} H(x,\lambda)&=\min\{|u|: U(u,\lambda)=\langle x,\lambda \rangle\}\\ &=\min\{|u|: (U(u,\lambda))_1=x, (U(u,\lambda))_2=\lambda\}\\ &\geq \min\{|u|: (U(u,\lambda))_1=x\}\\ &=H_C(x), \end{aligned} $$ y por ello $-H(x,\lambda)\leq -H_C(x)\leq - H(x)+c$, con lo que podemos concluir que $$H(x:\lambda)\leq H(x)-H(x,\lambda)+c''\leq H(x) -H(x) +c'''.$$
  3. Ya sabemos que $H(\lambda:y)\geq -c$. La prueba es similar a la de (2) usando el ordenador de Chaitin $D(v,\lambda)=(U(v,\lambda))_2$.

Propiedades algorítmicas de las complejidades

Definición: El conjunto de programas canónicos es $$\text{CP}=\{x^*|x\in A^*\}.$$

Definición: Un subconjunto $X\subset A^*$ es inmune si $X$ es infinito y no contiene ningún conjunto infinito computable enumerable.

Definición: Un subconjunto $X\subset A^*$ es computable si la función característica $\chi_X$ es computable.

Definición: Un subconjunto $X\subset A^*$ es computable enumerable (c.e.) si es o bien el conjunto vacío, o bien el rango de alguna función computable.

Nota: Un conjunto infinito c.e. es el rango de alguna función computable inyectiva.

Nota: Todo c.e. que sea infinito admite un subconjunto infinito computable.

Teorema: Existe una constante $c\geq 0$ tal que para todo $x\in \text{CP}$, se tiene $$H(x)\geq |x|-c_2.$$

Demostración: Consideramos el ordenador de Chaitin $$D(u,\lambda)=U(U(u,\lambda), \lambda).$$

Si $x=y^*,z=x^*$, tenemos
$$D(z,\lambda)=U(U(z,\lambda),\lambda)=U(U(x^*,\lambda),\lambda)=U(x,\lambda)=U(y^*,\lambda)=y,$$
luego
$$H_D(y)\leq |z|=|x^*|=H(x),$$
Entonces tenemos las desigualdades siguientes:
$$|x|=|y^*|=H(y)\leq H_D(y)+c\leq H(x)+c.$$

Teorema: $\text{CP}$ es inmune.

Demostración: Tenemos que demostrar que $\text{CP}$ es infinito y que si $E\subset \text{CP}$ es infinito, entonces no es c.e.

Lo primero es inmediato pues la función $x\to x^*$ es inyectiva.

Para demostrar lo segundo procedemos por reducción al absurdo. Supongamos que existe un subconjunto infinito $S\subset \text{CP}$ que es computable enumerable. Supóngase que $S$ es enumerado por la inyección computable $f:\mathbb N\to A^*$, $S=\text{rango}(f)$.

Definimos la función $g:\mathbb N\to A^*$ definida mediante la fórmula $g(0)=f(0)$ y
$$g(n+1)=f(\min\{j: |f(j)|>n+1\}),$$
La función $g$ es total (su doominio es $\mathbb N$) y computable; el rango de $g$, $S'=g(\mathbb N_+)$, es un conjunto infinito $S'\subset S$; y además $|g(i)|>i$ para todo $i>0$.

Recuérdese ahora del tema 2 que todo número natural $n>0$ tiene una representación en el conjunto libre de prefijo $\{d(x): x\in \{0,1\}^*\}$ de longitud $\log n+2\log\log n+1$ (esto está escrito con detalle en los apuntes del tema 2. Llamemos $h:\mathbb N\to A^*$ a la función computable. Consideramos el ordenador de Chaitin
$C(u,\lambda)$, definido para los $u$ pertenecientes al conjunto libre de prefijo $h(\mathbb N)$, del siguiente modo:
$$C(u,\lambda)=g(h^{-1}(u)).$$
Para todo $i>2$, si $u$ es tal que $C(u,\lambda)=g(i)$:
$$|u|\leq \log i +2\log \log i+ 1\leq 3\log i.$$
Existe una constante $c_1$ tal que
$$H(g(i))\leq H_C(g(i))+c_1\leq 3 \log i +c_1$$

Por el teorema anterior, existe una constante $c_2$ tal que $H(x)\geq |x|-c_2,$ para todo $x\in \text{CP}.$

Para todo $i>2$, $g(i)\in \text{CP}$, $|g(i)|>i$ y por lo tanto
$$i-c_2<|g(i)|-c_2\leq H(g(i))\leq 3\log i +c_1$$
Esto es una contradicción.

Nota: Los programas canónicos tienen complejidad alta.

Teorema: La función $f:A^*\to A^*$, $f(x)=x^*$ no es computable.

Demostración: La función $f$ es inyectiva y su rango es $\text{CP}$.

Teorema: $H(x)$ es semi-computable superiormente, pero no es computable.

Demostración: Hay que demostrar que el conjunto $\{(x,n): x\in A^*, n\in \mathbb N, H(x)<n\}$ es computable enumerable. Esto se tiene porque $H(x)<n$ si y solo si existe $y\in A^*$, y existe $t\in \mathbb N$ tal que $|y|<n$ y $U(y,\lambda)=x$ en a lo sumo $t$ pasos.

Para la segunda parte del teorema, vamos a demostrar un resultado algo más general, vamos a demostrar que no existe p.c. $\varphi:A^*\overset{o}{\to} \mathbb N$ de dominio infinito y tal que $H(x)=\varphi(x)$, para todo $x\in \text{dom}(\varphi)$.

Supóngase, por reducción al absurdo, que existe $\varphi$ p. c. tal que $H(x)=\varphi(x)$, para todo $x\in \text{dom}(\varphi)$, y $\varphi$ con dominio infinito. Sea $B\subset \text{dom}(\varphi)$ un subconjunto infinito computable y sea $f:A^*\overset{o}{\to} A^*$, la función parcial definida como
$$f(a_1^ia_2)=\min\{x\in B: H(x)\geq Q^i\}$$
con $i\geq 1$. Como $\varphi(x)=H(x)$ para todo $x\in B$, sigue que $f$ es p.c. Más aún, $f$ tiene grafo computable y su rango contiene cadenas de longitudes arbitrariamente grandes.

Definimos el ordenador de Chaitin $C(a_1^ia_2,\lambda)=f(a_1^ia_2)$. Para cada $i>0$
$$Q^i\leq H(f(a_1^ia_2))\leq H_C(f(a_1^ia_2))+c\leq i+1+c.$$
Esto es una contradicción.

Estimaciones cuantitativas

Teorema: Existe una constante $c>0$ tal que $$K(x)\leq |x|+c, H(x)\leq |x|+2\log |x|+c.$$

Demostración: Para $K$ tómese el ordenador $\varphi(x,\lambda)=x$, para todo $x\in A^*$. Para $H$, construimos el ordenador de Chaitin $C(d(x),\lambda)=x$, donde $|d(x)|=|x|+3\log |x|+1$.

Teorema: Para cada ordenador de Chaitin $C$ y para cada natural $n$ $$|\{x\in A^*:H_C(x)=n\}|\leq Q^n.$$

Demostración: No hay más de $Q^n$ programas de longitud $n$.

Teorema: Sea $E\subset A^*$ un conjunto con $m>0$ elementos y $\varepsilon>0$. Entonces, para todo ordenador de Chaitin $C$, $$|\{x\in E: H_C(x)\geq \log_Q m-\varepsilon\}|>m\left(1-\frac{Q^{1-\varepsilon}}{Q-1}\right).$$

Demostración:

$$
\begin{aligned}
|\{x\in E: H_C(x) \geq \log_Q m-\varepsilon\}|&=m-|\{ x\in E: H_C(x)<\log_Qm-\varepsilon\}\\
&>m-|\{x\in E: H_C(x)<\lfloor \log_Q m-\varepsilon\rfloor+1\}|\\
&=m-\sum_{0\leq i\leq \lfloor \log_Q m-\varepsilon\rfloor} |\{x\in E: H_C(x)=i\}|\\
&\geq m-\frac{Q^{\log_Q m -\varepsilon}-1}{Q-1}\\
&\geq m\left(1-\frac{Q^{1-\varepsilon}}{Q-1}\right)
\end{aligned}
$$

Teorema: Para cualquier ordenador de Chaitin $C$, para cualquier $n$ y para cualquier $\varepsilon>0$, se tiene $$|\{x\in A^n: H_C(x)\geq n-\varepsilon\}|>Q^n\left(1-\frac{Q^{1-\varepsilon}}{Q-1}\right).$$

Demostración: $E=A^n$ en el teorema anterior.

Teorema: Sea $F:A^*\to \mathbb N$ una función arbitraria tal que $H(x)\leq F(x)+O(1).$ Entonces $$|\{x\in A^*: F(x)<m\}|<Q^{m+O(1)}.$$

Demostración: Existe una constante $c$ tal que

$$\{x\in A^*: F(x)<H\}\subset \{x\in A^*: H(x)<m+c\}.$$
Consecuentemente:
$$
\begin{aligned}
\log_Q |\{ x\in A^*: F(x)<m\}| &\leq \log_Q |\{ x\in A^*: H(x)<m+c\}|\\
&\leq \log_Q \left( \frac{Q^{m+c}-1}{Q-1}\right)\\
&\leq m+c.
\end{aligned}
$$

Teorema: Sea $F:A^*\to \mathbb N$ una función semi-computable superiormente. Si existe una constante $q>0$ tal que para todo número natural
$m>0$:
$$|\{x\in A^*: F(x)<m\}|<\log m+q,$$
entonces $H(x)\leq F(x)+O(1).$

Demostración: Sea $\{(x_1,m_1),(x_2,m_2),\dots\}$ una enumeración computable del conjunto c. e. $\{(x,m)\in A^*\times \mathbb N, F(x)<m\}.$ Construimos el siguiente ordenador de Chaitin $C$ mediante el e algoritmo:

  1. Todas las cadenas $y\in A^*$ están disponibles.
  2. Para $i=1,2,\dots$ genera $(x_i,m_i)$ y elige el primer $y_i\in A^{\log m_i+q}$ y pongamos $C(d(y_i),\lambda)=x_i$
  3. La cadena $y_i$ ya no está disponible.

Ya hemos visto $d$ antes.

Probabilidades de parada

Definición: Dado un ordenador de Chaitin $C$ definimos la probabilidad:
$$P_C(x)=\sum Q^{-|u|}$$
donde la suma se extiende a aquellos $u\in A^*$ tales que $C(u,\lambda)=x$.

Definición: Dado un ordenador de Chaitin $C$ definimos las probabilidad condicionada :
$$P_C(x|y)=\sum Q^{-|u|}$$
donde la suma se extiende a aquellos $u\in A^*$ tales que $C(u,y)=x$.

Nota: Para $C=U$, escribimos $P(x)=P_U(x), P(x|y)=P_U(x|y)$.

Definición: $P_C(x)$ es la probabilidad algorítmica del ordenador $C$ con salida $x$ (mide la probabilidad de que $C$ produzca $x$).

Definición: $P_C(x|y)$ es la probabilidad condicionada algorítmica.

Teorema: Para cada ordenador de Chaitin $C$, y para todo par de cadenas

  1. $\displaystyle \Omega_C=\sum_{x\in A^*} P_C(x)\leq 1$.
  2. $\displaystyle \sum_{x\in A^*} P_C(x|y)\leq 1$.

Demostración:

  1. $\Omega_C=\sum_{x\in A^*} P_C(x)=\sum_{x\in A^*} \sum_{\{u\in A^*: C(u,\lambda)=x\}}Q^{-|u|}=\sum_{u\in \text{dom}(C_\lambda)}Q^{-|u|}\leq 1.$
  2. Completamente similar.

Nota: El número $\displaystyle \Omega_C=\sum_{x\in A^*} P_C(x) $ expresa la probabilidad de parada del ordenador $C$.

Teorema: Para todo ordenador de Chaitin $C$ y para todo par de cadenas $x,y$:

  1. $P_C(x)\geq Q^{-H_C(x)}$.
  2. $P_C(x|y)\geq Q^{-H_C(x|y)}$.

Demostración: 

  1. Es claro que $P_C(x)\geq Q^{-|u|},$ siendo $u$ tal que $|u|=H_C(x).$
  2. Igual.

Teorema: Para todo $x,y\in A^*$, $0<P(x)<1, 0<P(x|y)<1.$

Demostración: Está claro que $P(x)\geq Q^{-|x^*|}>0$, y como $\sum_{x\in A^*} P(x)\leq 1$, y teniendo en cuenta que cada elemento de la serie es $>0$ se deduce que $P(x)<1$. Un razonamiento similar sirve para $P(x|y).$

Teorema: Para todo ordenador de Chaitin $C$, para todo par de números naturales $n,m\geq 1$, las siguientes fórmulas son ciertas:

  1. $\displaystyle |\{x\in A^*: H_C(x)<m\}|<\frac{Q^m-1}{Q-1}$
  2. $\displaystyle |\{x\in A^*: H_C(x|y)<m\}|<\frac{Q^m-1}{Q-1} $
  3. $\displaystyle |\{x\in A^*:P_C(x)>n/m\}|<\frac{m}{n} $
  4. $\displaystyle |\{x\in A^*:P_C(x|y)>n/m\}|<\frac{m}{n} $

Demostración:

  1. Es por la desigualdad $|\{x\in A^*: H_C(x)=n\}|\leq Q^n.$
  2. Igual que (1).
  3. Sea $S=\{ x\in A^*: P_C(x)>n/m \}$. Por reducción al absurdo, supóngase que $|S|\geq m/n$. Entonces $$1\geq \sum_{x\in A^*}P_C(x)\geq \sum_{x\in S} P_C(x)>\frac{n}{m}|S|\geq 1$$ lo que es una contradicción.
  4. (4) Igual que (3).