TY - JOUR
AU - Campani, Carlos A. P.
AU - Menezes, Paulo Blauth
PY - 2004/12/20
Y2 - 2022/08/10
TI - Teorias da Aleatoriedade
JF - Revista de Informática Teórica e Aplicada
JA - RITA
VL - 11
IS - 2
SE - Tutoriais
DO - 10.22456/2175-2745.5983
UR - https://www.seer.ufrgs.br/index.php/rita/article/view/rita_v11_n2_p75-98
SP - 75-98
AB - 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.<b>Keywords</b>: randomness, Kolmogorov complexity, Turing machine, computability,probability.
ER -