Complexidade de Kolmogorov

A complexidade de Kolmogorov é unha teoría da información e da aleatoriedade, profunda e sofisticada, que trata da cantidade de información dos obxectos individuais, medida a través do tamaño da súa menor descrición algorítmica. É unha noción moderna de aleatoriedade, e refírese a un concepto puntual de aleatoriedade, no canto dunha aleatoriedade media como o fai a teoría da probabilidade. É un ramo derivado da teoría da información de Claude E. Shannon, aínda que hoxe poida ser considerada unha área de investigación madura e autónoma.

A complexidade de Kolmogorov define unha nova teoría da información, chamada teoría algorítmica da información (por tratar con algoritmos). Úsase a Máquina de Turing como mecanismo para describir os obxectos (para definir os algoritmos).

Orixe

A complexidade de Kolmogorov ten súa orixe nos anos 1960, cando Andrei Kolmogorov, Ray Solomonoff e Gregory Chaitin desenvolveron, de forma independente, unha teoría da información baseada no tamaño dos programas para a Máquina de Turing. Acordouse chamar a área xenericamente como "complexidade de Kolmogorov" en homenaxe ao famoso matemático ruso, e fundador da área, Andrei Nikolaevich Kolmogorov (1903-1987).

Definición

A complexidade de Kolmogorov está definida sobre o conxunto de cadeas binarias (secuencias de ceros e uns). Ela asocia a cada cadea binaria un valor numérico que é súa "complexidade".

A complexidade de Kolmogorov pode ser definida simplificadamente como o tamaño do menor programa (ou descrición algorítmica) que calcula na Máquina de Turing unha determinada cadea binaria.

Esíxese que o conxunto de descricións (programas) forme un conxunto libre de prefixo, e chámase a esta complexidade "complexidade de prefixo", representada por $K(x)$. Para salientar a Máquina que está sendo usada para definir a complexidade podemos escribir $K_{M}(x)$ en vez de $K(x)$, onde $M$ é unha Máquina de Turing en particular.

Tamén podemos definir unha complexidade condicional, $K(x|y)$, definida como o tamaño do programa que calcula $x$ a partir de $y$, que é dado como entrada do programa. Intuitivamente, $K(x|y)$ representa a cantidade de información que debemos sumar á información en $y$ para calcular $x$.

É importante que se fundamente ben o concepto de descrición (ou sexa, formalmente definido como un programa para a máquina de Turing) para evitar paradoxos. Os paradoxos (ou antinomías) son bastante frecuentes na historia da matemática. Podemos citar o famoso "paradoxo do barbeiro", de Bertrand Russel, que di que "o barbeiro é aquel que afeita aos homes que non se afeitan a si mesmos". O paradoxo é obtido ao preguntar se o barbeiro se barbea a si mesmo.

Máquina de Turing

Artigo principal: Máquina de Turing.

A Máquina de Turing é un dispositivo que foi proposto en 1936 por Alan Turing co obxectivo de formalizar matematicamente o que entendemos por "computador". Ela está formada basicamente por unha fita (cinta) na cal un cabezallo pode escribir símbolos dun conxunto predefinido, e así cálculos de diversos tipos poden ser feitos apenas cos movementos deste cabezal sobre a fita.

Unha propiedade importante da Máquina de Turing é a universalidade, ou sexa, a capacidade da Máquina de Turing de simular calquera outra máquina. Por isto, podemos chamala máquina universal.

Teorema da Invarianza

Da forma como foi definido, pode parecer que a complexidade de Kolmogorov permanece dependente da máquina escollida como máquina de referencia. Porén, existe un teorema (chamado Teorema da Invarianza) que proba que todas as máquinas universais (ou sexa, que ten a capacidade de simular todas as outras máquinas de Turing concibibles) resultan no mesmo valor de complexidade, a non ser por unha constante que é asintoticamente desprezable: $K_{U1}(x)\leq K_{U2}(x)+c$, para algunha constante $c$, e $U1$ e $U2$ son dúas máquinas universais calquera.

