Мартин-Лёф: случайно — значит проходит все проверки

Колмогоров определил случайность через длину описания. Через год его шведский ученик определил её совершенно иначе — через статистические проверки. Оказалось, что определяют они одно и то же.

Что такое проверка на случайность

Статистик, глядя на последовательность, применяет к ней критерий: слишком много единиц; слишком длинные серии; каждый третий знак предсказывает следующий. Всякий такой критерий устроен одинаково: он выделяет множество «подозрительных» последовательностей, и это множество должно быть малым — иначе критерий забракует и честную монету.

Формализуем «малое» через вероятность. Проверка уровня $\varepsilon$ — множество $U$ последовательностей, для которого $\mu(U) \leqslant \varepsilon$; последовательность проверку не проходит, если попала в $U$.

Одного уровня мало: хочется сказать «подозрительна при любом уровне». Поэтому проверкой Мартин-Лёф называет вложенный набор

$$U_1 \supseteq U_2 \supseteq U_3 \supseteq \dots, \qquad \mu(U_m) \leqslant 2^{-m},$$

причём такой, что множества $U_m$ машина умеет перечислять. Последовательность не проходит проверку, если лежит во всех $U_m$ сразу.

Определение

Последовательность случайна, если она проходит всякую эффективную проверку.

На первый взгляд это пустое условие: проверок бесконечно много, и уж какая-нибудь да поймает кого угодно. Действительно, для каждой отдельной последовательности легко придумать проверку, которую именно она не пройдёт. Спасает слово «эффективная».

Главный ход: проверок счётное число

Эффективная проверка задаётся программой, а программ счётное число. Значит, все проверки можно занумеровать: $U^{(1)}, U^{(2)}, U^{(3)}, \dots$ — и сложить в одну:

$$U_m \;=\; \bigcup_{i \geqslant 0} U^{(i)}_{\,m + i + 1}.$$

Это по-прежнему проверка, потому что

$$\mu(U_m) \;\leqslant\; \sum_{i \geqslant 0} 2^{-(m+i+1)} \;=\; 2^{-m}.$$

Мера сошлась. Значит, существует одна проверка, которая сильнее всех остальных: пройдя её, последовательность проходит любую. Условие «выдерживает бесконечно много испытаний» оказалось проверяемым в один приём.

Отсюда сразу: множество неслучайных последовательностей имеет меру нуль. Почти всякая последовательность случайна — то же самое, что даёт счёт несжимаемых слов, только другим способом.

Почему это тот же класс — и одна честная оговорка

Совпадение двух определений оказалось не сразу и не даром.

У исходного определения через сложность обнаружилась неприятность, и нашёл её сам Мартин-Лёф: идеально несжимаемых бесконечных последовательностей не существует. У всякой последовательности сложность начальных отрезков бесконечно часто проседает ниже $n - f(n)$ для подходящей растущей $f$ — работает эффект «границы слова», из-за которого длину программы приходится ещё и как-то отделять от её содержимого.

Починка нашлась в начале 1970-х у Левина и Чейтина: считать длину программы в самоограниченном виде, когда машина сама узнаёт, где текст программы кончился. Такая сложность называется префиксной, и для неё утверждение становится точным (теорема Шнорра):

$$\text{последовательность случайна по Мартин-Лёфу} \iff K(x_{1..n}) \geqslant n - c \ \text{для всех } n .$$

Три определения сошлись

Получилась редкая в математике картина. Одно понятие определили с трёх совершенно разных сторон:

• со стороны игрока — нельзя разбогатеть: никакая стратегия не сделает капитал неограниченным;
• со стороны описания — нельзя сжать: нет программы короче самого объекта;
• со стороны статистика — нельзя уличить: проходит все эффективные проверки.

Все три дают в точности один и тот же класс. Такие совпадения в математике означают, что понятие поймано правильно, а не придумано: точно так же вычислимость оказалась одной и той же у Чёрча, ТьюрингаАлан Тьюринганглийский математик и криптоаналитик · 1912–1954Определил, что значит «вычислить», за десять лет до появления компьютеров, взломал «Энигму» и был осуждён за то, кем он был. и Поста.

О человеке

Пер Мартин-Лёф (род. 1942) приехал в Москву учиться к КолмогоровуАндрей Николаевич Колмогороврусский и советский математик · 1903–1987Дал вероятности аксиомы, турбулентности — закон, сложности — определение, а школьной математике в СССР — программу, по которой учились миллионы. в 1964 году, двадцатидвухлетним, и определение случайности сложилось у него там же. После этого он ушёл из теории вероятностей совсем — и стал одним из главных людей конструктивной математики.

Его интуиционистская теория типов (1970-е) — прямая основа языка Agda и та почва, на которой выросли унивалентные основания Воеводского и весь нынешний обиход машинной проверки доказательств. Получается изящная симметрия: человек, сказавший, что значит «случайно», сказал заодно и что значит «доказано так, что машина проверит».