Complexidade de Kolmogorov - Kolmogorov complexity

Esta imagem ilustra parte do fractal do conjunto de Mandelbrot . O simples armazenamento da cor de 24 bits de cada pixel nesta imagem exigiria 23 milhões de bytes, mas um pequeno programa de computador pode reproduzir esses 23 MB usando a definição do conjunto de Mandelbrot e as coordenadas dos cantos da imagem. Portanto, a complexidade de Kolmogorov do arquivo bruto que codifica esse bitmap é muito menor que 23 MB em qualquer modelo pragmático de computação . A compressão de imagem de propósito geral do PNG apenas o reduz para 1,6 MB, menor do que os dados brutos, mas muito maior do que a complexidade de Kolmogorov.

Na teoria da informação algorítmica (um subcampo da ciência da computação e matemática ), a complexidade de Kolmogorov de um objeto, como um pedaço de texto, é o comprimento de um programa de computador mais curto (em uma linguagem de programação predeterminada ) que produz o objeto como saída. É uma medida das computacionais recursos necessários para especificar o objecto, e é também conhecida como a complexidade algorítmica , complexidade Solomonoff-Kolmogorov-Chaitin , complexidade programa de tamanho , complexidade descritiva , ou entropia algorítmico . O nome é uma homenagem a Andrey Kolmogorov , que publicou pela primeira vez sobre o assunto em 1963.

A noção de complexidade de Kolmogorov pode ser usada para declarar e provar resultados de impossibilidade semelhantes ao argumento diagonal de Cantor , ao teorema da incompletude de Gödel e ao problema de parada de Turing . Em particular, nenhum programa P computando um limite inferior para a complexidade de Kolmogorov de cada texto pode retornar um valor essencialmente maior do que o próprio comprimento de P (ver seção § Teorema da incompletude de Chaitin ); portanto, nenhum programa pode calcular a complexidade de Kolmogorov exata para um número infinito de textos.

Definição

Considere as seguintes duas strings de 32 letras minúsculas e dígitos:

abababababababababababababababab , e
4c1j5b2p0cv4w1x8rx2y39umgw5q85s7

A primeira string tem uma breve descrição em inglês, a saber " write ab 16 times", que consiste em 17 caracteres. O segundo não tem uma descrição simples óbvia (usando o mesmo conjunto de caracteres) além de escrever a própria string, ou seja, " write 4c1j5b2p0cv4w1x8rx2y39umgw5q85s7" que tem 38 caracteres. Portanto, pode-se dizer que a operação de escrever a primeira string tem "menos complexidade" do que escrever a segunda.

Mais formalmente, a complexidade de uma string é o comprimento da descrição mais curta possível da string em alguma linguagem de descrição universal fixa (a sensibilidade da complexidade em relação à escolha da linguagem de descrição é discutida abaixo). Pode-se mostrar que a complexidade de Kolmogorov de qualquer string não pode ser mais do que alguns bytes maior do que o comprimento da própria string. Strings como o exemplo abab acima, cuja complexidade de Kolmogorov é pequena em relação ao tamanho da string, não são consideradas complexas.

A complexidade de Kolmogorov pode ser definida para qualquer objeto matemático, mas para simplificar o escopo deste artigo é restrito a strings. Devemos primeiro especificar uma linguagem de descrição para strings. Essa linguagem de descrição pode ser baseada em qualquer linguagem de programação de computador, como Lisp , Pascal ou Java . Se P é um programa que produz uma string x , então P é uma descrição de x . O comprimento da descrição é apenas o comprimento de P como uma cadeia de caracteres, multiplicado pelo número de bits em um caractere (por exemplo, 7 para ASCII ).

Poderíamos, alternativamente, escolher uma codificação para máquinas de Turing , onde uma codificação é uma função que associa a cada Máquina de Turing M um bitstring < M >. Se M é uma máquina de Turing que, na entrada w , produz a string x , então a string concatenada < M > w é uma descrição de x . Para análise teórica, esta abordagem é mais adequada para a construção de provas formais detalhadas e é geralmente preferida na literatura de pesquisa. Neste artigo, uma abordagem informal é discutida.

Qualquer string s tem pelo menos uma descrição. Por exemplo, a segunda string acima é gerada pelo programa:

