RUS  ENG
Full version
JOURNALS // Problemy Peredachi Informatsii // Archive

Probl. Peredachi Inf., 2009 Volume 45, Issue 1, Pages 60–70 (Mi ppi1260)

This article is cited in 1 paper

Large Systems

Algorithmic randomness and splitting of supermartingales

An. A. Muchnik


Abstract: Randomness in the sense of Martin-Löf can be defined in terms of lower semicomputable supermartingales. We show that such a supermartingale cannot be replaced by a pair of supermartingales that bet only on even bits (the first one) and on odd bits (the second one) knowing all the preceding bits.

UDC: 621.391.1:519.2

Received: 10.09.2008


 English version:
Problems of Information Transmission, 2009, 45:1, 54–64

Bibliographic databases:


© Steklov Math. Inst. of RAS, 2024