Теорема Миллера–Ю даёт
критерий случайности в терминах простой колмогоровской
сложности (не монотонной и не префиксной): последовательность случайна по
равномерной мере тогда и только тогда, когда для любой вычислимой функции f
с конечной суммой Σ 2-f(n) имеет место неравенство
K(ω1...ωn) > n – f(n) + c для
некоторого c и для всех n.
Необходимость этого по существу уже была известна в 1970-e годы (Мартин-Лёф,
Звонкин и Левин), но вновь обратили внимание на это и доказали достаточность
Миллер и Ю совсем недавно (статья ещё не опубликована, но есть на сайте
Миллера). Их доказательство использует префиксную сложность. Однако можно
доказать это и непосредственно, используя лишь известную с 1973 года технику
Левина и Шнорра (и совсем несложно), как независимо заметили L. Bienvenu,
W. Merkle и другие.
Совместную статью Миллера и Ю "On initial segment
complexity and degrees of randomness" можно найти на его
сайте.