HSE Kolmogorov complexity, lecture 3: Solomonoff induction

-- A simple mistake bound from semimeasures. -- There is no (computable) multiplicatively maximal semimeasure. -- There exists a lower semicomputable (lsc) that exceeds any other lsc semimeasure up to a constant. This measure is called algorithmic probability. -- Solomonoff's theorem on the convergence of conditional algorithmic probability to computable conditional probability. Course website: http://wiki.cs.hse.ru/Kolmogorov_complexity_fall2025