Isto significa que a complexidade pasa a ser un atributo intrínseco do obxecto, independente da máquina universal escollida como máquina de referencia.

Principio de Occam

Artigo principal: Navalla de Occam.

Ao medir a complexidade dunha cadea polo tamaño do menor programa, a complexidade de Kolmogorov reedita un antigo principio, de autoría de William de Ockham (1285?-1349?), que ficou coñecido como Principio de Occam, que di que "as entidades non deben ser multiplicadas innecesariamente".

O Principio de Occam significa que entre todas as teorías que explican un fenómeno, a máis simple (ou menor) é a mellor para este fin. Isto ten evidentes connotacións filosóficas relacionadas coa expresividade dos métodos de descrición e cos sistemas formais.

Algunhas propiedades

Trivialmente, $K(x)\leq |x|+c$, para algún $c$, onde $|x|$ denota o tamaño da cadea (string) $x$, xa que calquera cadea pode ser computada por un programa que a teña almacenada literalmente no programa.

Tamén sabemos que $K(x|y)\leq K(x)+c$, xa que, na complexidade condicional, a presenza de $y$ é unha información a máis que é dada ao programa que calculará $x$.

Se $x$ denota unha cadea binaria que é resultado dun $p$-proceso de Bernoulli, entón ${\frac {1}{m}}K(x)\rightarrow H(p,1-p)$ en probabilidade, onde $H(p,1-p)$ é a entropía do proceso. Isto significa que $K(x)$ é asintoticamente converxente á entropía da teoría da información clásica.

Incompresividade de cadeas binarias

Se para unha cadea binaria $x$, $K(x)\geq |x|-c$, para algún $c$, entón dicimos que $x$ é incompresible.

Kolmogorov asociou o concepto de incompresividade co concepto de aleatoriedade, co obxectivo de definir secuencias aleatorias, e así fornecer unha base teórica para probabilidades e estatística.

Obxectivo da complexidade de Kolmogorov

O obxectivo orixinal do traballo de Kolmogorov era obter unha definición formal de secuencia aleatoria. Kolmogorov observou que algunhas secuencias binarias podían comprimirse algoritmicamente. Hoxe en día, a maioría das persoas están afeitas a usar programas de compresión de datos, tales como winzip, gzip etc. Así, a idea de que os datos se poidan comprimir non é estraña.

É doado entender que un número como 1 000 000 000 na base 10 pode facilmente expresarse como $10^{9}$, mentres que o número 5 321 478 927, escollido arbitrariamente, non podería ser expresado desta forma compacta.

Se tomarmos as cadeas binarias 11111111111111111111 e 10110011010111011010, aceptaríamos facilmente a segunda como resultante do lanzamento sucesivo dunha moeda honesta (1=cara e 0=coroa); porén, dificilmente a primeira secuencia podería ser resultado dun experimento realmente aleatorio. Notamos que a primeira cadea podería ser computada polo programa:

FOR I=1 TO 20 PRINT 1

Que é un programa pequeno en relación ao tamaño da cadea. A segunda cadea non pode ser calculada por un programa tan curto, pois el deberá conter a propia cadea literalmente almacenada dentro do programa:

PRINT 10110011010111011010

Kolmogorov postulou que as secuencias que non poden ser comprimidas algoritmicamente nunha descrición de tamaño moito menor que a secuencia orixinal son secuencias aleatorias (no sentido estocástico do termo). Esta definición só funciona se se admiten soamente descricións dentro dunha clase de descricións libres de prefixo (ou sexa que ningunha descrición sexa prefixo doutra da clase).

Desigualdade de Kraft

A razón para esixir que o conxunto de descricións (programas) forme un conxunto libre de prefixo debese a desigualdade de Kraft, expresión ben coñecida na teoría da información clásica. Ela significa que a serie $\sum 2^{-K(x)}$ converxe. Esta é unha propiedade importante da complexidade de Kolmogorov.

