Siguiente: Definiciones básicas
Un nivel arriba: Complejidad de Kolmogorov
Anterior: Introducción
Identificaremos a N con
mediante la correspondencia
donde
((n)2,k es la representación en base 2 de n utilizando exactamente k bits).
En la Figura 1 presentamos esta correspondencia. Cada entrada es de la forma
.
Figure:
Correspondencia
.
![\begin{figure}\begin{displaymath}\begin{array}{cccccccccccccccc}
\frac{\mbox{\...
...\vdots & \vdots & \vdots & \vdots
\end{array}\end{displaymath}
\end{figure}](img2196.gif) |
x(n) es pues una cadena de longitud
.
La función inversa es
Denotemos por |x| a la longitud de la cadena x. Resulta claro que
n(x)=2|x|-1+(x)2.
Esta última función es un programa universal S que dado el código p, como una cadena en
,
da el número n.
La complejidad de Kolmogorov de una cadena x es la longitud del mínimo programa p que reconstruye a x:
Guillermo Morales-Luna
2000-07-10