## Abstract

In the framework of the Kolmogorov's approach to the substantiation of the probability theory and information theory on the base of the theory of algorithms we try to formulate probabilistic laws, i.e. statements of the form P{ω|A(ω)} = 1, where A(ω) is some formula, in "pointwise" form "if ω is random then A(ω) holds". Nevertheless, not all proofs of such laws can be directly translated into the algorithmic form. In [11] two examples have been distinguished -Birkhoff's [2] ergodic theorem and Shannon-McMillan-Breiman theorem of information theory [1]. In this paper an analysis of algorithmic effectiveness of these theorems is given. We prove that Birkhoff's ergodic theorem is indeed in some strong sense "nonconstructive". At the same time the claim to formulate probabilistic laws for algorithmically random sequences is not so restrictive. We present the versions of these laws for individual random sequences.

Original language | English |
---|---|

Pages (from-to) | 343-361 |

Number of pages | 19 |

Journal | Theoretical Computer Science |

Volume | 207 |

Issue number | 2 |

DOIs | |

Publication status | Published - 6 Nov 1998 |

Externally published | Yes |

## Keywords

- Algorithmic information theory
- Birkhoff's ergodic theorem
- Individual random sequence
- Kolmogorov complexity
- Shannon-McMillan-Breiman theorem