Complexidade de Kolmogorov

Esta imagem ilustra parte do conjunto Mandelbrot fractal. Simplesmente armazenar a 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 Mandelbrot e as coordenadas de canto da imagem. Assim, a complexidade de Kolmogorov desta imagem é muito menos de 23 MB em qualquer modelo pragmático de computação. A compressão de imagem de uso geral da PNG reduz apenas para 1,6 MB, menor que os dados brutos, mas muito maior 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 predeterminada linguagem de programação) que produz o objeto como saída. É uma medida dos recursos computacionais necessários para especificar o objeto e também é conhecida como complexidade algorítmica, complexidade de Solomonoff–Kolmogorov–Chaitin, complexidade do tamanho do programa , complexidade descritiva ou entropia algorítmica. É nomeado após Andrey Kolmogorov, que publicou pela primeira vez sobre o assunto em 1963 e é uma generalização da teoria clássica da informação.

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

Definição

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

abababababababababababababababab e

4c1j5b2p0cv4w1x8rx2y39umgw5q85s7

A primeira string tem uma descrição curta em inglês, ou seja, "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, "escreva 4c1j5b2p0cv4w1x8rx2y39umgw5q85s7" que tem 38 caracteres. Portanto, pode-se dizer que a operação de escrever a primeira string tem "menos complexidade" do que escrever o segundo.

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 maior do que alguns bytes maior 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 gera 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 uma bitstring <M >. Se M é uma Máquina de Turing que, na entrada w, gera 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 pseudocódigo:

função GenerateString2()
 retorno "4c1j5b2p0cv4w1x8rx2y39umgw5q85s7"

enquanto a primeira string é gerada pelo pseudo-código (muito mais curto):

função GenerateString1()
 retorno "ab" × 16

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

KK(S) = |D(S)|.

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

Teorema da 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, tal 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 nessa linguagem.

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), sendo a segunda parte a entrada para esse 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 constante a sobrecarga.

Prova: Qualquer descrição D em L pode ser convertida em uma descrição na linguagem ideal descrevendo primeiro 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 de D. Assim, existe no máximo um overhead constante, independentemente do objeto descrito. Portanto, a linguagem ótima é universal até esta constante aditiva.

Um tratamento mais formal

Teorema: Se K₁ e K₂ são as funções de complexidade em relação às linguagens de descrição completa de Turing L₁ e L₂, então há uma constante c – que depende apenas dos idiomas L₁ e L₂ escolhido – tal que

