Золотой билет - Лэнс Фотноу

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

Андрей Колмогоров родился в 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, хоть она и не связана с этой проблемой напрямую.

Леонид Анатольевич Левин

В 2800 километрах к востоку от Москвы находится Новосибирск – самый крупный город в Сибири и третий по численности во всей России. В 1961 году из Москвы в Новосибирск приехал Алексей Андреевич Ляпунов и вскоре основал в Новосибирском университете кафедру теоретической кибернетики.

Первыми сотрудниками стали преимущественно бывшие московские студенты Яблонского и самого Ляпунова. Новая кафедра быстро приобрела статус центра кибернетических исследований – второго по значимости в Советском Союзе. Почти сразу к исследовательскому коллективу присоединился Борис Трахтенброт, который также занимался кибернетикой и на тот момент – в сорок с небольшим лет – уже был доктором наук; вскоре Трахтенброт стал одним из ведущих сотрудников кафедры. В 1962 году в Новосибирск приехал Ян Мартынович Барздинь, незадолго до того защитивший кандидатскую в Латвийском государственном университете в Риге. Трахтенброт и Барздинь начали совместные исследования в области сложности вычислений и привлекли к работе множество российских и латышских студентов. В середине шестидесятых ученые уже вовсю разрабатывали теорию алгоритмической сложности – аналогичную той, что в то же самое время создавалась на Западе.

Впрочем, в СССР с вычислительной сложностью все было довольно сложно. В 1984 году Трахтенброт напишет:

«Напряженность в отношениях с представителями так называемой классической школы – и в особенности с Яблонским – нас очень угнетала. Эти люди занимали крайне негативную позицию касательно применения теории алгоритмов к вопросам сложности <…> Они не допускали и мысли о том, что вычислительную и алгоритмическую сложность можно связать с проблемой перебора. Яблонский к тому времени играл уже далеко не последнюю роль в различных организациях, занимавшихся планированием и контролем математических исследований; в дальнейшем наше противостояние только усилилось – по всей видимости, из-за разногласий по поводу необходимости перебора»[4].

Летом 1963 года в Новосибирск приехал Колмогоров и начал совместные исследования с Трахтенбротом. Ученые пытались понять, каким образом теория алгоритмов может помочь им продвинуться в изучении сложности и информации.

Из Новосибирска Колмогоров вскоре отправился в Киев, где посетил физико-математическую школу-интернат при Киевском университете. Ученый предложил школьникам несколько задач; пятнадцатилетний Леонид Левин справился почти со всеми. Позже Колмогоров пригласил его в Московский университет и взял под свое руководство. Во время учебы в аспирантуре Левин разрабатывал сразу два разных направления.