Complexidade de Kolmogorov

A complexidade de Kolmogorov é uma teoria da informação e da aleatoriedade, profunda e sofisticada, que trata da quantidade de informação de objetos individuais, medida através do tamanho de sua menor descrição algorítmica. Ela é uma noção moderna de aleatoriedade, e refere-se a um conceito pontual de aleatoriedade, ao invés de uma aleatoriedade média como o faz a teoria das probabilidades. Ela é um ramo derivado da teoria da informação de Claude Shannon, embora hoje possa ser considerada uma área de pesquisa madura e autônoma.

Complexidade de Kolmogorov define uma nova teoria da informação, chamada teoria algorítmica da informação (por tratar com algoritmos). A Máquina de Turing é usada como mecanismo para descrever os objetos (para definir os algoritmos).

Origem

A complexidade de Kolmogorov tem sua origem nos anos 1960, quando Andrei Kolmogorov, Ray Solomonoff e Gregory Chaitin desenvolveram, de forma independente, uma teoria da informação baseada no tamanho dos programas para a Máquina de Turing. Convencionou-se chamar a área genericamente de "complexidade de Kolmogorov" em homenagem ao famoso matemático russo, e fundador da área, Andrei Nikolaevich Kolmogorov (1903-1987).

Definição

A complexidade de Kolmogorov está definida sobre o conjunto de strings binárias (seqüências de zeros e uns). Ela associa a cada string binária um valor numérico que é sua "complexidade".

A complexidade de Kolmogorov pode ser definida simplificadamente como o tamanho do menor programa (ou descrição algoritmica) que computa na Máquina de Turing uma determinada string binária.

Exige-se que o conjunto de descrições (programas) forme um conjunto livre de prefixo, e se chama esta complexidade de "complexidade de prefixo", representada por $K(x)$ . Para enfatizar a Máquina que está sendo usada para definir a complexidade podemos escrever $K_{M}(x)$ ao invés de $K(x)$ , onde $M$ é uma Máquina de Turing em particular.

Também podemos definir uma complexidade condicional, $K(x|y)$ , definida como o tamanho do programa que computa $x$ a partir de $y$ , que é dado como entrada do programa. Intuitivamente, $K(x|y)$ representa a quantidade de informação que devemos adicionar à informação em $y$ para computar $x$ .

Importante que o conceito de descrição seja bem fundamentado (ou seja, formalmente definido como um programa para a máquina de Turing) para evitar paradoxos. Paradoxos (ou antinômias) são bastante freqüentes na história da matemática. Podemos citar o famoso "paradoxo do barbeiro", de autoria de Bertrand Russel, que diz que "o barbeiro é aquele que barbeia os homens que não barbeiam a si próprios". O paradoxo é obtido ao perguntar se o barbeiro barbeia a si próprio.

Máquina de Turing

A Máquina de Turing é um dispositivo que foi proposto em 1936 por Alan Turing com o objetivo de formalizar matematicamente o que entendemos por "computador". Ela é basicamente formada por uma fita na qual um cabeçote pode escrever símbolos de um conjunto pré-definido, e assim cálculos de diversos tipos podem ser feitos apenas com os movimentos deste cabeçote sobre a fita.

Uma propriedade importante da Máquina de Turing é a universalidade, ou seja, a capacidade da Máquina de Turing de simular qualquer outra máquina. Por isto, podemos chama-la de máquina universal.

Teorema da Invariância

Da forma como foi definido, pode parecer que a complexidade de Kolmogorov permanece dependente da máquina escolhida como máquina de referência. No entanto, existe um teorema (chamado Teorema da Invariância) que prova que todas as máquinas universais (ou seja, que tem a capacidade de simular todas as outras máquinas de Turing concebíveis) resultam no mesmo valor de complexidade, a não ser por uma constante que é assintoticamente desprezável: $K_{U1}(x)\leq K_{U2}(x)+c$ , para alguma constante $c$ , e $U1$ e $U2$ são duas máquinas universais quaisquer.

Isto significa que a complexidade passa a ser um atributo intrínseco do objeto, independente da máquina universal escolhida como máquina de referência.

Princípio de Occam

Ao medir a complexidade de uma string pelo tamanho do menor programa, a complexidade de Kolmogorov reedita um antigo princípio, de autoria de William de Ockham (1285?-1349?), que ficou conhecido como Navalha de Occam, que diz que "entidades não devem ser multiplicadas desnecessariamente".

O Princípio de Occam significa que entre todas as teorias que representam um fenômeno, a mais simples (ou menor) é a melhor para este fim. Isto tem evidentes conotações filosóficas relacionadas com a expressividade dos métodos de descrição e com os sistemas formais.

Algumas propriedades

Trivialmente, $K(x)\leq |x|+c$ , para algum $c$ , onde $|x|$ denota o tamanho da string $x$ , já que qualquer string pode ser computada por um programa que a tem armazenada literalmente no programa.

Também sabemos que $K(x|y)\leq K(x)+c$ , já que, na complexidade condicional, a presença de $y$ é uma informação a mais que é fornecida ao programa que computará $x$ .

Se $x$ denota uma string binária que é resultado de um $p$ -processo de Bernoulli, então ${\frac {1}{n}}K(x)\rightarrow H(p,1-p)$ em probabilidade, onde $H(p,1-p)$ é a entropia do processo. Isto significa que $K(x)$ é assintoticamente convergente à entropia da teoria da informação clássica.

Incompressividade de strings binárias

Se para uma string binária $x$ , $K(x)\geq |x|-c$ , para algum $c$ , então dizemos que $x$ é incompressível.

