#матлог #учёба #спецсеминар

Kolmogorov seminar on complexity (for receive the zoom link, please email nikolay.vereshchagin@gmail.com)

This Monday 24 November, 18:30 MSK, we will have a talk by Alexander Shen.

Upcrossing inequalities revisited

Bishop used upcrossing inequalities to prove Birkhoff's ergodic theorem. Vyugin used his inequality (in one of the forms) to prove the algorithmic version of it (for Martin-L\"of random sequences). It turns out that another version (a stronger one, from a different paper of Bishop) immediately implies the result of Barmpalias and Lewis-Pye about lower semicomputable randoms: if $a_n$ and $b_n$ are computable increasing sequences of rational numbers that converge to reals $A$ and $B$, and $A$ is random, then $(B-b_n)/(A-a_n)$ converges. And, to finish the story, Misha Andreev invented a simple and nice proof of the Bishop's inequality used in this argument.

➰ ВК