Карта → линии → сквозной сюжет

Демон и монетка

есть ли случай на самом деле — и что значит «эта последовательность случайна»

Спросите класс, бывает ли случайность на самом деле, — и кто-нибудь непременно построит демона. Если бы кто-то знал все законы и положение каждой молекулы, он предсказал бы и монетку, и погоду, и завтрашний день; значит, случайность — просто имя нашего незнания. Возразить нечего: рассуждение верное, ему двести лет, и придумал его Лаплас. Эта нить — о том, что было дальше.

Считать научились раньше, чем определять. Жребий тысячелетиями был способом спросить не природу, а высшую волю, и сосчитать его никому не приходило в голову. Летом 1654 года шансы наконец сосчитали, через полвека доказали, что частота сходится к вероятности, — и на двести пятьдесят лет остановились на этом. Вероятность события определена; что такое случайный объект, никто не спрашивает.

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

Попытки определить. Борель находит признак: у случайного числа все цифры и все их сочетания встречаются с правильной частотой. Оказывается, таковы почти все числа — и ни одного привычного предъявить нельзя. Фон Мизес заходит со стороны игрока: случайно то, против чего не работает никакая система игры. Колмогоров в 1933 году строит аксиоматику, которая обходит вопрос стороной, — и это оказывается правильным ходом, потому что определение Мизеса через двадцать лет опровергают. А Рамсей тем временем доказывает встречное: полного беспорядка не бывает вовсе, в достаточно большом хаосе порядок заводится сам.

Ответ. В 1965 году Колмогоров возвращается к вопросу, который сам же обошёл, и отвечает: случайно то, что нельзя описать короче, чем выписать целиком. Миллион нулей задаётся строчкой программы, случайная строка — только собой. Случайность перестала быть свойством мира и стала свойством описания. Мартин-Лёф приходит к тому же классу с другой стороны, а Чейтин предъявляет счёт: почти всякий объект случаен — и почти ни про один этого нельзя доказать.

Неожиданный поворот. Пока случайность определяли, ею научились пользоваться: Эрдёш доказывает случайностью теоремы, Улам и фон Нейман ею считают, Соловей и Штрассен бросают монетку вместо доказательства — и на этом до сих пор держится выдача ключей. Тут выясняется третье возможное определение: случайно то, что не отличить от случайного. Не свойство мира, не свойство описания, а свойство того, кто смотрит. А из него следует подозрение, до сих пор не доказанное: вычислителю настоящая случайность, скорее всего, вообще не нужна.

И наконец про демона. Вопрос, который считался философским, оказался проверяемым. Белл выписал неравенство: если исходы предопределены заранее и ничто не обгоняет свет, некоторая величина не может превысить двойки. Опыт даёт почти тройку. Демон, знающий положения и скорости всех частиц, — тот самый, которого строит школьник, — противоречит эксперименту.

Честный итог нити такой. Существует ли случайность «на самом деле» — математика не доказала и не собирается: это вопрос не её ведения. Но три разных её отдела независимо доказали, что случайность неустранима — из предсказания, из описания и из опыта. А заодно выяснилось, что вопрос «есть ли случай» был не самым интересным: гораздо содержательнее оказался вопрос «а что вы, собственно, называете случайным», и вот на него ответ есть.

Открыть на карте

1

Амьен ок. 1250 г.
«De Vetula»: шансы в стихах
Завязка: жребий перестаёт быть способом спросить свыше и становится счётным

В латинской поэме De Vetula дан один из самых ранних известных в Европе правильных комбинаторных разборов броска трёх костей. Автор различает сочетания очков и способы, которыми они могут получиться, — ключевой шаг от бытового рассуждения об удаче к математике случайных исходов.
2

Париж лето 1654
Лето 1654 года: Паскаль, Ферма и задача о разделе ставки
Шансы научились считать — не определив, что именно считают

Переписка Блеза Паскаля и Пьера Ферма дала общий метод решения задачи о разделе банка в прерванной игре. Главное новшество: справедливую долю игрока определяют не по уже набранным очкам, а по вероятности его будущей победы.
3

Базель рукопись — к 1690-м; издана в 1713
«Ars Conjectandi»: закон больших чисел
Частота сходится к вероятности. К чему сходится сама вероятность, не спрашивают

Якоб Бернулли доказывает первую предельную теорему: частота сходится к вероятности — значит, шансы можно измерять наблюдениями. Мост между исчислением игр и данными Граунта.
4

