# K-trivial, K-low and ML-low: a tutorial

This year Laurent Bienvenu (visiting Moscow) taught a course on Kolmogorov complexity and randomness; at the end he tried to present the equivalence between these three notion in a less formal and more easy-to-read way. After several discussions, we tried to write down an exposition of the proof, now added to pdf-logic-blog. This is essentially the original proof, but we tried to present it in a more structured way; the technical difference is mostly in explicit game interpretation (the result is a corollary of an existence of a winning strategy in a combinatorial game) and n the different `flow of control’: now the strategy is described as a family of parallel threads (each of them recursively creates other threads, etc.) that are waked up and put into sleep depending on the changes in the opponent’s path.