Gerenciamento de contasS.c ≤ KK₁(S) KK₂(S≤ c.

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

KK₁(S≤ KK₂(S) + c.

Agora, suponha que exista um programa na linguagem L₁ que atua como um interpretador para L₂:

função InterpretoLanguagem(string p)

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

Correr InterpretLanguage na entrada p retorna o resultado da execução p.

Assim, se P é um programa em L₂ 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. O comprimento do programa InterpretLanguage, que podemos tomar para ser a constante c.
2. O comprimento de P que por definição é KK₂(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 pela primeira vez 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, "Uma teoria formal da inferência indutiva" Parte 1 e Parte 2 em Informação e Controle.

Andrey Kolmogorov mais tarde 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 Kolmogorov.

O teorema diz que, entre os algoritmos que decodificam strings a partir de suas descrições (códigos), existe um ideal. 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 esse algoritmo e os comprimentos de código que ele permite para definir uma "probabilidade universal" de uma string na qual a inferência indutiva dos dígitos subsequentes da string pode ser baseada. Kolmogorov usou esse teorema para definir várias funções de strings, incluindo complexidade, aleatoriedade e informação.

Quando Kolmogorov tomou conhecimento 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, foi associar esse tipo de complexidade a Kolmogorov, que se preocupava com a aleatoriedade de uma sequência, enquanto a probabilidade algorítmica tornou-se associada a Solomonoff, que se concentrou na previsão usando sua invenção da distribuição de probabilidade a priori universal.. A área mais ampla que abrange a complexidade descritiva e a probabilidade costuma ser chamada de complexidade de Kolmogorov. O cientista da computação Ming Li considera isso um exemplo do efeito Mateus: "...a todos que têm, mais será dado..."

Existem várias outras variantes da complexidade de Kolmogorov ou informações algorítmicas. A mais utilizada é baseada em programas autodelimitados, 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 GenerateString2 acima que gera s é um fixo quantidade maior que s.

Teorema: Existe uma constante c tal que

Gerenciamento de contasS. KK(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 possa calcular K(s) para qualquer s, como o seguinte:

função Complexidade de Kolmogorov(string s)
 para I = 1 para infinito:
 para cada string p de comprimento exatamente i
 se isValidProgram(p) e avaliação(p) == S
 retorno Eu...

Este programa itera por todos os programas possíveis (interagindo por 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-o com a entrada s. Se o resultado corresponder, o comprimento do programa será retornado.

No entanto, isso não funcionará porque alguns dos programas p testados não serão encerrados, por exemplo, se eles 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 sofisticado 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úmero natural n, existe uma string s com K(s) ≥ n.

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

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

A seguinte prova por contradição usa uma linguagem simples semelhante a Pascal para denotar programas; para simplificar a prova, suponha que sua descrição (ou seja, um intérprete) tenha um comprimento de 1400000 bits. Assuma por contradição que existe um programa

função Complexidade de Kolmogorov(string s)

que recebe como entrada uma string s e retorna K(s). Todos os programas têm comprimento finito, portanto, para simplificar a prova, suponha que seja 7000000000 bits. Agora, considere o seguinte programa de tamanho 1288 bits:

função Gerar ComplexString()
 para I = 1 para infinito:
 para cada string s de comprimento exatamente i
 se KolmogorovComplexidade (s) ≥ 8000000000
 retorno S

Usando KolmogorovComplexity como uma sub-rotina, o programa tenta cada string, começando com a mais curta, até retornar uma string com complexidade Kolmogorov de pelo menos 8000000000 bits, ou seja, uma string que não pode ser produzida por nenhum programa menor que 8000000000 bits. No entanto, o comprimento total do programa acima que produziu s é de apenas 7001401288 bits, o que é uma contradição. (Se o código de KolmogorovComplexity for mais curto, a contradição permanece. Se for mais longo, a constante usada em GenerateComplexString sempre pode ser alterada apropriadamente.)

A prova acima usa uma contradição semelhante à do paradoxo de Berry: "₁O ₂menor ₃positivo ₄inteiro ₅que ₆não pode ₇ser ₈definido ₉em ₁₀menos ₁₁do que ₁₂ vinte ₁₃inglês ₁₄palavras". Também é possível mostrar a não-computabilidade de K por redução da não-computabilidade do problema de parada H, pois K e H são Turing-equivalentes.

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

Regra da cadeia para a complexidade de Kolmogorov

A regra da cadeia para a complexidade de Kolmogorov afirma que

KK(X,Y≤ KK(X) + KK(Y|X) + O(em inglês)KK(X,Y)).

Afirma que o programa mais curto que reproduz X e Y não é mais do que um termo logarítmico maior que um programa para reproduzir X e um programa para reproduzir Y dado X. Usando esta declaraçã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 descompactador correspondente no idioma escolhido, concatenar o descompactador à string compactada e medir o comprimento da string resultante - concretamente, o tamanho de um arquivo de extração automática no idioma especificado.

Uma string s é compressí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. Diz-se que uma string incompressível por 1 é simplesmente incompressível - pelo princípio da casa dos pombos, que se aplica porque cada string compactada é mapeada para apenas uma string não compactada, strings incompressíveis devem existir, pois existem 2ⁿ sequências de bits de comprimento n, mas apenas 2ⁿ − 1 sequências mais curtas, ou seja, strings de comprimento menor que n, (ou seja, com comprimento 0, 1,..., n − 1).

Pelo mesmo motivo, a maioria das strings são complexas no sentido de que não podem ser significativamente comprimidas – seu K(s) não é muito menor que | s|, o comprimento de s em bits. Para tornar isso preciso, fixe um valor de n. Existem 2 ⁿ bitstrings de comprimento n. A distribuição de probabilidade uniforme no espaço dessas cadeias de bits atribui peso exatamente igual 2⁻ⁿ a cada cadeia de comprimento n.

Teorema: Com a distribuição de probabilidade uniforme no espaço de cadeias de bits de comprimento n, a probabilidade de uma cadeia ser incompressível por c é pelo menos 1 − 2^−c+1 + 2⁻ⁿ.

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

1 + 2 + 2² + 2^{n - Sim. c} = 2^{n- Sim.c+ 1} - 1.

Restam pelo menos

2ⁿ - 2^{n- Sim.c+ 1} + 1

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

Teorema da incompletude de Chaitin

Complexidade de Kolmogorov KK(S), e duas funções de ligação inferior computáveis prog1(s), prog2(s). O eixo horizontal (escala logarítmica) enumera todas as cadeias S, ordenado 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 por uma quantidade constante. 9 cordas compressíveis são mostradas na imagem, aparecendo como encostas quase verticais. Devido ao teorema da incompletude de Chaitin (1974), a saída de qualquer programa computando um limite inferior da complexidade de Kolmogorov não pode exceder algum limite fixo, que é independente da cadeia 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 forma significativamente "comprimidas" caminho. No entanto, verifica-se que o fato de uma string específica ser complexa não pode ser provado formalmente, se a complexidade da string estiver acima de um certo 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 que ser poderoso o suficiente para que, a certas afirmações A sobre complexidade de strings, se possa associar uma fórmula F_A em S. Esta associação deve ter a seguinte propriedade:

Se F_A é demonstrável a partir dos axiomas de S, então a afirmação correspondente A deve ser verdadeiro. Essa "formalização" pode ser obtido 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 existe uma string s para a qual a instrução

KK(S≥ L (como formalizado em S)

pode ser comprovado dentro de S.

Idéia de prova: A prova desse resultado é modelada em uma construção auto-referencial usada no paradoxo de Berry. Primeiro obtemos um programa que enumera as provas dentro de S e especificamos um procedimento P que toma como entrada um inteiro L e imprime as strings x que estão dentro de provas dentro de S da declaração K(x) ≥ L. Ao definir L para maior que o comprimento deste procedimento P, temos o comprimento necessário de um programa para imprimir x conforme indicado em K(x) ≥ L como sendo pelo menos L é então menor que o valor L desde que a string x foi impressa pelo procedimento 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 efetiva de todas as provas formais em S por algum procedimento

função NthProof(- Não. n)

que toma como entrada n e mostra alguma prova. Esta função enumera todas as provas. Algumas delas são provas para fórmulas com as quais não nos importamos aqui, já que todas as provas possíveis na linguagem de S são produzidas para algum n. Algumas delas são fórmulas de complexidade na forma K(s) ≥ n onde s e n são constantes na linguagem de S. Existe um procedimento

função NthProofProvesComplexidadeFormula(- Não. n)

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

função StringNthProof(- Não. n)

função ComplexidadeLowerBoundNthProof(- Não. n)

Considere o seguinte procedimento:

função GerarProvavelmente ComplexString(- Não. n)
 para i = 1 para o infinito:
 se NthProofProvesComplexityFormula(i) e ComplexidadeLowerBoundNthProof(i) ≥ n retorno StringNthProof(Eu...)

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 tal prova não existe, ele faz um loop para sempre.

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

GerarProvavelmente ComplexString(n0)

onde a constante n₀ será determinada posteriormente. A duração total do programa pode ser expressa como U+log₂(n₀), onde U é uma constante e log₂(n₀) representa o comprimento do valor inteiro n ₀, sob a suposição razoável de que é codificado em dígitos binários. Escolheremos n₀ para ser maior que o comprimento do programa, ou seja, tal que n₀ > U+log₂(n₀). Isso é claramente verdadeiro para n₀ suficientemente grande, porque o lado esquerdo cresce linearmente em n₀ enquanto o lado direito cresce logaritmicamente em n₀ até a constante fixa U.

Então nenhuma prova da forma "K(s)≥L" com L≥n₀ pode ser obtido em S, como pode ser visto por um argumento indireto: Se ComplexityLowerBoundNthProof(i) pudesse retornar um valor ≥n₀, então o loop dentro de GenerateProvablyComplexString acabaria terminando, e esse procedimento retornaria uma string s tal que

Isso é uma contradição, Q.E.D.

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

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

Tamanho mínimo da mensagem

O princípio de comprimento mínimo de mensagem de inferência estatística e indutiva e aprendizado de máquina foi desenvolvido por C.S. Wallace e D.M. Boulton em 1968. MML é bayesiano (ou seja, incorpora crenças anteriores) e teórico da informação. Tem as propriedades desejáveis de invariância estatística (ou seja, a inferência transforma com uma reparametrização, como de coordenadas polares para coordenadas cartesianas), consistência estatística (ou seja, mesmo para problemas muito difíceis, o MML 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). C.S. Wallace e D.L. Dowe (1999) mostrou uma conexão formal entre o MML e a teoria da informação algorítmica (ou complexidade de Kolmogorov).

Aleatoriedade de Kolmogorov

Aleatoriedade de Kolmogorov define uma string (geralmente de bits) como aleatória se e somente se todo programa de computador que pode produzir essa 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 o "programa" significa um programa para esta máquina universal. Uma string aleatória neste sentido é "incompressível" na medida em que é impossível "comprimir" a string em um programa menor que a própria string. Para cada computador universal, existe pelo menos uma string algoritmicamente aleatória de cada comprimento. No entanto, se uma sequência específica é aleatória, depende do computador universal específico escolhido. Isso ocorre porque um computador universal pode ter uma string específica codificada em si mesma, e um programa executado nesse computador universal pode simplesmente se referir a essa string codificada usando uma sequência curta de bits (ou seja, muito mais curta que a própria string)..

Esta 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 maneira 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 é 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 a entropia

Para sistemas dinâmicos, taxa de entropia e complexidade algorítmica das trajetórias estão relacionadas por um teorema de Brudno, que a igualdade KK(x;T)= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =h(T){displaystyle K(x;T)=h(T)} para quase todos xNão..

Pode ser mostrado 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 (como o comprimento da saída vai para o infinito) para a entropia da fonte.

Versões condicionais

A complexidade condicional Kolmogorov de duas cordas KK(x|Sim.)(x|y)} é, aproximadamente, definido como a complexidade de Kolmogorov x dados Sim. como uma entrada auxiliar para o procedimento.

Há também uma complexidade de comprimento condicionado KK(x|L(x))(x|L(x)}, que é a complexidade x dado o comprimento de x como conhecido / entrada.