Париж 1810–1812
Лаплас: собор классической вероятности
Прямой ответ: случайности нет, есть незнание. Демон, знающий всё, не удивляется ничему

Центральная предельная теорема (1810) объясняет вездесущность колокола де Муавра, а «Théorie analytique des probabilités» (1812) собирает всю классическую теорию под одной крышей.
5

Париж мемуар о задаче трёх тел — 1890, «Наука и метод» — 1908
Пуанкаре: случай как чувствительность
Возражение: незнание неустранимо — ничтожная разница в начале даёт любой конец

Лаплас утверждал: случайности нет, есть наше незнание. Пуанкаре соглашается — и делает обратный вывод. Разбирая задачу трёх тел, он находит движения, у которых ничтожная разница в начальных данных через некоторое время даёт совершенно разные траектории. Значит, незнание неустранимо: чтобы предсказывать, демону мало знать почти всё, ему нужно знать точно, а точно не бывает. Детерминизм остаётся, предсказуемость исчезает — и случай возвращается уже как строгое понятие.
6

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

Эмиль Борель доказывает усиленный закон больших чисел и заодно устанавливает, что почти каждое число «нормально» — в его десятичной записи все цифры встречаются с равной частотой. Теория меры входит в вероятность за 24 года до Колмогорова.
7

Берлин статья — 1919, «Вероятность, статистика и истина» — 1928
Фон Мизес: случайно то, где нельзя выиграть системой
Первое определение: случайно то, против чего нет системы игры

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

Кембридж 1930
Рамсей: полный беспорядок невозможен
Встречный запрет: полного беспорядка не бывает, порядок заводится сам

В любой достаточно большой структуре найдётся большой упорядоченный кусок — как ни старайся его разрушить. Теорема доказана как вспомогательная лемма в работе по логике; автор умер в том же году, двадцати шести лет.
9

Москва 1933
«Grundbegriffe»: вероятность = мера
Аксиомы обходят вопрос: определена вероятность события, а не случайность объекта

Колмогоров аксиоматизирует вероятность как теорию меры — ту самую, что выросла из рядов Фурье через Лебега. Вся современная вероятность стоит на этой книге.
10

Париж диссертация — 1939
Вилль: коллектив опровергнут, появляется мартингал
Определение Мизеса опровергнуто; на его месте появляется мартингал

Жан Вилль защищает в Париже диссертацию, где показывает: какой счётный набор правил выбора ни возьми, найдётся последовательность, удовлетворяющая всем условиям Мизеса и заведомо не случайная — доля единиц подходит к своему пределу всё время с одной стороны. Заодно Вилль вводит понятие, которым такие подделки и ловят: мартингал — капитал игрока, ставящего на исходы. Случайно то, на чём нельзя разбогатеть; через четырнадцать лет Дуб сделает из этого целую теорию.
11

Лос-Аламос 1946–1949
Улам и фон Нейман: вычислять вероятностью
Практическая нужда: машине случайность необходима — и взять её негде

Станислав Улам, раскладывая пасьянс во время болезни, понимает: вместо того чтобы вычислять вероятность комбинаторно, проще разыграть партии и посчитать. Поворот на 180 градусов — теперь не математика служит случаю, а случай служит математике.
12

Будапешт 1947
Эрдёш: вероятность как инструмент существования
Переворот применения: случайностью не описывают мир, а доказывают теоремы

Чтобы доказать, что нужный объект существует, Эрдёш предложил не строить его, а бросить монету и посчитать вероятность. Доказательство занимает три строки, даёт оценку, которую за семьдесят пять лет почти не улучшили, — и не позволяет предъявить ни одного примера.
13

Мюррей-Хилл (Bell Labs) 1948
Шеннон: вероятность становится информацией
Непредсказуемость получает число — но это мера источника, а не отдельной последовательности

Клод Шеннон определяет количество информации через энтропию распределения и доказывает, что у канала связи есть точная пропускная способность. Вероятность из инструмента расчёта шансов превращается в меру незнания.
14

Москва семинар в МГУ, 1960-е; публикации 1962–1964
Колмогоров: стих как случайный процесс
Информация в стихе считается плохо — и становится ясно, чего не хватает

В начале 1960-х Колмогоров ведёт в Московском университете семинар по стиховедению и приносит туда то, чего филологии не хватало полвека: нулевую гипотезу. Ритмическая особенность существует, только если её нельзя объяснить одним словарём языка.
15

Кембридж (Массачусетс) перезапуск расчёта — 1961, статья — 1963, «крыло бабочки» — 1972
Лоренц: три уравнения, которые нельзя досчитать
Три уравнения без единого случайного члена, решения которых не предсказать

