Teoria algorítmica da informação

A teoria algorítmica da informação é um subcampo da teoria da informação e da ciência da computação que se preocupa com a relação entre computação e informação. De acordo com Gregory Chaitin, ela é "o resultado de colocar a teoria da informação de Shannon e teoria da computabilidade de Turing em uma coqueteleira, agitando-a vigorosamente".

Visão geral

A teoria algorítmica da informação estuda, principalmente, medidas de complexidade em cadeias (ou outras estruturas de dados). Como a maioria dos objetos matemáticos podem ser descritos em termos de cadeias, ou como o limite de uma sequência de cadeias, ela pode ser usadas para estudar uma ampla variedade de objetos matemáticos, incluindo números inteiros.

Informalmente, a partir do ponto de vista da teoria algorítmica da informação, o conteúdo de informação de uma cadeia é equivalente ao comprimento da representação autossuficiente o mais comprimida possível da cadeia. A representação auto-suficiente é essencialmente um programa - em alguma linguagem de programação universal fixa, mas por outro lado irrelevante - que, quando executada, gera a cadeia original.

A partir deste ponto de vista, 3000 páginas de uma enciclopédia contém, na verdade, menos informação que 3000 páginas de letras completamente aleatórias, apesar do fato de que a enciclopédia é muito mais útil. Isso porque, para reconstruir toda a sequência de letras aleatórias, é preciso saber, mais ou menos, o que cada letra representa. Por outro lado, se cada vogal fosse retirada da enciclopédia, alguém com conhecimento razoável da língua na qual foi escrita poderia reconstruí-la, assim como se poderia provavelmente reconstruir a frase em inglês "Ths sntnc hs lw nfrmtn cntnt" a partir do contexto e consoantes presente.

Ao contrário da teoria da informação clássica, a teoria algorítmica da informação dá definições formais, rigorosas de uma cadeia aleatória e uma sequência infinita aleatória que não dependem de intuições físicas ou filosóficas sobre não-determinismo ou verossimilhança. (O conjunto de sequências 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 cadeia é invariável até uma constante aditiva, dependendo apenas da escolha da máquina de Turing universal. Por esta razão, o conjunto de sequências aleatórias infinitas é independente da escolha da máquina universal).

Alguns dos resultados da teoria algorítmica da informação, como o teorema da incompletude de Chaitin, parecem desafiar intuições matemáticas e filosóficas comuns. O mais notável é a construção da constante Ω de Chaitin, um número real que expressa a probabilidade de uma máquina de Turing universal auto-delimitada parar quando sua entrada é fornecida pelo jogar de uma moeda (às vezes, considera-se como a probabilidade de que um programa de computador aleatório irá, eventualmente, parar). Embora Ω seja facilmente definido, em qualquer teoria axiomática consistente só se pode calcular um número finito de dígitos de Ω, por isso é de certa forma desconhecido, proporcionando um limite absoluto no conhecimento que é uma reminiscência do teorema 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 aleatória de algoritmos e, assim, os seus dígitos binários são distribuídos uniformemente (de fato, é normal).

História

A teoria algorítmica da informação foi fundada por Ray Solomonoff, que publicou as ideias básicas em que o campo se baseia como parte de sua invenção de probabilidade algorítmica - uma maneira de superar problemas graves associados à aplicação das regras de Bayes em estatística. Ele descreveu pela primeira vez os seus resultados em uma conferência em Caltech em 1960, e em um relatório, em fevereiro de 1960, "Relatório Preliminar sobre a Teoria Geral da Inferência Indutiva". A teoria algorítmica da informação mais tarde foi desenvolvida de forma independente por Andrey Kolmogorov , em 1965, e Gregory Chaitin, em torno de 1966.

Existem diversas variantes da complexidade Kolmogorov ou teoria algorítmica da informação; a mais amplamente utilizada é a baseada em programas auto-delimitantes e é devido, 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 algorítmica da informação com base nos axiomas de Blum (Blum 1967) foi introduzida por Mark Burgin em um trabalho apresentado para publicação por Andrey Kolmogorov (Burgin 1982). A abordagem axiomática engloba outras abordagens na teoria algorítmica da informação.

É possível tratar diferentes medidas algorítmica da informação como casos particulares de medidas, definidas axiomaticamente, algorítmicas da informação . Em vez de provar teoremas semelhantes, como o teorema fundamental da invariância, para cada medida particular, é possível deduzir facilmente todos os resultados de um teorema correspondente provado pela definição axiomática. Esta é uma vantagem geral da abordagem axiomática em matemática. A aproximação axiomática à teoria algorítmica da informação foi desenvolvida no livro (Burgin 2005) e aplicada a métricas de softwares (Burgin e Debnath, 2003; Debnath e Burgin, 2003).

Definições precisas

Ver artigo principal: Complexidade de Kolmogorov

Uma cadeia binária é dita aleatória se a complexidade de Kolmogorov da cadeia é, pelo menos, o comprimento da codeia. Um argumento simples de contagem mostra que algumas cadeias de qualquer comprimento são aleatórias, e quase todas as cadeias estão muito perto de serem aleatórias. Como a complexidade de Kolmogorov depende de uma escolha fixa da máquina de Turing universal (informalmente, uma "linguagem de descrição" fixa em que as "descrições" são dadas), a coleção de cadeias aleatórias não depende da escolha de uma máquina universal fixa. No entanto, a coleção de cadeias aleatórias, como um todo, tem propriedades semelhantes, independentemente da máquina fixa, assim, é possível (e muitas vezes o fazem) falar sobre as propriedades de sequências aleatórias como um grupo sem ter que primeiro especificar uma máquina universal.

Uma sequência binária infinita é dita ser 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 demonstrar que quase toda sequência (do ponto de vista da medida padrão - "moeda honesta" ou medida de Lebesgue - no espaço de sequências binárias infinitas) é aleatória. Além disso, uma vez que pode ser mostrado que a complexidade de Kolmogorov relativa a duas máquinas universais diferentes difere em não mais do que uma constante, a coleção de sequências aleatórias infinitas não depende da escolha da máquina universal (em contraste com as cadeias finitas). Esta definição de aleatoriedade é geralmente chamada de aleatoriedade de Martin-Löf, por causa de Per Martin-Löf, para distingui-la de outras noções semelhantes de aleatoriedade. Também pode ser chamado, às vezes, de 1-aleatoriedade para distingui-la de outras noções mais fortes de aleatoriedade (2-aleatoriedade, 3-aleatoriedade, etc.).

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

Sequência específica

A teoria algorítmica da informação (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 a complexidade de um objeto podem ser medidos pelo comprimento da sua descrição mais curta. Por exemplo, a cadeia

"0101010101010101010101010101010101010101010101010101010101010101"

tem a menor descrição sendo: “31 repetições de '01'”, enquanto a cadeia

"1100100001100001110111101110110011111010010000100101011110010110"

supostamente não tem uma descrição simples que não seja escrever a cadeia em si.

Mais formalmente, a complexidade algorítmica (AC) de uma cadeia x é definido como o comprimento do programa mais curto que computa ou gera x, em que o programa é executado em uma referência fixa de computador universal.

Uma noção estreitamente relacionada é a probabilidade de que um computador universal gera alguma cadeia x quando tem como entrada um programa escolhido ao acaso. O algoritmo de probabilidade "Solomonoff" (AP) é fundamental para combater, de uma maneira formal, o velho problema filosófico da indução.

A principal desvantagem do AC e AP são a sua incomputabilidade. A complexidade limitada pelo tempo de "Levin" penaliza um programa lento adicionando um logaritmo do seu tempo de execução para o seu comprimento. Isto leva a variantes computáveis de AC e AP, e a busca universal “Levin” (US) resolve todos os problemas de inversão em ótimo tempo (exceto por algumas constantes de multiplicação exageradas).

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

AC, AP, e AR são os sub-disciplinas centrais da AIT, mas AIT se ramifica em muitas outras áreas. Ele serve como a base do princípio da descrição do mínimo comprimento (MDL), pode simplificar provas em teoria da complexidade computacional, tem sido utilizado para definir uma métrica universal semelhante entre objetos, resolve o problema daemon de Maxwell, e muitos outros.

Ver também

• Complexidade de Kolmogorov
• Epistemologia
• Raciocínio indutivo

Ligações externas

• Algorithmic Information Theory (Scholarpedia)
• Chaitin's account of the history of AIT.

Leitura complementar

• Blum, M. (1967) On the Size of Machines, Information and Control, v. 11, pp. 257–265
• Blum M. (1967a) A Machine-independent Theory of Complexity of Recursive Functions, Journal of the ACM, v. 14, No.2, pp. 322–336
• Burgin, M. (1982) Generalized Kolmogorov complexity and duality in theory of computations, Soviet Math. Dokl., v.25, No. 3, pp. 19–23
• Burgin, M. (1990) Generalized Kolmogorov Complexity and other Dual Complexity Measures, Cybernetics, No. 4, pp. 21–29
• Burgin, M. Super-recursive algorithms, Monographs in computer science, Springer, 2005
• Calude, C.S. (1996) Algorithmic information theory: Open problems, J. UCS, v. 2, pp. 439–441
• Calude, C.S. Information and Randomness: An Algorithmic Perspective, (Texts in Theoretical Computer Science. An EATCS Series), Springer-Verlag, Berlin, 2002
• Chaitin, G.J. (1966) On the Length of Programs for Computing Finite Binary Sequences, J. Association for Computing Machinery, v. 13, No. 4, pp. 547–569
• Chaitin, G.J. (1969) On the Simplicity and Speed of Programs for Computing Definite Sets of Natural Numbers, J. Association for Computing Machinery, v. 16, pp. 407–412
• Chaitin, G.J. (1975) A Theory of Program Size Formally Identical to Information Theory, J. Association for Computing Machinery, v. 22, No. 3, pp. 329–340
• Chaitin, G.J. (1977) Algorithmic information theory, IBM Journal of Research and Development, v.21, No. 4, 350-359
• Chaitin, G.J. Algorithmic Information Theory, Cambridge University Press, Cambridge, 1987
• Kolmogorov, A.N. (1965) Three approaches to the definition of the quantity of information, Problems of Information Transmission, No. 1, pp. 3–11
• Kolmogorov, A.N. (1968) Logical basis for information theory and probability theory, IEEE Trans. Inform. Theory, vol. IT-14, pp. 662–664
• Levin, L. A. (1974) Laws of information (nongrowth) and aspects of the foundation of probability theory, Problems of Information Transmission, v. 10, No. 3, pp. 206–210
• Levin, L.A. (1976) Various Measures of Complexity for Finite Objects (Axiomatic Description), Soviet Math. Dokl., v. 17, pp. 522–526
• Li, M., and Vitanyi, P. An Introduction to Kolmogorov Complexity and its Applications, Springer-Verlag, New York, 1997
• Solomonoff, R.J. (1960) A Preliminary Report on a General Theory of Inductive Inference, Technical Report ZTB-138, Zator Company, Cambridge, Mass.
• Solomonoff, R.J. (1964) A Formal Theory of Inductive Inference, Information and Control, v. 7, No. 1, pp. 1–22; No.2, pp. 224–254
• Solomonoff, R.J. (2009) Algorithmic Probability: Theory and Applications, Information Theory and Statistical Learning, Springer NY, Emmert-Streib, F. and Dehmer, M. (Eds), ISBN 978-0-387-84815-0.
• Van Lambagen (1989). «Algorithmic Information Theory». Journal for Symbolic Logic. 54: 1389–1400. doi:10.1017/S0022481200041153 
• Zurek, W.H. (1991) Algorithmic Information Content, Church-Turing Thesis, physical entropy, and Maxwell’s demon, in Complexity, Entropy and the Physics of Information, (Zurek, W.H., Ed.) Addison-Wesley, pp. 73–89
• Zvonkin, A.K. and Levin, L. A. (1970) The Complexity of Finite Objects and the Development of the Concepts of Information and Randomness by Means of the Theory of Algorithms, Russian Mathematics Surveys, v. 256, pp. 83–124