function GenerateString2()
    return "4c1j5b2p0cv4w1x8rx2y39umgw5q85s7"

enquanto a primeira string é produzida pelo pseudocódigo (muito mais curto):

function GenerateString1()
    return "ab" × 16

Se uma descrição d ( s ) de uma string s tem comprimento mínimo (ou seja, usando o menor número de bits), é chamada de descrição mínima de s , e o comprimento de d ( s ) (ou seja, o número de bits no mínimo descrição) é a complexidade de Kolmogorov de s , escrito K ( s ). Simbolicamente,

K ( s ) = | d ( s ) |.

O comprimento da descrição mais curta dependerá da escolha da linguagem de descrição; mas o efeito da mudança de linguagem é limitado (um resultado chamado teorema da invariância ).

Teorema de invariância

Tratamento informal

Existem algumas linguagens de descrição que são ótimas, no seguinte sentido: dada qualquer descrição de um objeto em uma linguagem de descrição, essa descrição pode ser usada na linguagem de descrição ótima com um overhead constante. A constante depende apenas das linguagens envolvidas, não da descrição do objeto, nem do objeto que está sendo descrito.

Aqui está um exemplo de uma linguagem de descrição ideal. Uma descrição terá duas partes:

  • A primeira parte descreve outra linguagem de descrição.
  • A segunda parte é uma descrição do objeto nesse idioma.

Em termos mais técnicos, a primeira parte de uma descrição é um programa de computador (especificamente: um compilador para a linguagem do objeto, escrito na linguagem de descrição), com a segunda parte sendo a entrada para aquele programa de computador que produz o objeto como saída.

O teorema da invariância segue: Dada qualquer linguagem de descrição L , a linguagem de descrição ótima é pelo menos tão eficiente quanto L , com alguma sobrecarga constante.

Prova: Qualquer descrição D em L pode ser convertida em uma descrição na linguagem ótima, primeiro descrevendo L como um programa de computador P (parte 1) e, em seguida, usando a descrição original D como entrada para esse programa (parte 2). O comprimento total desta nova descrição D ′ é (aproximadamente):

| D ′ | = | P | + | D |

O comprimento de P é uma constante que não depende D . Portanto, há no máximo uma sobrecarga constante, independente do objeto descrito. Portanto, a linguagem ideal é universal até essa constante aditiva.

Um tratamento mais formal

Teorema : Se K 1 e K 2 são as funções de complexidade relativas às linguagens de descrição completa de Turing L 1 e L 2 , então há uma constante c  - que depende apenas das linguagens L 1 e L 2 escolhidas - de modo que

s . - cK 1 ( s ) - K 2 ( s ) ≤ c .

Prova : Por simetria, basta provar que existe alguma constante c tal que para todas as cordas s

K 1 ( s ) ≤ K 2 ( s ) + c .

Agora, suponha que haja um programa na linguagem L 1 que atue como um intérprete para L 2 :

function InterpretLanguage(string p)

onde p é um programa em L 2 . O intérprete é caracterizado pela seguinte propriedade:

Executar InterpretLanguagena entrada p retorna o resultado da execução de p .

Assim, se P é um programa em L 2 que é uma descrição mínima de s , então InterpretLanguage( P ) retorna a string s . O comprimento desta descrição de s é a soma de

  1. A duração do programa InterpretLanguage, que podemos considerar a constante c .
  2. O comprimento de P, que por definição é K 2 ( s ).

Isso prova o limite superior desejado.

História e contexto

A teoria da informação algorítmica é a área da ciência da computação que estuda a complexidade de Kolmogorov e outras medidas de complexidade em strings (ou outras estruturas de dados ).

O conceito e a teoria da Complexidade de Kolmogorov são baseados em um teorema crucial descoberto por Ray Solomonoff , que o publicou em 1960, descrevendo-o em "Um Relatório Preliminar sobre uma Teoria Geral de Inferência Indutiva" como parte de sua invenção da probabilidade algorítmica . Ele deu uma descrição mais completa em suas publicações de 1964, "A Formal Theory of Inductive Inference", Parte 1 e Parte 2 em Informação e Controle .

Andrey Kolmogorov posteriormente publicou independentemente este teorema em Problems Inform. Transmissão em 1965. Gregory Chaitin também apresenta este teorema em J. ACM  - o artigo de Chaitin foi submetido em outubro de 1966 e revisado em dezembro de 1968, e cita os artigos de Solomonoff e de Kolmogorov.

