### Resumen

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.

Idioma original | English |
---|---|

Título de la publicación alojada | STACS 2009 - 26th International Symposium on Theoretical Aspects of Computer Science |

Páginas | 469-480 |

Número de páginas | 12 |

Volumen | 3 |

Estado | Published - 2009 |

Evento | 26th International Symposium on Theoretical Aspects of Computer Science, STACS 2009 - Freiburg, Germany Duración: 26 feb 2009 → 28 feb 2009 |

### Other

Other | 26th International Symposium on Theoretical Aspects of Computer Science, STACS 2009 |
---|---|

País | Germany |

Ciudad | Freiburg |

Período | 26/02/09 → 28/02/09 |

### ASJC Scopus subject areas

- Software

### Citar esto

*STACS 2009 - 26th International Symposium on Theoretical Aspects of Computer Science*(Vol. 3, pp. 469-480)

}

*STACS 2009 - 26th International Symposium on Theoretical Aspects of Computer Science.*vol. 3, pp. 469-480, 26th International Symposium on Theoretical Aspects of Computer Science, STACS 2009, Freiburg, Germany, 26/02/09.

**Randomness on computable probability spaces - A dynamical point of view.** / Gacs, Peter; Hoyrup, Mathieu; Rojas, Cristobal.

Resultado de la investigación: Conference contribution

TY - GEN

T1 - Randomness on computable probability spaces - A dynamical point of view

AU - Gacs, Peter

AU - Hoyrup, Mathieu

AU - Rojas, Cristobal

PY - 2009

Y1 - 2009

N2 - 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.

AB - 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.

KW - Birkhoff's ergodic theorem

KW - Computable measures

KW - Schnorr randomness

UR - http://www.scopus.com/inward/record.url?scp=84880198126&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:84880198126

SN - 9783939897095

VL - 3

SP - 469

EP - 480

BT - STACS 2009 - 26th International Symposium on Theoretical Aspects of Computer Science

ER -