Siguiente: Presentación de la teoría Un nivel arriba: Complejidad de Kolmogorov Anterior: Complejidad de Kolmogorov

Introducción

La información contenida en una cadena de caracteres la podemos representar como la longitud del programa mínimo para construirla.

• 1ⁿ se construye con un programa de longitud $O(\log n)$.
• $\pi=3.14159\ldots$ se construye con un programa de longitud O(1).

Conforme la cadena dada sea más ``regular'', tanto más ``comprimible'' ha de ser: Un programa que la construya será muy compacto. Así pues la noción de ``aleatoriedad'' puede identificarse como ``no-compresibilidad''.


Definición: Una sucesión

$$\left(a_n\right)_{n\in N}\in \{0,1\}^{<\omega}$$

es un colectivo si

1.

La probabilidad de aparición de 1 en la sucesión está bien definida:

$$\exists p\in[0,1]:\;\lim_{n\rightarrow \infty}\frac{1}{n+1}\mbox{\rm card}\{m< n\vert a_m=1\}=p.$$

2.

Dada una función $\phi:\{0,1\}^{*}\rightarrow \{0,1\}$ definamos la sucesión

$$\mbox{\bf s}_{\phi}=\left(s_n\right)_{n\in N}$$

haciendo

$$\begin{eqnarray*}s_0 &=& \mathop{\rm Min}\{m\vert\phi(a_0\ldots a_{m-1})=1\} \\ ... ...hop{\rm Min}\{m\vert\phi(a_0\ldots a_{m-1})=1\;\land\; m>s_n\} \end{eqnarray*}$$

Pues bien, para la noción de ``colectivo'' hemos de tener también que para todo $\phi$, en una clase de funciones dada, por ejemplo, la clase de funciones recursivas totales,

$$\lim_{n\rightarrow \infty}\frac{1}{n+1}\mbox{\rm card}\{m< n\vert a_{s_m}=1\}=p.$$

Ejemplo: Sea $A=\left(a_n\right)_{n\in N}\in \{0,1\}^{<\omega}$ una sucesión tal que satisface la primera condición anterior:

$$\exists p\in[0,1]:\;\lim_{n\rightarrow \infty}\frac{1}{n+1}\mbox{\rm card}\{m< n\vert a_m=1\}=p.$$

Consideremos la función

$$\phi_1:(a_0\ldots a_{n-1})\mapsto \left\{\begin{array}{ll} 1... ...n=1$,} \\ \perp &\mbox{\rm en otro caso.} \end{array}\right.$$

Si se cumpliera la segunda condición, hemos de tener p=1. Sin embargo para la función

$$\phi_2:(a_0\ldots a_{n-1})\mapsto \neg a_n,$$

hemos de tener que p=0. Así pues en clases grandes de funciones la definición anterior no se puede satisfacer.
Siguiente: Presentación de la teoría Un nivel arriba: Complejidad de Kolmogorov Anterior: Complejidad de Kolmogorov