O teorema diz que, entre os algoritmos que decodificam strings a partir de suas descrições (códigos), existe um ótimo. Este algoritmo, para todas as strings, permite códigos tão curtos quanto os permitidos por qualquer outro algoritmo até uma constante aditiva que depende dos algoritmos, mas não das próprias strings. Solomonoff usou este algoritmo e os comprimentos de código que ele permite definir uma "probabilidade universal" de uma string na qual a inferência indutiva dos dígitos subsequentes da string pode ser baseada. Kolmogorov usou este teorema para definir várias funções de strings, incluindo complexidade, aleatoriedade e informação.

Quando Kolmogorov ficou sabendo do trabalho de Solomonoff, ele reconheceu a prioridade de Solomonoff. Por vários anos, o trabalho de Solomonoff foi mais conhecido na União Soviética do que no mundo ocidental. O consenso geral na comunidade científica, no entanto, era associar esse tipo de complexidade a Kolmogorov, que estava preocupado com a aleatoriedade de uma sequência, enquanto a Probabilidade Algorítmica passou a ser associada a Solomonoff, que se concentrou na previsão usando sua invenção da distribuição de probabilidade universal anterior . A área mais ampla que abrange a complexidade descritiva e a probabilidade é freqüentemente chamada de complexidade de Kolmogorov. O cientista da computação Ming Li considera isso um exemplo do efeito Mateus : "... a todos que tiverem, mais será dado ..."

Existem várias outras variantes da complexidade de Kolmogorov ou informações algorítmicas. O mais utilizado baseia-se em programas de autodeterminação e deve-se principalmente a Leonid Levin (1974).

Uma abordagem axiomática da complexidade de Kolmogorov baseada nos axiomas de Blum (Blum 1967) foi introduzida por Mark Burgin no artigo apresentado para publicação por Andrey Kolmogorov.

Resultados básicos

Na discussão a seguir, seja K ( s ) a complexidade da string s .

Não é difícil ver que a descrição mínima de uma string não pode ser muito maior do que a própria string - o programa GenerateString2acima que produz s é uma quantidade fixa maior do que s .

Teorema : Existe uma constante c tal que

s . K ( s ) ≤ | s | + c .

Incomputabilidade da complexidade de Kolmogorov

Uma tentativa ingênua de um programa para calcular K

À primeira vista, pode parecer trivial escrever um programa que pode calcular K ( s ) para qualquer s , como o seguinte:

function KolmogorovComplexity(string s)
    for i = 1 to infinity:
        for each string p of length exactly i
            if isValidProgram(p) and evaluate(p) == s
                return i

Este programa itera por meio de todos os programas possíveis (iterando por meio de todas as strings possíveis e considerando apenas aqueles que são programas válidos), começando com o mais curto. Cada programa é executado para encontrar o resultado produzido por esse programa, comparando-a à entrada de s . Se o resultado corresponder ao comprimento do programa, ele será retornado.

No entanto, isso não funcionará porque alguns dos programas p testados não serão encerrados, por exemplo, se contiverem loops infinitos. Não há como evitar todos esses programas testando-os de alguma forma antes de executá-los devido à não computabilidade do problema da parada .

Além disso, nenhum programa pode calcular a função K , por mais sofisticada que seja. Isso é comprovado a seguir.

Prova formal de incomputabilidade de K

Teorema : Existem strings de complexidade de Kolmogorov arbitrariamente grande. Formalmente: para cada n ∈ ℕ, existe uma string s com K ( s ) ≥ n .

Prova: caso contrário, todas as infinitas strings finitas possíveis poderiam ser geradas pelos programas infinitamente numerosos com uma complexidade abaixo de n bits.

Teorema : K não é uma função computável . Em outras palavras, não há programa que pegue qualquer string s como entrada e produza o inteiro K ( s ) como saída.

A seguinte prova indireta usa uma linguagem simples do tipo Pascal para denotar programas; para simplificar a prova, presuma que sua descrição (ou seja, um intérprete ) tenha um comprimento de1 400 000 pedaços. Suponha por contradição que existe um programa

function KolmogorovComplexity(string s)