Метеоролог из Массачусетского технологического перезапускает расчёт погоды с распечатки, где числа округлены до трёх знаков вместо шести, — и получает совершенно другую погоду. Из этой неприятности он выделяет систему трёх обыкновенных дифференциальных уравнений: полностью детерминированную, без единого случайного слагаемого, с решениями, которые не повторяются никогда и расходятся экспоненциально. То, о чём Пуанкаре рассуждал, здесь можно нарисовать.
16

Москва 1963 и 1965
Колмогоров: случайно — значит несжимаемо
Развязка: случайно то, что нельзя описать короче, чем выписать целиком

Через тридцать два года после своих аксиом Колмогоров возвращается к вопросу, который они обошли: что такое случайный объект? Ответ: сложность слова — это длина самой короткой программы, которая его печатает. Миллион нулей печатается коротким циклом; у случайного слова короткой программы нет, его придётся выписать целиком. Случайность перестаёт быть свойством мира и становится свойством описания — и её теперь можно мерить в битах. Годом раньше к тому же понятию независимо пришёл Рэй Соломонов, искавший формализацию индукции.
17

Стокгольм статья — 1966; работа у Колмогорова в Москве — 1964–1965
Мартин-Лёф: случайно — значит проходит все проверки
Тот же класс с другой стороны: случайно то, что проходит все эффективные проверки

Швед, приехавший учиться к Колмогорову, доводит определение до конца с другой стороны. Всякая проверка на случайность указывает множество меры нуль — последовательности, подозрительные по какому-то признаку. Проверок бесконечно много, но эффективных, тех, что выполнит машина, — счётное число, и их можно свести в одну, самую сильную. Случайно то, что эту проверку проходит. Позже выяснилось, что получается ровно тот же класс, что и через сложность, — если сложность считать в самоограниченном виде.
18

Йорктаун-Хайтс теорема о неполноте — 1974, число Ω — 1975
Чейтин: число, которое нельзя вычислить
Цена определения: почти всё случайно — и почти ни про что этого не доказать

Чейтин строит число Ω — вероятность того, что наугад набранная программа когда-нибудь остановится. Его двоичная запись случайна в самом сильном смысле: ни один кусок не ужимается. Отсюда следствие, стоящее рядом с гёделевым: у всякой формальной системы есть собственный предел сложности, и утверждение «сложность этого слова больше такой-то» она доказать не может. Почти всякое слово случайно — и почти ни про одно этого нельзя доказать.
19

Беркли Миллер — 1976, Соловей и Штрассен — 1977, Рабин — 1980
Соловей и Штрассен: монетка вместо доказательства
Случайность из предмета изучения становится ресурсом: монетка вместо доказательства

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

Беркли доклады — 1982, журнальные версии — 1984
Блюм, Микали и Яо: подделка, которую не отличить
Третье определение: случайно то, что не отличить от случайного — свойство наблюдателя

Настоящей случайности у машины нет: фон Нейман ещё на исходе сороковых назвал состоянием греха попытку получать случайные цифры арифметикой. Ответ, найденный в Беркли: настоящая и не нужна. Достаточно, чтобы короткое случайное зерно разворачивалось в длинную последовательность, которую никакая быстрая программа не отличит от честной монетки, — а это возможно, если существуют задачи, которые легко задать и трудно решить. Случайность впервые определена не через мир и не через описание, а через того, кто смотрит.
21

Иерусалим Нисан и Вигдерсон — 1988, Импальяццо и Вигдерсон — 1997
Импальяццо и Вигдерсон: а нужна ли она вообще
И, возможно, вычислителю она не нужна вовсе: монетку удаётся подделать до конца

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

Женева статья — 1964, опыты — 1982 и 2015, Нобелевская премия — 2022
Белл: неравенство, которое можно проверить
Развязка исходного вопроса: демона, знающего положения и скорости, проверили опытом

Спор Эйнштейна и Бора о том, стоят ли за квантовой случайностью скрытые причины, считался философским, пока сотрудник ЦЕРНа не превратил его в арифметику. Белл выписывает неравенство для корреляций двух разлетевшихся частиц: если исходы предопределены заранее, а сигнал не обгоняет свет, некая комбинация не может превысить двойки. Квантовая механика обещает почти тройку. Опыты Аспе, а затем безлазеечные опыты 2015 года дали квантовый ответ; в 2022-м за это присуждена Нобелевская премия. Демон, знающий положения и скорости, больше не спасает.