Repositório Digital

A- A A+

Teorias da Aleatoriedade

.

Teorias da Aleatoriedade

Mostrar registro completo

Estatísticas

Título Teorias da Aleatoriedade
Autor Campani, Carlos Antonio Pereira
Menezes, Paulo Fernando Blauth
Resumo 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.
Abstract 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.
Contido em Revista de informática teórica e aplicada. Porto Alegre, RS. Vol. 11, n. 2 (dez. 2004), p. 75-98
Assunto Aleatoriedade
Complexidade : Kolmogorov
Maquinas : Turing
Teoria : Ciência : Computação
[en] Computability
[en] Kolmogorov complexity
[en] Probability
[en] Randomness
[en] Turing machine
Origem Nacional
Tipo Artigo de periódico
URI http://hdl.handle.net/10183/19897
Arquivos Descrição Formato
000455360.pdf (132.9Kb) Texto completo Adobe PDF Visualizar/abrir

Este item está licenciado na Creative Commons License

Este item aparece na(s) seguinte(s) coleção(ões)


Mostrar registro completo

Percorrer



  • O autor é titular dos direitos autorais dos documentos disponíveis neste repositório e é vedada, nos termos da lei, a comercialização de qualquer espécie sem sua autorização prévia.
    Projeto gráfico elaborado pelo Caixola - Clube de Criação Fabico/UFRGS Powered by DSpace software, Version 1.8.1.