Teoria da informação algorítmica - Algorithmic information theory

A teoria da informação algorítmica (AIT) é um ramo da ciência da computação teórica que se preocupa com a relação entre computação e informação de objetos gerados computavelmente (em oposição a gerados estocasticamente ), como strings ou qualquer outra estrutura de dados . Em outras palavras, é mostrado na teoria algorítmica da informação que a incompressibilidade computacional "imita" (exceto para uma constante que depende apenas da linguagem de programação universal escolhida) as relações ou desigualdades encontradas na teoria da informação . De acordo com Gregory Chaitin , é "o resultado de colocar a teoria da informação de Shannon e a teoria da computabilidade de Turing em uma coqueteleira e agitando vigorosamente".

Além da formalização de uma medida universal para o conteúdo de informação irredutível de objetos gerados por computador, algumas conquistas principais do AIT foram mostrar que: na verdade, a complexidade algorítmica segue (no caso autodeterminado ) as mesmas desigualdades (exceto para uma constante) que a entropia faz, como na teoria da informação clássica; aleatoriedade é incompressibilidade; e, dentro do domínio do software gerado aleatoriamente, a probabilidade de ocorrência de qualquer estrutura de dados é da ordem do programa mais curto que a gera quando executado em uma máquina universal.

O AIT estuda principalmente medidas de conteúdo de informação irredutível de strings (ou outras estruturas de dados ). Como a maioria dos objetos matemáticos pode ser descrita em termos de strings, ou como o limite de uma sequência de strings, ele pode ser usado para estudar uma ampla variedade de objetos matemáticos, incluindo inteiros . Uma das principais motivações por trás do AIT é o próprio estudo da informação transportada por objetos matemáticos como no campo da metamatemática , por exemplo, como mostrado pelos resultados de incompletude mencionados abaixo. Outras motivações principais vieram de: superar as limitações da teoria da informação clássica para objetos únicos e fixos; formalizar o conceito de aleatoriedade ; e encontrar uma inferência probabilística significativa sem conhecimento prévio da distribuição de probabilidade (por exemplo, se é independente e distribuída de forma idêntica , Markoviana ou mesmo estacionária ). Desta forma, AIT é conhecido por ser basicamente fundada sobre três principais conceitos matemáticos e as relações entre eles: complexidade algorítmica , aleatoriedade algorítmica e de probabilidade algorítmica .

Visão geral

A teoria da informação algorítmica estuda principalmente as medidas de complexidade em strings (ou outras estruturas de dados ). Como a maioria dos objetos matemáticos pode ser descrita em termos de strings ou como o limite de uma sequência de strings, ele pode ser usado para estudar uma ampla variedade de objetos matemáticos, incluindo inteiros .

Informalmente, do ponto de vista da teoria algorítmica da informação, o conteúdo de informação de uma string é equivalente ao comprimento da representação autocontida mais compactada possível dessa string. Uma representação autocontida é essencialmente um programa - em alguma linguagem de programação universal fixa, mas irrelevante - que, quando executado, produz a string original.

Deste ponto de vista, uma enciclopédia de 3.000 páginas, na verdade, contém menos informações do que 3.000 páginas de letras completamente aleatórias, apesar do fato de que a enciclopédia é muito mais útil. Isso ocorre porque, para reconstruir toda a seqüência de letras aleatórias, é preciso saber o que é cada letra. Por outro lado, se todas as vogais fossem removidas da enciclopédia, alguém com razoável conhecimento da língua inglesa poderia reconstruí-la, assim como alguém provavelmente poderia reconstruir a frase "Ths sntnc hs lw nfrmtn cntnt" do contexto e consoantes presentes.

