## Abstract

Combining outcomes of coin-tossing and transducer algorithms it is possible to generate with probability close to 1 very pathological sequences for which computable probabilistic forecasting is impossible. These sequences are not random with respect to any reasonable probability distribution. A natural consequence from the definition of such sequences is that each simple measure of the set of all such sequences is equal to 0. It was Kolmogorov's and Levin's idea to estimate the probability of generating of such sequences in the combinations of probabilistic and algorithmic processes [8, 14, 21]. We collect several results in this direction for infinite sequences and asymptotic results for finite sequences including estimation of space and time of losing randomness for time bounded forecasting systems (a correction to [22]).

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

Pages (from-to) | 363-382 |

Number of pages | 20 |

Journal | Theoretical Computer Science |

Volume | 207 |

Issue number | 2 |

DOIs | |

Publication status | Published - 6 Nov 1998 |

Externally published | Yes |

## Keywords

- Algorithmic information theory
- Computable calibration
- Forecasting systems
- Measure of nonrandomness
- Non-stochastic sequences