b'\n_START_ARTICLE_\nComplexidade de Kolmogorov\n_START_PARAGRAPH_\nA complexidade de Kolmogorov \xc3\xa9 uma teoria da informa\xc3\xa7\xc3\xa3o e da aleatoriedade, profunda e sofisticada, que trata da quantidade de informa\xc3\xa7\xc3\xa3o de objetos individuais, medida atrav\xc3\xa9s do tamanho de sua menor descri\xc3\xa7\xc3\xa3o algor\xc3\xadtmica. Ela \xc3\xa9 uma no\xc3\xa7\xc3\xa3o moderna de aleatoriedade, e refere-se a um conceito pontual de aleatoriedade, ao inv\xc3\xa9s de uma aleatoriedade m\xc3\xa9dia como o faz a teoria das probabilidades. Ela \xc3\xa9 um ramo derivado da teoria da informa\xc3\xa7\xc3\xa3o de Claude Shannon, embora hoje possa ser considerada uma \xc3\xa1rea de pesquisa madura e aut\xc3\xb4noma._NEWLINE_Complexidade de Kolmogorov define uma nova teoria da informa\xc3\xa7\xc3\xa3o, chamada teoria algor\xc3\xadtmica da informa\xc3\xa7\xc3\xa3o (por tratar com algoritmos). A M\xc3\xa1quina de Turing \xc3\xa9 usada como mecanismo para descrever os objetos (para definir os algoritmos).\n_START_SECTION_\nOrigem\n_START_PARAGRAPH_\nA 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\xc3\xa7\xc3\xa3o baseada no tamanho dos programas para a M\xc3\xa1quina de Turing. Convencionou-se chamar a \xc3\xa1rea genericamente de "complexidade de Kolmogorov" em homenagem ao famoso matem\xc3\xa1tico russo, e fundador da \xc3\xa1rea, Andrei Nikolaevich Kolmogorov (1903-1987).\n_START_SECTION_\nDefini\xc3\xa7\xc3\xa3o\n_START_PARAGRAPH_\nA complexidade de Kolmogorov est\xc3\xa1 definida sobre o conjunto de strings bin\xc3\xa1rias (seq\xc3\xbc\xc3\xaancias de zeros e uns). Ela associa a cada string bin\xc3\xa1ria um valor num\xc3\xa9rico que \xc3\xa9 sua "complexidade"._NEWLINE_A complexidade de Kolmogorov pode ser definida simplificadamente como o tamanho do menor programa (ou descri\xc3\xa7\xc3\xa3o algoritmica) que computa na M\xc3\xa1quina de Turing uma determinada string bin\xc3\xa1ria._NEWLINE_Exige-se que o conjunto de descri\xc3\xa7\xc3\xb5es (programas) forme um conjunto livre de prefixo, e se chama esta complexidade de "complexidade de prefixo", representada por . Para enfatizar a M\xc3\xa1quina que est\xc3\xa1 sendo usada para definir a complexidade podemos escrever  ao inv\xc3\xa9s de , onde  \xc3\xa9 uma M\xc3\xa1quina de Turing em particular._NEWLINE_Tamb\xc3\xa9m podemos definir uma complexidade condicional, , definida como o tamanho do programa que computa  a partir de , que \xc3\xa9 dado como entrada do programa. Intuitivamente,  representa a quantidade de informa\xc3\xa7\xc3\xa3o que devemos adicionar \xc3\xa0 informa\xc3\xa7\xc3\xa3o em  para computar ._NEWLINE_Importante que o conceito de descri\xc3\xa7\xc3\xa3o seja bem fundamentado (ou seja, formalmente definido como um programa para a m\xc3\xa1quina de Turing) para evitar paradoxos. Paradoxos (ou antin\xc3\xb4mias) s\xc3\xa3o bastante freq\xc3\xbcentes na hist\xc3\xb3ria da matem\xc3\xa1tica. Podemos citar o famoso "paradoxo do barbeiro", de autoria de Bertrand Russel, que diz que "o barbeiro \xc3\xa9 aquele que barbeia os homens que n\xc3\xa3o barbeiam a si pr\xc3\xb3prios". O paradoxo \xc3\xa9 obtido ao perguntar se o barbeiro barbeia a si pr\xc3\xb3prio.\n_START_SECTION_\nM\xc3\xa1quina de Turing\n_START_PARAGRAPH_\nA M\xc3\xa1quina de Turing \xc3\xa9 um dispositivo que foi proposto em 1936 por Alan Turing com o objetivo de formalizar matematicamente o que entendemos por "computador". Ela \xc3\xa9 basicamente formada por uma fita na qual um cabe\xc3\xa7ote pode escrever s\xc3\xadmbolos de um conjunto pr\xc3\xa9-definido, e assim c\xc3\xa1lculos de diversos tipos podem ser feitos apenas com os movimentos deste cabe\xc3\xa7ote sobre a fita._NEWLINE_Uma propriedade importante da M\xc3\xa1quina de Turing \xc3\xa9 a universalidade, ou seja, a capacidade da M\xc3\xa1quina de Turing de simular qualquer outra m\xc3\xa1quina. Por isto, podemos chama-la de m\xc3\xa1quina universal.\n_START_SECTION_\nTeorema da Invari\xc3\xa2ncia\n_START_PARAGRAPH_\nDa forma como foi definido, pode parecer que a complexidade de Kolmogorov permanece dependente da m\xc3\xa1quina escolhida como m\xc3\xa1quina de refer\xc3\xaancia. No entanto, existe um teorema (chamado Teorema da Invari\xc3\xa2ncia) que prova que todas as m\xc3\xa1quinas universais (ou seja, que tem a capacidade de simular todas as outras m\xc3\xa1quinas de Turing conceb\xc3\xadveis) resultam no mesmo valor de complexidade, a n\xc3\xa3o ser por uma constante que \xc3\xa9 assintoticamente desprez\xc3\xa1vel:_NEWLINE_, para alguma constante , e_NEWLINE_ e  s\xc3\xa3o duas m\xc3\xa1quinas universais quaisquer._NEWLINE_Isto significa que a complexidade passa a ser um atributo intr\xc3\xadnseco do objeto, independente da m\xc3\xa1quina universal escolhida como m\xc3\xa1quina de refer\xc3\xaancia.\n_START_SECTION_\nPrinc\xc3\xadpio de Occam\n_START_PARAGRAPH_\nAo medir a complexidade de uma string pelo tamanho do menor programa, a complexidade de Kolmogorov reedita um antigo princ\xc3\xadpio, de autoria de William de Ockham (1285?-1349?), que ficou conhecido como Navalha de Occam, que diz que "entidades n\xc3\xa3o devem ser multiplicadas desnecessariamente"._NEWLINE_O Princ\xc3\xadpio de Occam significa que entre todas as teorias que representam um fen\xc3\xb4meno, a mais simples (ou menor) \xc3\xa9 a melhor para este fim. Isto tem evidentes conota\xc3\xa7\xc3\xb5es filos\xc3\xb3ficas relacionadas com a expressividade dos m\xc3\xa9todos de descri\xc3\xa7\xc3\xa3o e com os sistemas formais.\n_START_SECTION_\nAlgumas propriedades\n_START_PARAGRAPH_\nTrivialmente, , para algum , onde  denota o tamanho da string , j\xc3\xa1 que qualquer string pode ser computada por um programa que a tem armazenada literalmente no programa._NEWLINE_Tamb\xc3\xa9m sabemos que , j\xc3\xa1 que, na complexidade condicional, a presen\xc3\xa7a de  \xc3\xa9 uma informa\xc3\xa7\xc3\xa3o a mais que \xc3\xa9 fornecida ao programa que computar\xc3\xa1 ._NEWLINE_Se  denota uma string bin\xc3\xa1ria que \xc3\xa9 resultado de um -processo de Bernoulli, ent\xc3\xa3o  em probabilidade, onde  \xc3\xa9 a entropia do processo. Isto significa que  \xc3\xa9 assintoticamente convergente \xc3\xa0 entropia da teoria da informa\xc3\xa7\xc3\xa3o cl\xc3\xa1ssica.\n_START_SECTION_\nIncompressividade de strings bin\xc3\xa1rias\n_START_PARAGRAPH_\nSe para uma string bin\xc3\xa1ria , , para algum , ent\xc3\xa3o dizemos que  \xc3\xa9 incompress\xc3\xadvel._NEWLINE_Kolmogorov associou o conceito de incompressividade com o conceito de aleatoriedade,  com o objetivo de definir seq\xc3\xbc\xc3\xaancias aleat\xc3\xb3rias, e assim fornecer uma base te\xc3\xb3rica para probabilidades e estat\xc3\xadstica.\n_START_SECTION_\nObjetivo da complexidade de Kolmogorov\n_START_PARAGRAPH_\nO objetivo original do trabalho de Kolmogorov era obter uma defini\xc3\xa7\xc3\xa3o formal de seq\xc3\xbc\xc3\xaancia aleat\xc3\xb3ria. Kolmogorov observou que algumas seq\xc3\xbc\xc3\xaancias bin\xc3\xa1rias podiam ser comprimidas algoritmicamente. Nos dias de hoje, a maioria das pessoas est\xc3\xa1 acostumada a usar programas de compress\xc3\xa3o de dados, tais como winzip, gzip, arj, etc. Assim, a ideia que dados possam ser comprimidos n\xc3\xa3o \xc3\xa9 de todo estranha._NEWLINE_Fica f\xc3\xa1cil perceber que um n\xc3\xbamero como 1.000.000.000 na base 10 pode ser facilmente expresso como , enquanto que o n\xc3\xbamero 5.321.478.927, escolhido arbitrariamente, n\xc3\xa3o poderia ser expresso desta forma compacta._NEWLINE_Se tomarmos as strings bin\xc3\xa1rias 11111111111111111111 e 10110011010111011010, aceitar\xc3\xadamos facilmente a segunda como sendo resultante do lan\xc3\xa7amento sucessivo de uma moeda honesta (1=cara e 0=coroa). No entanto, dificilmente a primeira seq\xc3\xbc\xc3\xaancia poderia ser resultado de um experimento realmente aleat\xc3\xb3rio. Notamos que a primeira string poderia ser computada pelo programa:_NEWLINE_FOR I=1 TO 20 PRINT 1_NEWLINE_Que \xc3\xa9 um programa pequeno em rela\xc3\xa7\xc3\xa3o ao tamanho da string. J\xc3\xa1 a segunda string n\xc3\xa3o pode ser computada por um programa t\xc3\xa3o curto, pois ele dever\xc3\xa1 conter a pr\xc3\xb3pria string literalmente armazenada dentro do programa:_NEWLINE_PRINT 10110011010111011010_NEWLINE_Kolmogorov postulou que seq\xc3\xbc\xc3\xaancias que n\xc3\xa3o podem ser comprimidas algoritmicamente em uma descri\xc3\xa7\xc3\xa3o de tamanho muito menor que a seq\xc3\xbc\xc3\xaancia original s\xc3\xa3o seq\xc3\xbc\xc3\xaancias aleat\xc3\xb3rias (no sentido estoc\xc3\xa1stico do termo). Esta defini\xc3\xa7\xc3\xa3o s\xc3\xb3 funciona se forem admitidas apenas descri\xc3\xa7\xc3\xb5es dentro de uma classe de descri\xc3\xa7\xc3\xb5es livres de prefixo (ou seja que nenhuma descri\xc3\xa7\xc3\xa3o seja prefixo de outra da classe).\n_START_SECTION_\nDesigualdade de Kraft\n_START_PARAGRAPH_\nA raz\xc3\xa3o para exigir que o conjunto de descri\xc3\xa7\xc3\xb5es (programas) forme um conjunto livre de prefixo deve-se a desigualdade de Kraft, express\xc3\xa3o bem conhecida na teoria da informa\xc3\xa7\xc3\xa3o cl\xc3\xa1ssica. Ela significa que a s\xc3\xa9rie  converge. Esta \xc3\xa9 uma propriedade importante da complexidade de Kolmogorov.\n_START_SECTION_\nSeq\xc3\xbc\xc3\xaancias Aleat\xc3\xb3rias de Martin-L\xc3\xb6f\n_START_PARAGRAPH_\nUma resposta consistente ao problema de definir o conceito de seq\xc3\xbc\xc3\xaancia aleat\xc3\xb3ria foi dada por Per Martin-L\xc3\xb6f. A defini\xc3\xa7\xc3\xa3o de Martin-L\xc3\xb6f baseia-se em teoria da medida, e na exist\xc3\xaancia de um conjunto efetivo nulo maximal, no conjunto das strings bin\xc3\xa1rias. Isto significa a exist\xc3\xaancia de um conjunto nulo (com baixa probabilidade de ocorr\xc3\xaancia) que cont\xc3\xa9m todos os conjuntos nulos cujas strings podem ser algoritmicamente geradas. Esta defini\xc3\xa7\xc3\xa3o equivale a afirmar a exist\xc3\xaancia de um teste de aleatoriedade universal. Interessante observar que a defini\xc3\xa7\xc3\xa3o de Martin-L\xc3\xb6f \xc3\xa9 equivalente \xc3\xa0 defini\xc3\xa7\xc3\xa3o de seq\xc3\xbc\xc3\xaancia aleat\xc3\xb3ria dada pela complexidade de Kolmogorov (via incompressividade das strings).\n_START_SECTION_\nAplica\xc3\xa7\xc3\xb5es\n_START_PARAGRAPH_\nSolomonoff prop\xc3\xb4s o uso da regra de Bayes para obter previs\xc3\xa3o indutiva, ou seja, para prever a seq\xc3\xbc\xc3\xaancia de uma string bin\xc3\xa1ria. Para isto ele usou como probabilidade pr\xc3\xa9via a probabilidade universal, que pode ser definida como , porque ela domina toda probabilidade pr\xc3\xa9via semi-comput\xc3\xa1vel conceb\xc3\xadvel. Isto constitui-se no n\xc3\xbacleo dos m\xc3\xa9todos de intelig\xc3\xaancia artificial MDL (minimum description length) e MML (minimum message length)._NEWLINE_A complexidade  induz um conceito de dist\xc3\xa2ncia (ou similaridade), chamada dist\xc3\xa2ncia de informa\xc3\xa7\xc3\xa3o, que \xc3\xa9 uma medida a priori e absoluta sobre o conjunto das strings bin\xc3\xa1rias. Esta dist\xc3\xa2ncia pode ser aplicada em diversos e diferentes contextos de forma muito similar a outras medidas de dist\xc3\xa2ncia definidas na matem\xc3\xa1tica. O interessante \xc3\xa9 que podemos aproximar esta medida usando um programa compressor de dados e efetuar medi\xc3\xa7\xc3\xb5es emp\xc3\xadricas. Destacam-se como aplica\xc3\xa7\xc3\xb5es desta dist\xc3\xa2ncia o reconhecimento de genoma, a classifica\xc3\xa7\xc3\xa3o autom\xc3\xa1tica de m\xc3\xbasica, e o estabelecimento de uma hierarquia de linguagens humanas._NEWLINE_Chaitin construiu um paradoxo envolvendo o tamanho dos programas que constitui-se em uma prova alternativa ao que ficou conhecido como prova de G\xc3\xb6del (ou Teorema da incompletude de G\xc3\xb6del). Chaitin baseou-se no paradoxo de Berry que sup\xc3\xb5e considerar o menor n\xc3\xbamero inteiro positivo que n\xc3\xa3o pode ser definido por uma frase em portugu\xc3\xaas com menos que 1.000.000.000 de caracteres. No entanto, a pr\xc3\xb3pria defini\xc3\xa7\xc3\xa3o do problema define o n\xc3\xbamero e tem menos de 1.000.000.000 de caracteres, o que \xc3\xa9 uma contradi\xc3\xa7\xc3\xa3o. Isto resulta que strings n\xc3\xa3o podem ser produzidas por programas que tenham menos complexidade que a pr\xc3\xb3pria string, sendo isto um limite dos sistemas formais._NEWLINE_Uma outra interessante aplica\xc3\xa7\xc3\xa3o de complexidade de Kolmogorov \xc3\xa9 o n\xc3\xbamero m\xc3\xa1gico e m\xc3\xadstico , proposto por Chaitin, definido como:  Nesta f\xc3\xb3rmula,  representa um programa que p\xc3\xa1ra (finaliza) e  \xc3\xa9 o tamanho deste programa. \xc3\x89 interessante observar que , representando  a probabilidade de um programa qualquer parar (finalizar).  \xc3\xa9 um n\xc3\xbamero real aleat\xc3\xb3rio (cujos d\xc3\xadgitos formam uma seq\xc3\xbc\xc3\xaancia aleat\xc3\xb3ria) e n\xc3\xa3o comput\xc3\xa1vel (ou seja, n\xc3\xa3o pode ser computado por um programa na m\xc3\xa1quina de Turing). Al\xc3\xa9m disto,  cont\xc3\xa9m em si, da forma mais compacta poss\xc3\xadvel, todas as verdades matem\xc3\xa1ticas poss\xc3\xadveis de serem expressas._NEWLINE_Diversas outras aplica\xc3\xa7\xc3\xb5es da teoria foram desenvolvidas desde ent\xc3\xa3o: intelig\xc3\xaancia artificial, linguagens formais, complexidade computacional, teoria dos grafos, biotecnologia, etc.'