Secuencias Aleatorias de Martin-Löf

Unha resposta consistente ao problema de definir o concepto de secuencia aleatoria foi dada por Martin-Löf. A definición de Martin-Löf baséase na teoría da medida, e na existencia dun conxunto efectivo nulo máximo, no conxunto das cadeas binarias. Isto significa a existencia dun conxunto nulo (con baixa probabilidade de ocorrencia) que contén todos os conxuntos nulos cuxas cadeas poden ser algoritmicamente xeradas. Esta definición equivale a afirmar a existencia dun teste de aleatoriedade universal. Interesante observar que a definición de Martin-Löf é equivalente á definición de secuencia aleatoria dada pola complexidade de Kolmogorov (vía incompresividade das cadeas).

Aplicacións

Solomonoff propuxo o uso da regra de Bayes para obter previsión indutiva, ou sexa, para prever a secuencia dunha cadea binaria. Para isto el usou como probabilidade previa a probabilidade universal, que pode ser definida como $2^{-K(x)}$, porque ela domina toda probabilidade previa semi-computable concibible. Isto constitúese no núcleo dos métodos de intelixencia artificial MDL (minimum description length) e MML (minimum message length).

A complexidade $K(x|y)$ induce un concepto de distancia (ou similitude), chamada distancia de información, que é unha medida a priori e absoluta sobre o conxunto das cadeas binarias. Esta distancia pode ser aplicada en diversos e diferentes contextos de forma moi similar a outras medidas de distancia definidas nas matemáticas. O interesante é que podemos aproximar esta medida usando un programa compresor de dados e efectuar medicións empíricas. Destácanse como aplicacións desta distancia o recoñecemento dos xenomas, a clasificación automática de música, e o establecemento dunha xerarquía de linguaxes humanas.

Chaitin construíu un paradoxo co tamaño dos programas que se constitúe nunha proba alternativa ao que ficou coñecido como proba de Gödel (ou Teorema da incompletude de Gödel). Chaitin baseouse no paradoxo de Berry que supón considerar o menor número enteiro positivo que non pode ser definido por unha frase con menos de 1 000 000 000 de caracteres. Non obstante, a propia definición do problema define o número e ten menos de 1 000 000 000 de caracteres, o que é unha contradición. Isto resulta que as cadeas non se poden producir por programas que teñan menos complexidade que a propia cadea, sendo isto un límite dos sistemas formais.

Unha outra interesante aplicación de complexidade de Kolmogorov é o número máxico e místico $\Omega$, proposto por Chaitin, definido como: $\Omega =\sum _{p}2^{-|p|}.$ Nesta fórmula, $p$ representa un programa que para (finaliza) e $|p|$ é o tamaño deste programa. É interesante observar que $0\leq \Omega \leq 1$, representando $\Omega$ a probabilidade de que un programa calquera finalice. $\Omega$ é un número real aleatorio (cuxos díxitos forman unha secuencia aleatoria) e non computable (ou sexa, non pode ser computado por un programa na máquina de Turing). Alén disto, $\Omega$ contén en si, da forma máis compacta posible, todas as verdades matemáticas posibles de seren expresas.

Diversas outras aplicacións da teoría foron desenvolvidas desde entón: intelixencia artificial, linguaxes formais, complexidade computacional, teoría de grafos, biotecnoloxía etc.

Véxase tamén

Outros artigos

• Andrei Nikolaevich Kolmogorov.
• Teoría da información.
• Teoría da probabilidade.
• Probabilidade.
• Aleatoriedade.
• Teoría da computación.
• Máquina de Turing.

Ligazóns externas

• Kolmogorov Complexity Resources
• Grupo Omega-pi
• Gregory Chaitin home page
• Paul Vitányi home page
• Ray Solomonoff home page
• Kolmogorov Biography Arquivado 28 de xullo de 2005 en Wayback Machine.