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.

Hope this could help future readers (and lecturers) – and thanks in advance for comments…

gentle introduction to triviality

Leave a Reply