Книга: Золотой билет

Андрей Николаевич Колмогоров

Андрей Николаевич Колмогоров

Андрей Колмогоров родился в 1903 году в Тамбове. В 1920 году он поступил в Московский университет, где поначалу интересовался не только математикой, но и пробовал свои силы и в истории, занимаясь изучением налогообложения на Руси в Средние века. Вопрос в его работе ставился такой: назначался ли налог сразу целому селению или же складывался из налогов, назначенных отдельных дворам? Проанализировав старинные налоговые записи, Колмогоров показал: расшифровать эти записи и объяснить правило, по которому они составлялись, будет гораздо проще в предположении, что налог назначался селению. На историческом отделении работу студента оценили очень высоко. Однако в ответ на вопрос, следует ли ему опубликовать полученные результаты, Колмогоров услышал: «У вашей гипотезы есть лишь одно обоснование. А для публикации требуется как минимум два», что в конечном итоге заставило его отвернуться от истории и посвятить себя науке, в которой одного доказательства было вполне достаточно. Колмогоров внес неоценимый вклад в самые разные области математики; это величайший математик XX века и один из крупнейших ученых в истории всей российской и мировой науки.

Существует забавная история – анекдот, по всей видимости, – о том, как Колмогоров спас теорию вероятностей от сталинского режима.

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

Разобравшись с генетикой, «светочи науки» ополчились на теорию вероятностей за понятие независимых событий. Теория вероятностей занимается изучением шансов на тот или иной исход; к примеру, если одновременно бросить две игральные кости, то вероятность того, что в сумме выпадет пять очков, равняется одной девятой. Через понятие вероятности определяются и независимые события. Например, при подкидывании двух игральных костей число выпавших очков на одной никак не зависит от числа выпавших очков на другой. Все это плохо согласовывалось с марксистской философией, согласно которой все кругом взаимосвязано и взаимообусловлено.

Колмогорова вызвали наверх и упрекнули в том, что независимые события идут вразрез с идеями марксизма.

Ученый понимал, насколько важно подобрать верные слова: от того, что он скажет, зависит будущее советской математики. «Вы ошибаетесь», – начал он, и его собеседники тут же решили: «Попался!» Ведь критиковать линию партии – все равно что подрывать основы марксистского учения, и для Колмогорова это означало конец карьеры.

«Допустим, поп во время засухи молится о ниспослании дождя, – продолжал ученый. – На следующий день начинается дождь. Эти два события совершенно независимы». Что тут можно было возразить? Допустить даже самую отдаленную связь значило признать действенность религии, что было равносильно попытке дискредитировать учение Маркса. Так Колмогоров спас теорию вероятностей.

Рис. 5.3. Комикс про Дилберта. © Скотт Адамс, 2001. Публикуется с разрешения UNIVERSAL UCLICK. Все права защищены

Стремление проникнуть в суть вероятности и случайности привело Колмогорова к одной удивительно простой и в то же время гениальной идее. Рассмотрим три последовательности цифр:

• 999 999 999 999 999 999 999 999 999 999 999 999 999 999 999 999 999;

707 106 781 186 547 524 400 844 362 104 849 039 284 835 937 688 474;

982 922 216 207 267 591 232 795 977 564 268 549 473 337 889 037 097.

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

Выдавать одни девятки для генератора случайных чисел не очень-то естественно. Вторая последовательность, – как некоторые уже, наверно, догадались, – это начало дробной части квадратного корня из 1/2. А вот третья действительно была создана генератором.

Колмогоров придумал определять степень случайности последовательности в зависимости от длины ее самого короткого описания. Первая последовательность – это «51 девятка». Вторая – «1/?2». Описать третью можно, только повторив ее целиком: «982 922 216 207 267 591 232 795 977 564 268 549 473 337 889 037 097». Конечно, «описание» – понятие неформальное; Колмогоров формализовал его через понятие компьютерной программы.

Аналогичные идеи независимо друг от друга и от Колмогорова разработали также двое американских ученых: Рэй Соломонов (из Кливленда, а не из СССР, как можно было бы подумать по его фамилии) – чуть раньше Колмогорова, Грегори Хайтин – чуть позже. Однако Колмогоров и его последователи углубились в эту тему гораздо дальше, так что сложность, определяемую через длину описания, стали называть «колмогоровской».

Последовательность называется случайной, если самый короткий способ описать ее – это привести ее целиком, как в случае с нашим третьим примером.

Создать случайную последовательность нетрудно: просто выбирай каждое следующее число случайным образом – и все. Однако без случайных величин последовательность никогда не станет по-настоящему случайной. Алгоритм, не являющийся вероятностным, т. е. не использующий случайные числа, не способен строить случайные последовательности произвольной длины. Поэтому не стану утверждать, что последовательность

982 922 216 207 267 591 232 795 977 564 268 549 473 337 889 037 097

действительно является случайной: чтобы доказать это, мне пришлось бы проанализировать все возможные описания меньшей длины, а эта задача явно не из легких!

За понятием колмогоровской сложности стоит обширная и глубокая теория, которая находит применение в машинном обучении, анализе алгоритмов и в сложности вычислений. Именно колмогоровская сложность привела Леонида Левина – ученика Колмогорова – к проблеме равенства P и NP, хоть она и не связана с этой проблемой напрямую.

Оглавление книги