Logo image
Se connecter
Ergodic-Type Characterizations of Algorithmic Randomness
Acte de colloque   Avec comité de lecture

Ergodic-Type Characterizations of Algorithmic Randomness

Laurent Bienvenu, Adam Day, Ilya Mezhirov et Alexander Shen
PROGRAMS, PROOFS, PROCESSES, Vol.6158, pp.49-58
Lecture Notes in Computer Science
01/01/2010

Résumé

Computer Science Computer Science, Theory & Methods Science & Technology Technology
A theorem of Kucera states that given a Martin-Lof random infinite binary sequence omega and an effectively open set A of measure less than 1, some tail of omega is not in A. We show that this result can be seen as an effective version of Birkhoff's ergodic theorem (in a special case). We prove several results in the same spirit and generalize them via an effective ergodic theorem for bijective ergodic maps.

Indicateurs

1 Consultations de la notice

Détails

Logo image