Алгоритмические тесты и случайность относительно классов мер

Приводятся некоторые новые результаты об алгоритмической случайности по отношению к классам мер, а также подробно излагаются известные (но не опубликованные подробно) результаты об алгоритмических тестах случайности. Мы начинаем с переформулировки определения случайности по Мартин-Лёфу в терминах тестов случайности (функций, измеряющих степень “неслучайности” последовательностей). Приводится формула, выражающая значение универсального теста в терминах префиксной сложности. Рассматриваются также варианты определения дефекта случайности для конечных слов, связанные с универсальным тестом. Далее рассматривается (введенное еще Мартин-Лёфом) понятие бернуллиевой последовательности (как последовательности, не противоречащей гипотезе о том, что все испытания независимы и имеют одинаковую вероятность успеха). Показано, что определение с помощью универсального теста эквивалентно первоначальному определению Мартин-Лёфа и что последовательность является бернуллиевой тогда и только тогда, когда она случайна по Мартин-Лёфу относительно бернуллиевой меры $B_p$ при некотором $p$ (с оракулом для $p$). Затем этот же вопрос (о сравнении тестов относительно классов мер и тестов как функции двух аргументов – последовательности и меры) применяется к произвольным эффективно замкнутым классам мер в канторовском пространстве. Для бернуллиевых мер $B_p$ значение $p$ можно восстановить, глядя на произвольную случайную относительно $B_p$ последовательность (свойство ортогональности). Изучаются свойства ортогональных классов мер, и указываются предположения, в которых два понятия случайности (равномерная и безоракульная) совпадают. В заключение рассматриваются обобщения некоторых из указанных результатов на случай произвольных метрических пространств.