Kolmogorov associou o conceito de incompressividade com o conceito de aleatoriedade, com o objetivo de definir seqüências aleatórias, e assim fornecer uma base teórica para probabilidades e estatística.

Objetivo da complexidade de Kolmogorov

O objetivo original do trabalho de Kolmogorov era obter uma definição formal de seqüência aleatória. Kolmogorov observou que algumas seqüências binárias podiam ser comprimidas algoritmicamente. Nos dias de hoje, a maioria das pessoas está acostumada a usar programas de compressão de dados, tais como winzip, gzip, arj, etc. Assim, a ideia que dados possam ser comprimidos não é de todo estranha.

Fica fácil perceber que um número como 1.000.000.000 na base 10 pode ser facilmente expresso como $10^{9}$ , enquanto que o número 5.321.478.927, escolhido arbitrariamente, não poderia ser expresso desta forma compacta.

Se tomarmos as strings binárias 11111111111111111111 e 10110011010111011010, aceitaríamos facilmente a segunda como sendo resultante do lançamento sucessivo de uma moeda honesta (1=cara e 0=coroa). No entanto, dificilmente a primeira seqüência poderia ser resultado de um experimento realmente aleatório. Notamos que a primeira string poderia ser computada pelo programa:

FOR I=1 TO 20 PRINT 1

Que é um programa pequeno em relação ao tamanho da string. Já a segunda string não pode ser computada por um programa tão curto, pois ele deverá conter a própria string literalmente armazenada dentro do programa:

PRINT 10110011010111011010

Kolmogorov postulou que seqüências que não podem ser comprimidas algoritmicamente em uma descrição de tamanho muito menor que a seqüência original são seqüências aleatórias (no sentido estocástico do termo). Esta definição só funciona se forem admitidas apenas descrições dentro de uma classe de descrições livres de prefixo (ou seja que nenhuma descrição seja prefixo de outra da classe).

Desigualdade de Kraft

A razão para exigir que o conjunto de descrições (programas) forme um conjunto livre de prefixo deve-se a desigualdade de Kraft, expressão bem conhecida na teoria da informação clássica. Ela significa que a série $\sum 2^{-K(x)}$ converge. Esta é uma propriedade importante da complexidade de Kolmogorov.

Seqüências Aleatórias de Martin-Löf

Uma resposta consistente ao problema de definir o conceito de seqüência aleatória foi dada por Per Martin-Löf. A definição de Martin-Löf baseia-se em teoria da medida, e na existência de um conjunto efetivo nulo maximal, no conjunto das strings binárias. Isto significa a existência de um conjunto nulo (com baixa probabilidade de ocorrência) que contém todos os conjuntos nulos cujas strings podem ser algoritmicamente geradas. Esta definição equivale a afirmar a existência de um teste de aleatoriedade universal. Interessante observar que a definição de Martin-Löf é equivalente à definição de seqüência aleatória dada pela complexidade de Kolmogorov (via incompressividade das strings).

Aplicações

Solomonoff propôs o uso da regra de Bayes para obter previsão indutiva, ou seja, para prever a seqüência de uma string binária. Para isto ele usou como probabilidade prévia a probabilidade universal, que pode ser definida como $2^{-K(x)}$ , porque ela domina toda probabilidade prévia semi-computável concebível. Isto constitui-se no núcleo dos métodos de inteligência artificial MDL (minimum description length) e MML (minimum message length).

A complexidade $K(x|y)$ induz um conceito de distância (ou similaridade), chamada distância de informação, que é uma medida a priori e absoluta sobre o conjunto das strings binárias. Esta distância pode ser aplicada em diversos e diferentes contextos de forma muito similar a outras medidas de distância definidas na matemática. O interessante é que podemos aproximar esta medida usando um programa compressor de dados e efetuar medições empíricas. Destacam-se como aplicações desta distância o reconhecimento de genoma, a classificação automática de música, e o estabelecimento de uma hierarquia de linguagens humanas.

Chaitin construiu um paradoxo envolvendo o tamanho dos programas que constitui-se em uma prova alternativa ao que ficou conhecido como prova de Gödel (ou Teorema da incompletude de Gödel). Chaitin baseou-se no paradoxo de Berry que supõe considerar o menor número inteiro positivo que não pode ser definido por uma frase em português com menos que 1.000.000.000 de caracteres. No entanto, a própria definição do problema define o número e tem menos de 1.000.000.000 de caracteres, o que é uma contradição. Isto resulta que strings não podem ser produzidas por programas que tenham menos complexidade que a própria string, sendo isto um limite dos sistemas formais.

Uma outra interessante aplicação de complexidade de Kolmogorov é o número mágico e místico $\Omega$ , proposto por Chaitin, definido como: $\Omega =\sum _{p}2^{-|p|}.$ Nesta fórmula, $p$ representa um programa que pára (finaliza) e $|p|$ é o tamanho deste programa. É interessante observar que $0\leq \Omega \leq 1$ , representando $\Omega$ a probabilidade de um programa qualquer parar (finalizar). $\Omega$ é um número real aleatório (cujos dígitos formam uma seqüência aleatória) e não computável (ou seja, não pode ser computado por um programa na máquina de Turing). Além disto, $\Omega$ contém em si, da forma mais compacta possível, todas as verdades matemáticas possíveis de serem expressas.

Diversas outras aplicações da teoria foram desenvolvidas desde então: inteligência artificial, linguagens formais, complexidade computacional, teoria dos grafos, biotecnologia, etc.