que toma como entrada uma cadeia s e retorna K ( s ). Todos os programas são de comprimento finito, portanto, para fins de simplicidade de prova, assuma que seja7 000 000 000 bits. Agora, considere o seguinte programa de comprimento1288 bits:

function GenerateComplexString()
    for i = 1 to infinity:
        for each string s of length exactly i
            if KolmogorovComplexity(s) ≥ 8000000000
                return s

Usando KolmogorovComplexitycomo uma sub-rotina, o programa tenta cada string, começando com a mais curta, até retornar uma string com complexidade de Kolmogorov pelo menos8 000 000 000 pedaços, isto é, uma cadeia que não pode ser produzido por qualquer programa mais curto do que8 000 000 000 pedaços. No entanto, a duração total do programa acima que produziu s é apenas7 001 401 288 bits, o que é uma contradição. (Se o código de KolmogorovComplexityfor mais curto, a contradição permanece. Se for mais longo, a constante usada em GenerateComplexStringsempre pode ser alterada de forma adequada.)

A prova acima usa uma contradição semelhante ao do paradoxo Berry : " 1 a 2 menor 3 positiva 4 inteiro 5 que 6 não pode 7 ser 8 definidas 9 em 10 menos 11 do que 12 vinte 13 Inglês 14 palavras". Também é possível mostrar a não computabilidade de K por redução da não computabilidade do problema da parada H , uma vez que K e H são equivalentes de Turing .

Há um corolário, humoristicamente chamado de " teorema de pleno emprego " na comunidade de linguagens de programação, afirmando que não existe um compilador com otimização de tamanho perfeito.

Regra da cadeia para complexidade de Kolmogorov

A regra da cadeia para a complexidade de Kolmogorov afirma que

K ( X , Y ) ≤ K ( X ) + K ( Y | X ) + O (log ( K ( X , Y ))).

Afirma que o programa mais curto que reproduz X e Y é não mais do que um termo logarítmica maior do que um programa de reprodução X e um programa para reproduzir Y dado X . Usando essa afirmação, pode-se definir um análogo de informação mútua para a complexidade de Kolmogorov .

Compressão

É simples calcular limites superiores para K ( s ) - simplesmente comprima a string s com algum método, implemente o descompressor correspondente na linguagem escolhida, concatene o descompressor à string compactada e meça o comprimento da string resultante - concretamente, o tamanho de um arquivo de extração automática no idioma fornecido.

Uma string s é compactável por um número c se tiver uma descrição cujo comprimento não exceda | s | - c bits. Isso equivale a dizer que K ( s ) ≤ | s | - c . Caso contrário, s é incompressível por c . Uma string incompressível por 1 é dita simplesmente incompressível  - pelo princípio do escaninho , que se aplica porque toda string compactada mapeia para apenas uma string não compactada, strings incompressíveis devem existir, uma vez que existem 2 n strings de bits de comprimento n , mas apenas 2 n - 1 string mais curta, ou seja, strings de comprimento menor que n , (ou seja, com comprimento 0, 1, ..., n - 1).

Pela mesma razão, a maioria das strings são complexas no sentido de que não podem ser comprimidas significativamente - seus K ( s ) não são muito menores que | s |, o comprimento de s em bits. Para tornar isso preciso, fixe um valor de n . Existem 2 n bits de comprimento n . A distribuição de probabilidade uniforme no espaço dessas bitstrings atribui peso exatamente igual 2 - n a cada string de comprimento n .

Teorema : Com a distribuição de probabilidade uniforme no espaço de bitstrings de comprimento n , a probabilidade de que uma string seja incompressível por c é pelo menos 1 - 2 - c +1 + 2 - n .

Para provar o teorema, observe que o número de descrições de comprimento não excedendo n - c é dado pela série geométrica:

1 + 2 + 2 2 +… + 2 n - c = 2 n - c +1 - 1.

Restam pelo menos

2 n - 2 n - c +1 + 1

bitstrings de comprimento n que são incompressíveis por c . Para determinar a probabilidade, divida por 2 n .

Teorema da incompletude de Chaitin

