La Singularidad Desnuda

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

Posts Tagged ‘Compresibilidad’

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

Posted in Calculabilidad, Matemáticas | Etiquetado: , , | 10 Comments »