La Singularidad Desnuda

Un universo impredecible de pensamientos y cavilaciones sobre ciencia, tecnología y otros conundros

Turing en una cáscara de nuez: Complejidad de Kolmogorov

Posted by Carlos en junio 28, 2007

Aprovechando unos minutos de inusual relax para la época del año en la que nos encontramos, vamos a continuar la serie sobre computabilidad. En el último apunte al respecto vimos el problema del castor afanoso que -entre otras cosas- es especialmente interesante porque proporciona un primer nexo entre calculabilidad y complejidad descriptiva. Hay que recordar que la función castor afanoso se define como el mayor valor generable por un programa de cierta longitud, y que tal como vimos no es computable. Vamos ver hoy una noción más general y realmente interesante: la complejidad de Kolmogorov.

Imaginemos que tenemos una secuencia s de símbolos tomados de un cierto alfabeto Σ. Por simplicidad, y sin pérdida de generalidad, vamos a suponer que Σ={0,1}, y que por lo tanto estamos hablando de cadenas binarias. Supongamos ahora que queremos describir esta secuencia, donde por describir nos referimos a proporcionar información suficiente para poder reproducir dicha secuencia. Informalmente hablando, si la secuencia es simple, la cantidad de información necesaria para esta descripción será pequeña (por ejemplo, una cadena formada exclusivamente por ceros puede ser descrita simplemente dando su longitud, y aclarando que todos los símbolos son ceros). Por otra parte, es posible que no seamos capaces de discernir ningún patrón en los símbolos, y no nos quede otro remedio que usar la misma secuencia como su propia descripción.

De una manera más formal, imaginemos un cierto lenguaje L que usaremos para describir las cadenas de símbolos. Puesto que queremos evitar la ambigüedad del lenguaje natural, vamos a emplear un lenguaje puramente computacional. Por ejemplo, podemos considerar que L es nuestro lenguaje de programación favorito: haskell, perl, smalltalk, … Entonces, una descripción de una cadena de símbolos será un programa que la genera, e.g., la imprime en pantalla. Hecho esto, definimos la complejidad de Kolmogorov K(s) de una cierta cadena de símbolos s como el tamaño (definido de alguna manera razonable) del programa más pequeño que la genera.

Una primera consideración que nos puede venir a la mente de manera inmediata es que dicho tamaño es muy dependiente del lenguaje descriptivo que empleemos. La dependencia es cierta, pero no es muy preocupante ya que se reduce a una cierta constante, esto es, dados dos lenguajes L1 y L2, y cualquier cadena de símbolos s, |K2(s)-K2(s)| < c. Esto puede parecer sorprendente, pero no lo es, ya que lo único que necesitamos para pasar de una descripción en L1 a otra en L2 es un programa intérprete de L1 escrito en L2. Dicho intérprete podrá ser más o menos largo, pero es fijo, por lo que su tamaño es una constante (y el tamaño del programa correspondiente en L2 es el tamaño del programa en L1 más el del intérprete). Otro resultado interesante pero menos sorprendente es que existe una constante c (dependiente del lenguaje) tal que para cualquier cadena s, K(s) < |s| + c. Esto es fácil de ver, si pensamos que en el peor caso basta con confeccionar un programa que contenga la propia cadena como constante interna.

Dicho lo anterior, uno de los aspectos más interesantes de la complejidad de Kolmogorov es el que hace referencia a la noción de compresibilidad. Si tenemos una cadena s y un programa P más pequeño que s que la describe, entonces dicho programa puede interpretarse como una compresión (sin pérdida de información) de s. Por lo tanto, si K(s)<|s| diremos que s es compresible. Es fácil ver que no todas las cadenas son compresibles, esto es, hay cadenas s que son incompresibles: K(s) >= |s|. Por ejemplo, si P es el programa más pequeño que describe a s (i.e., K(s) = |P|), y pudiéramos comprimir al propio P usando el mismo lenguaje en el que está escrito, tendríamos una descripción Q más corta de s, lo que suponíamos que no existía. Siendo estrictos, en realidad una vez que ejecutáramos Q, tendríamos que dar la orden de ejecutar la salida que ha producido –P– para obtener s, por lo que incluyendo el tamaño de dicha orden llegamos a que K(s) >= |s|-c (y decimos entonces que s es c-incompresible). En cualquier caso, existen (|Σ|n-1)/(|Σ|-1) cadenas de menos de n símbolos, y |Σ|n cadenas de n símbolos, esto es, más que la primera cantidad por lo que no se puede hacer una correspondencia biyectiva entre ellas, y por lo tanto existen cadenas 1-incompresibles.

El próximo día exploraremos más en detalle las propiedades algorítmicas de la complejidad de Kolmogorov, y veremos que no sólo no es computable, sino que a través de ella llegamos una vez más a los teoremas de incompletitud de Gödel.

Enviar a Blog Memes Enviar a del.icio.us Enviar a digg Enviar a fresqui Enviar a menéame

Anuncios

