Non-stochastic infinite and finite sequences

V. V. V'yugin

Research output: Contribution to journalArticlepeer-review

8 Citations (Scopus)

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 languageEnglish
Pages (from-to)363-382
Number of pages20
JournalTheoretical Computer Science
Volume207
Issue number2
DOIs
Publication statusPublished - 6 Nov 1998
Externally publishedYes

Keywords

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

Fingerprint

Dive into the research topics of 'Non-stochastic infinite and finite sequences'. Together they form a unique fingerprint.

Cite this