Ao contrário da teoria da informação clássica, a teoria da informação algorítmica fornece definições formais e rigorosas de uma string aleatória e uma sequência infinita aleatória que não depende de intuições físicas ou filosóficas sobre não determinismo ou probabilidade . (O conjunto de strings aleatórias depende da escolha da máquina de Turing universal usada para definir a complexidade de Kolmogorov , mas qualquer escolha dá resultados assintóticos idênticos porque a complexidade de Kolmogorov de uma string é invariante até uma constante aditiva dependendo apenas da escolha de Turing universal máquina. Por esta razão, o conjunto de sequências infinitas aleatórias é independente da escolha da máquina universal.)

Alguns dos resultados da teoria da informação algorítmica, como o teorema da incompletude de Chaitin , parecem desafiar as intuições matemáticas e filosóficas comuns. O mais notável entre eles é a construção da constante de Chaitin Ω , um número real que expressa a probabilidade de que uma máquina de Turing universal autodeterminada pare quando sua entrada for fornecida por jogadas de uma moeda justa (às vezes considerada como a probabilidade de que uma moeda aleatória o programa de computador eventualmente será interrompido). Embora Ω seja facilmente definido, em qualquer teoria axiomatizável consistente só se pode computar muitos dígitos finitos de Ω , então é em certo sentido incognoscível , fornecendo um limite absoluto no conhecimento que é uma reminiscência dos teoremas da incompletude de Gödel . Embora os dígitos de Ω não possam ser determinados, muitas propriedades de Ω são conhecidas; por exemplo, é uma sequência algorítmica aleatória e, portanto, seus dígitos binários são uniformemente distribuídos (na verdade, é normal ).

História

A teoria da informação algorítmica foi fundada por Ray Solomonoff , que publicou as idéias básicas nas quais o campo se baseia como parte de sua invenção da probabilidade algorítmica - uma maneira de superar problemas sérios associados à aplicação das regras de Bayes em estatística. Ele descreveu seus resultados pela primeira vez em uma conferência na Caltech em 1960 e em um relatório, em fevereiro de 1960, "Um relatório preliminar sobre uma teoria geral da inferência indutiva". A teoria da informação algorítmica foi posteriormente desenvolvida de forma independente por Andrey Kolmogorov , em 1965, e Gregory Chaitin , por volta de 1966.

Existem várias variantes da complexidade de Kolmogorov ou informações algorítmicas; o mais amplamente utilizado baseia-se em programas de autodeterminação e deve-se principalmente a Leonid Levin (1974). Per Martin-Löf também contribuiu significativamente para a teoria da informação de sequências infinitas. Uma abordagem axiomática da teoria da informação algorítmica baseada nos axiomas de Blum (Blum 1967) foi introduzida por Mark Burgin em um artigo apresentado para publicação por Andrey Kolmogorov (Burgin 1982). A abordagem axiomática abrange outras abordagens na teoria da informação algorítmica. É possível tratar diferentes medidas de informação algorítmica como casos particulares de medidas definidas axiomaticamente de informação algorítmica. Em vez de provar teoremas semelhantes, como o teorema da invariância básica, para cada medida particular, é possível deduzir facilmente todos esses resultados de um teorema correspondente provado no cenário axiomático. Esta é uma vantagem geral da abordagem axiomática em matemática. A abordagem axiomática da teoria da informação algorítmica foi desenvolvida no livro (Burgin 2005) e aplicada a métricas de software (Burgin e Debnath, 2003; Debnath e Burgin, 2003).

Definições precisas

Uma string binária é considerada aleatória se a complexidade de Kolmogorov da string tiver pelo menos o comprimento da string. Um argumento de contagem simples mostra que algumas strings de qualquer comprimento são aleatórias e quase todas as strings estão muito próximas de serem aleatórias. Uma vez que a complexidade de Kolmogorov depende de uma escolha fixa de máquina de Turing universal (informalmente, uma "linguagem de descrição" fixa na qual as "descrições" são fornecidas), a coleção de strings aleatórias depende da escolha da máquina universal fixa. No entanto, a coleção de strings aleatórias, como um todo, tem propriedades semelhantes, independentemente da máquina fixa, portanto, pode-se (e freqüentemente faz) falar sobre as propriedades de strings aleatórias como um grupo sem ter que primeiro especificar uma máquina universal.