Kolmogorov complexidade K ( s ) , e duas funções de limite inferior calculáveis prog1(s), prog2(s). O eixo horizontal ( escala logarítmica ) enumera todas as strings s , ordenadas por comprimento; o eixo vertical ( escala linear ) mede a complexidade de Kolmogorov em bits . A maioria das cordas são incompressíveis, ou seja, sua complexidade de Kolmogorov excede seu comprimento em um valor constante. 9 cordas compressíveis são mostradas na imagem, aparecendo como declives quase verticais. Devido ao teorema da incompletude de Chaitin (1974), a saída de qualquer programa que calcule um limite inferior da complexidade de Kolmogorov não pode exceder algum limite fixo, que é independente da string de entrada s .

Pelo teorema acima ( § Compressão ), a maioria das strings são complexas no sentido de que não podem ser descritas de nenhuma forma significativamente "comprimida". No entanto, verifica-se que o fato de uma string específica ser complexa não pode ser formalmente comprovada, se a complexidade da string estiver acima de um determinado limite. A formalização precisa é a seguinte. Primeiro, fixe um sistema axiomático particular S para os números naturais . O sistema axiomático tem de ser suficientemente forte de modo a que, a certa afirmações Uma cerca de complexidade de cordas, pode-se associar uma fórmula F Um em S . Essa associação deve ter a seguinte propriedade:

Se F A é demonstrável a partir dos axiomas de S , então a asserção A correspondente deve ser verdadeira. Essa "formalização" pode ser alcançada com base em uma numeração de Gödel .

Teorema : Existe uma constante L (que depende apenas de S e da escolha da linguagem de descrição) tal que não existe uma string s para a qual o enunciado

K ( s ) ≥ L       (conforme formalizado em S )

pode ser comprovada dentro S .


Idéia de prova : A prova desse resultado é modelada em uma construção autorreferencial usada no paradoxo de Berry . Nós, em primeiro lugar obter um programa que enumera as provas dentro S e que especifica um procedimento P que toma como entrada um inteiro G e imprime as cordas x que estão dentro provas dentro S da instrução K ( x ) ≥ L . Definindo então L para maior do que o comprimento deste procedimento P , temos que o comprimento necessário de um programa para imprimir x como indicado em K ( x ) ≥ L como sendo pelo menos L é então menor que a quantidade L desde a string x foi impresso pelo processo P . Isso é uma contradição. Portanto, não é possível para o sistema de prova S provar K ( x ) ≥ L para L arbitrariamente grande, em particular, para L maior que o comprimento do procedimento P , (que é finito).

Prova :

Podemos encontrar uma enumeração eficaz de todas as provas formais em S por algum procedimento

function NthProof(int n)

que toma como entrada ne produz alguma prova. Esta função enumera todas as provas. Algumas dessas são provas para fórmulas com as quais não nos importamos aqui, uma vez que todas as provas possíveis na linguagem de S são produzidas para alguns n . Alguns destes são fórmulas complexidade da forma de K ( s ) ≥  n onde s e n são constantes na linguagem de S . Existe um procedimento

function NthProofProvesComplexityFormula(int n)

que determina se o n th prova realmente demonstra uma complexidade fórmula K ( s ) ≥  L . As strings s , e o inteiro L, por sua vez, são computáveis ​​pelo procedimento:

function StringNthProof(int n)
function ComplexityLowerBoundNthProof(int n)

Considere o seguinte procedimento:

function GenerateProvablyComplexString(int n)
    for i = 1 to infinity:
        if NthProofProvesComplexityFormula(i) and ComplexityLowerBoundNthProof(i) ≥ n
            return StringNthProof(i)

Dado um n , este procedimento tenta todas as provas até encontrar uma string e uma prova no sistema formal S da fórmula K ( s ) ≥  L para algum L  ≥  n ; se essa prova não existe, ele continua para sempre.

Finalmente, considere o programa que consiste em todas essas definições de procedimento e uma chamada principal:

GenerateProvablyComplexString(n0)

onde a constante n 0 será determinada posteriormente. O comprimento total do programa pode ser expresso como U + log 2 ( n 0 ), onde U é alguma constante e log 2 ( n 0 ) representa o comprimento do valor inteiro n 0 , sob a suposição razoável de que é codificado em dígitos binários . Escolheremos n 0 como sendo maior que o comprimento do programa, ou seja, tal que n 0 > U + log 2 ( n 0 ). Isto é claramente verdadeira para n 0 suficientemente grande, porque o lado esquerdo cresce linearmente em n 0 , enquanto o lado direito cresce logaritmicamente em n 0 até a constante fixa L .

