Randomness on Computable Probability Spaces - A Dynamical Point of ViewReportar como inadecuado

Randomness on Computable Probability Spaces - A Dynamical Point of View - Descarga este documento en PDF. Documentación en PDF para descargar gratis. Disponible también para leer online.

1 Boston University - Computer Science Department Boston 2 ENS Paris - École normale supérieure - Paris 3 CARTE - Theoretical adverse computations, and safety Inria Nancy - Grand Est, LORIA - FM - Department of Formal Methods 4 CREA - Centre de recherche en épistémologie appliquée

Abstract : We extend the notion of randomness in the version introduced by Schnorr to computable Probability Spaces and compare it to a dynamical notion of randomness: typicality. Roughly, a point is typical for some dynamic, if it follows the statistical behavior of the system Birkhoff-s pointwise ergodic theorem. We prove that a point is Schnorr random if and only if it is typical for every mixing computable dynamics. To prove the result we develop some tools for the theory of computable probability spaces for example, morphisms that are expected to have other applications.

Keywords : Schnorr Randomness Birkhoff-s ergodic theorem computable measures

Autor: Peter Gacs - Mathieu Hoyrup - Cristobal Rojas -

Fuente: https://hal.archives-ouvertes.fr/


Documentos relacionados