Uma sequência binária infinita é considerada aleatória se, para alguma constante c , para todo n , a complexidade de Kolmogorov do segmento inicial de comprimento n da sequência é pelo menos n  -  c . Pode-se mostrar que quase todas as sequências (do ponto de vista da medida padrão - "moeda justa" ou medida de Lebesgue - no espaço de sequências binárias infinitas) são aleatórias. Além disso, uma vez que pode ser mostrado que a complexidade de Kolmogorov em relação a duas máquinas universais diferentes difere em no máximo uma constante, a coleção de sequências infinitas aleatórias não depende da escolha da máquina universal (em contraste com cordas finitas). Essa definição de aleatoriedade é geralmente chamada de aleatoriedade de Martin-Löf , em homenagem a Per Martin-Löf , para distingui-la de outras noções semelhantes de aleatoriedade. Às vezes também é chamado de 1-aleatoriedade para distingui-lo de outras noções mais fortes de aleatoriedade (2-aleatoriedade, 3-aleatoriedade, etc.). Além dos conceitos de aleatoriedade de Martin-Löf, há também aleatoriedade recursiva, aleatoriedade de Schnorr e aleatoriedade de Kurtz etc. Yongge Wang mostrou que todos esses conceitos de aleatoriedade são diferentes.

(Definições relacionadas podem ser feitas para outros alfabetos além do conjunto .) ${\ displaystyle \ {0,1 \}}$

Seqüência específica

A teoria da informação algorítmica (AIT) é a teoria da informação de objetos individuais, usando a ciência da computação, e se preocupa com a relação entre computação, informação e aleatoriedade.

O conteúdo de informação ou complexidade de um objeto pode ser medido pelo comprimento de sua descrição mais curta. Por exemplo, a corda

"0101010101010101010101010101010101010101010101010101010101010101"

tem a breve descrição "32 repetições de '01'", enquanto

"1100100001100001110111101110110011111010010000100101011110010110"

presumivelmente, não tem uma descrição simples além de escrever a própria string.

Mais formalmente, a complexidade algorítmica (AC) de uma string x é definida como o comprimento do programa mais curto que calcula ou produz x , onde o programa é executado em algum computador universal de referência fixa.

Uma noção intimamente relacionada é a probabilidade de que um computador universal produza alguma string x quando alimentado com um programa escolhido aleatoriamente. Esta probabilidade algorítmica de "Solomonoff" (AP) é a chave para abordar o velho problema filosófico da indução de uma maneira formal.

A principal desvantagem de AC e AP é sua incomputabilidade. A complexidade de "Levin" limitada pelo tempo penaliza um programa lento adicionando o logaritmo de seu tempo de execução à sua duração. Isso leva a variantes computáveis ​​de AC e AP, e a busca universal de "Levin" (US) resolve todos os problemas de inversão no tempo ideal (exceto por alguma constante multiplicativa irrealisticamente grande).

AC e AP também permitem uma definição formal e rigorosa de aleatoriedade de strings individuais para não depender de intuições físicas ou filosóficas sobre não determinismo ou probabilidade. Grosso modo, uma string é "Martin-Löf" aleatória algorítmica (AR) se for incompressível no sentido de que sua complexidade algorítmica é igual ao seu comprimento.

AC, AP e AR são as subdisciplinas principais do AIT, mas o AIT se espalha em muitas outras áreas. Ele serve como base para o princípio do Comprimento Mínimo de Descrição (MDL), pode simplificar as provas na teoria da complexidade computacional , foi usado para definir uma métrica de similaridade universal entre objetos, resolve o problema do daemon Maxwell e muitos outros.

Veja também

Referências

links externos

• Teoria da Informação Algorítmica na Scholarpedia
• O relato de Chaitin sobre a história da AIT .

Leitura adicional