Золотой билет - Страница 29

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

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

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

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

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

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

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

• 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 году в Новосибирск приехал Ян Мартынович Барздинь, незадолго до того защитивший кандидатскую в Латвийском государственном университете в Риге. Трахтенброт и Барздинь начали совместные исследования в области сложности вычислений и привлекли к работе множество российских и латышских студентов. В середине шестидесятых ученые уже вовсю разрабатывали теорию алгоритмической сложности – аналогичную той, что в то же самое время создавалась на Западе.