Então, nenhuma prova da forma " K ( s ) ≥ L " com Ln 0 pode ser obtida em S , como pode ser visto por um argumento indireto : Se ComplexityLowerBoundNthProof(i)pudesse retornar um valor ≥ n 0 , então o loop interno GenerateProvablyComplexStringacabaria eventualmente , e esse procedimento retornaria uma string s tal que

K ( s )
n 0           pela construção de GenerateProvablyComplexString
> U + log 2 ( n 0 ) pela escolha de n 0
K ( s ) uma vez que s foi descrito pelo programa com aquele comprimento

Isso é uma contradição, QED

Como consequência, o programa acima, com o valor escolhido de n 0 , deve repetir para sempre.

Idéias semelhantes são usadas para provar as propriedades da constante de Chaitin .

Comprimento mínimo da mensagem

O princípio do comprimento mínimo da mensagem de inferência estatística e indutiva e aprendizado de máquina foi desenvolvido por CS Wallace e DM Boulton em 1968. MML é bayesiano (isto é, incorpora crenças anteriores) e teórico da informação. Tem as propriedades desejáveis ​​de invariância estatística (ou seja, as transformações de inferência com uma rempararametrização, como de coordenadas polares para coordenadas cartesianas), consistência estatística (ou seja, mesmo para problemas muito difíceis, MML irá convergir para qualquer modelo subjacente) e eficiência ( ou seja, o modelo MML convergirá para qualquer modelo subjacente verdadeiro o mais rápido possível). CS Wallace e DL Dowe (1999) mostraram uma conexão formal entre MML e a teoria da informação algorítmica (ou complexidade de Kolmogorov).

Aleatoriedade de Kolmogorov

A aleatoriedade de Kolmogorov define uma string (geralmente de bits ) como sendo aleatória se e somente se cada programa de computador que pode produzir aquela string for pelo menos tão longo quanto a própria string. Para tornar isso preciso, um computador universal (ou máquina de Turing universal ) deve ser especificado, de modo que "programa" signifique um programa para essa máquina universal. Uma string aleatória, nesse sentido, é "incompressível", pois é impossível "compactar" a string em um programa mais curto do que a própria string. Para cada computador universal, há pelo menos uma string algorítmica aleatória de cada comprimento. Se uma determinada string é aleatória, no entanto, depende do computador universal específico que é escolhido. Isso ocorre porque um computador universal pode ter uma determinada string codificada em si mesmo, e um programa em execução neste computador universal pode então simplesmente se referir a esta string codificada usando uma curta sequência de bits (ou seja, muito mais curta do que a própria string) .

Essa definição pode ser estendida para definir uma noção de aleatoriedade para sequências infinitas de um alfabeto finito. Essas sequências algorítmicas aleatórias podem ser definidas de três maneiras equivalentes. Uma maneira usa um análogo eficaz da teoria da medida ; outro usa martingales eficazes . A terceira forma define uma sequência infinita como aleatória se a complexidade de Kolmogorov sem prefixo de seus segmentos iniciais crescer rápido o suficiente - deve haver uma constante c tal que a complexidade de um segmento inicial de comprimento n seja sempre pelo menos n - c . Esta definição, ao contrário da definição de aleatoriedade para uma string finita, não é afetada por qual máquina universal é usada para definir a complexidade de Kolmogorov sem prefixo.

Relação com entropia

Para sistemas dinâmicos, a taxa de entropia e a complexidade algorítmica das trajetórias são relacionadas por um teorema de Brudno, que a igualdade vale para quase todos .

Pode-se mostrar que para a saída das fontes de informação de Markov , a complexidade de Kolmogorov está relacionada à entropia da fonte de informação. Mais precisamente, a complexidade de Kolmogorov da saída de uma fonte de informação de Markov, normalizada pelo comprimento da saída, converge quase certamente (já que o comprimento da saída vai ao infinito) para a entropia da fonte.

Versões condicionais

A complexidade de Kolmogorov condicional de duas strings é, grosso modo, definida como a complexidade de Kolmogorov de x dado y como uma entrada auxiliar para o procedimento.

Há também uma complexidade condicional de comprimento , que é a complexidade de x dado o comprimento de x como conhecido / entrada.

Veja também

Notas

Referências

Leitura adicional

links externos