10 comentarios to “Turing en una cáscara de nuez: Complejidad de Kolmogorov”

  1. Vaya, estos artículos siempre me encantan y aprendo algo nuevo, ¿puedo preguntar a qué te dedicas en la actualidad?, si lo has puesto en algún lado ya, perdón por no mirar mejor :D, un saludo.

  2. G said

    llegará el día que tendré que estudiar en serio este tema. ¿qué recomendarías como para empezar a leer?

  3. Carlos said

    @J: Pues me dedico a un cocktail de docencia, investigación y administración (o sea, trabajo en la Universidad). Los tres componentes tienen sus cosas buenas y sus cosas regulares, y el hecho de que la proporción de los ingredientes sea incontrolable (bueno, la administración tiende a crecer siempre) le da su punto de picante 😉 .

  4. Carlos said

    @G: Si lo que te interesa es la calculabilidad y la complejidad, un buen punto de partida es el libro de Papadimitriou:

    Christos H. Papadimitriou, Computational Complexity, Addison Wesley, 1993

    Es un texto clásico y cubre bastante bien el área, aunque cosas como la complejidad de Kolmogorov no se estudian (apenas se le dedica una mención en un ejercicio propuesto). Sobre este último tema hay un libro de Ming Li y Paul Vitanyi:

    Ming Li, Paul Vitanyi, An Introduction to Kolmogorov Complexity and Its Applications, Springer Verlag, 1997

    A nivel más popular, Gregory Chaitin tiene varios libros sobre “metamatemáticas” y toca algunos de estos temas. Por ejemplo,

    Gregory J. Chaitin, The Unknowable, Springer-Verlag, 1999

    Saludos.

  5. Villa said

    A los interesados en teoría de la información, complejidad, Kolmogorov y Chaitin, también les interesará la complejidad “funcional” de la información del grupo de Szostak: http://www.pnas.org/cgi/reprint/0701744104v1.pdf
    “Functional information and the emergence of biocomplexity”.

  6. Pérez Poch said

    Los libros de Chaitin -en su parte filosófica-, como introducción, pueden dar lugar a muchos equívocos, más debido a su aparente sencillez. Más valen para repasar lo que ya se sabe; todo lo que te parezca inexacto o fantástico en Chaitin, en contraste con lo que ya sabes, seguro que lo es… Le tengo bastante “tirria”, no sé si se nota.

    Roy Solomonoff, otra de las madres del invento de la complejidad algorítmica, tiene su página en internet, con bastantes textos actuales y pasados:
    http://world.std.com/~rjs/ray.html

  7. Pérez Poch said

    Acabo de comprobar en la wikipedia que no soy el único con “tirria” hacia Chaitin…

  8. Carlos said

    Uno de los problemas de Chaitin es su ego sobredimensionado. Hace falta echarle valor para autoproclamarse a la altura de Turing y Gödel, como hace él. No sé si el autobombo le irá bien para vender libros, que es lo probablemente lo que busca, pero desde luego no suscita muchas simpatías tampoco por mi parte. Lo que tiene escrito a nivel popular es como indicas muy superficial, y no adecuado como introducción técnica. Eso sí, sus libros tienen el mérito de ser posiblemente los que mayor densidad de signos de admiración por párrafo tengan en el mercado 😉 .

  9. Pérez Poch said

    Efectivamente, eso es lo que me irrita de Chatin. Pero aún es más grave que se considere ¡superior! a Leibniz, incluso a la caricatura de Leibniz que aparece en sus escritos. Además, la interpretación “revolucionaria” que hace de resultados ¿propios? y ajenos me parece completamente vacía. Si no estuviera destinada a halagar a los informáticos -universo digital, matemáticas “experimentales” asistidas por ordenador y tal- ya habria sido denunciada como una impostura intelectual más. Sin embargo, ahí le tenemos, con un “artículo revolucionario” en el “investigación y ciencia” cada tres años. Lo mismo pienso de Kosko, el divulgador de la lógica borrosa en obras como “El cielo en un chip”.

    No les crítico por lo que defienden, sino por las formas. Un Daniel Dennett defiende a veces cosas parecidas, pero lo hace con un estilo ameno que no insulta a la inteligencia del lector ni a los que sostienen otros puntos de vista; cuando plantea una paradoja, hace pensar, no como otros que parecen asustar a los niños. En fin, cosas de un racionalista anticuado.

    Por cierto, releo mis propios comentarios y también me parecen irritantes. ¿Qué le importa a nadie a quien le tengo tirria y a quien no? Lamento haber participado con una observación tan poco construcitva: “Procura que tus palabras valgan más que tu silencio” (proverbio hindú).

    Por recierto, la serie de “Turing en un cáscara…” sigue teniendo una gran calidad. aunque la cáscara de nuez empieza a ser un caparazón de tortuga (algo inevitable, dado el interés y los vericuetos del tema).

  10. […] Turing en una cáscara de nuez: Complejidad de Kolmogorov […]

Sorry, the comment form is closed at this time.

 
A %d blogueros les gusta esto: