Teorias da Aleatoriedade

Abstract

Este trabalho apresenta uma revisão bibliográfica sobre a definição de “seqüência aleatória”. Nós enfatizamos a definição de Martin-Löf e a definição baseada em incompressividade (complexidade de Kolmogorov). Complexidade de Kolmogorov é uma teoria sofisticada e profunda da informação e da aleatoriedade baseada na máquina de Turing. Estas duas definições resolvem todos os problemas das outras abordagens e satisfazem o nosso conceito intuitivo de aleatoriedade, sendo matematicamente corretas. Adicionalmente, apresentamos a abordagem de Schnorr que inclui um requisito de efetividade (computabilidade) em sua definição. São apresentadas as relações entre estas diversas definições de forma crítica.

This work is a survey about the definition of “random sequence”. We emphasize the definition of Martin-Löf and the definition based on incompressibility (Kolmogorov complexity). Kolmogorov complexity is a profound and sofisticated theory of information and randomness based on Turing machines. These two definitions solve all the problems of the other approaches, satisfying our intuitive concept of randomness, and both are mathematically correct. Furthermore, we show the Schnorr’s approach, that includes a requisite of effectiveness (computability) in his definition. We show the relations between all definitions in a critical way.