Интервью с Леонидом Левиным

о Колмогорове, колмогоровской сложности и др.



A. В 1963-64 году я учился в девятом классе в киевском интернате, и нам читали курс логики. Он мне очень нравился, но меня смущало, что эта логика такая чёрно-белая. Она интересуется, верно утверждение или нет, но ведь огромное множество утверждений, верны, но скучны, противоестественны, никому не интересны. И наоборот есть утверждения, которые может быть даже неверны, как например парадоксы, но интересны, и люди будут их обсуждать.

Я искал способ это как-то выразить, хотел ввести такое понятие ``неестественности'' натурального числа или строчки. Я это определял как самый короткий арифметический предикат, который для этого и только для этого числа доказуем. Я понимал, что в одной формулировке это может быть одно, а в другой -- другое. Я мечтал доказать, что эта зависимость ограничена константным множетелем, но конечно не мог: мне было 15 лет.

Потом я перешёл в московский интернат, и рассказал это Сосинскому. Он спросил Колмогорова, и тот сказал -- ну конечно, вот сейчас выходит моя статья, где как раз это доказано. Более того он доказал это с точностью даже не до мультипликативной, а до аддитивной константы.

Я был поражён. Я вообще-то понимал, что академики гораздо больше знают чем я, но тут оказывается, что они не только больше знают, но что они-таки умнее, чем я --- некоторые из них. Я был страшно заинтригован и хотел стать учеником Колмогорова.

Q. Это шестьдесят какой год?

A. Я перешёл в московский интернат в 1964, значит Колмогоров тогда это уже знал и можно предположить, что он это знал существенно раньше, потому что вряд ли было такое точное совпадение. Но с другой стороны посылая статью в Sankhya, он, похоже, этого ещё не знал.

Q. Там есть смутное примечание, что вот можно было бы основываться ... что в принципе возможен другой подход, при котором ...

A. Crucial в этом не само понятие, про кодировки знал ещё Шеннон. Crucial здесь теорема об оптимальности, что оно инвариантно. Посылая статью в Sankhya Колмогоров этого ещё мог не знать. Потом я поступил в университет и он читал спецкурс по сложности, ужасно увлекательный.

Q. И там уже была случайность по Мартин-Лёфу?

A. По-моему, да. И зимой 1966/67 на втором курсе, я уехал на каникулы и решил, что мне обязательно нужно что-то доказать, чтобы он меня взял в ученики. И я доказал тогда коммутативность информации и её монотонность, и какие-то там ещё вещи. Вернувшись, я позвонил Колмогорову и сказал: вот я доказал какие-то теоремы, хочу Вам рассказать. Он говорит: конечно, конечно, позвоните мне через две недели. Ну я через две недели позвонил, он говорит ну вы знаете, я сейчас вот очень занят в этом месяце, позвоните мне в следующем, и так это длилось где-то до августа.

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

И дальше он сказал интересную вещь про которую я не уверен что ему всегда её credit. Там доказательство было такое, что даже если алгоритмы работают быстро в одну сторону коммутативности, чтобы доказывать что сложность маленькая в другую сторону, надо эти быстрые алгоритмы обращать, находить, быстро или нет, короткую программу.

Он сказал что про такие задачи перебора есть очень важная проблема, можно ли всегда элиминировать перебор или бывают случаи, когда нельзя. И этот случай не слишком общий и не слишком специальный, выглядит обещающе чтобы попытаться доказать что перебор невозможно элиминировать. Слишком общий случай может быть неподходящим, слишком специальнуй тоже, а это как раз где-то посередине, что очень привлекательно. Мой интерес к этому был в общем-то им спровоцирован. Я после этого довольно быстро доказал что есть универсальная задача tiling.

Q. Это какой год? 1968 уже?

A. Нет, это 1967 год ...

Q. Спецкурс был 1966/67 год?

A. Я не помню в точности, мне кажется, это был именно его спецкурс, но возможно это были какие-то его лекции. Я доказал эту коммутативность на Украине на зимних каникулах второго курса, то есть это был январь или февраль 1967, а беседа эта с Колмогоровым была в августе 1967 года. Он вполне возможно мог иметь такого же типа идеи и раньше, по другим поводам: он с Яблонским много на эти темы ругался. Но мой интерес был вызван именно этим его замечанием я тогда быстро доказал, что есть tiling, я называл её задачей Дирихле, которая будет трудно разрешима, если какая-нибудь задача трудно разрешима. Тогда же я нашёл оптимальный решающий алгоритм. Колмогорову tiling результат очень нравился а мне нет; оптимальный алгоритм мне наоборот казался интересным, но к нему как раз Колмогоров относился скептически.

Q. А к этому моменту Мартин-Лёф уже уехал?

A. Мартин-Лёфа я в тот период никогда не видел, когда он был в Москве, учился у Колмогорова и этим всем занимался. Я его первый раз увидел уже после того как он уехал из Москвы и потом то ли он вернулся то ли я его ещё где-то видел, не помню уже.

На следующий год я уже захотел сам вести семинар. Я был третьекурсником но сказал что хочу вести семинар по сложности. (Раз Колмогоров не ведёт, другого столь же умного человека на свете нет :-). Я пришёл к Успенскому, тот несколько опешил, но сказал, что если я уговорю какого-то аспиранта чтоб он вместе со мной числился руководителем и чтобы в зачётках расписывался именно он а не я, то это можно. Я уговорил Душского и мы с ним вели этот семинар. Звонкин был активным участником, Толик Колодий, Мишин, Петри, Канович, там было много людей.

Q. (Вьюгину) а Вы там тоже были?

A. Нет, Вьюгин не ходил

В. Я вообще не знал.

A. Звонкин вёл записи, но, потом они вроде были утеряны. Некоторые вопросы мы ставили прямо на семинаре; вот я поставил такую задачу: доказать, что если у последовательности ограничена константой условная сложность кусков при известной длине то она разрешима. Потом я доказал что это так. Я сказал Колодию и Мишину и они ответили, что тоже знают, уже это доказали. Я не спрашивал у них подробности, но мы со Звонкиным потом включили это как совместный с ними резултат в наш обзор.

Q. А разбиралось ли там про случайность?

A. Там всё разбиралось, подробно, -- всё что было известно к тому времени. Звонкин говорит что потерял эти записи но может быть он где-то может их ещё найти. Он вёл очень подробные записи.

Q. Звонкин характерен этим ...

A. Я вёл этот семинар только один год. Душский ходил но особенного участия не принимал. На 4 и 5 курсе никаких семинаров не было.

Как-то Сосинский сказал, что Колмогоров хочет, чтобы какие-нибудь люди, которые этим занимаются, написали обзорную статью по сложности. ``Ну это Колмогоров конечно не имел в виду Левина, а там всякие другие люди чтобы написали.'' Я обиделся, считал что это Сосинский ко мне относится настороженно и хочет меня исключить. Я это замечание проигнорировал и предложил Звонкину и Колодию писать вместе статью. Они согласились и мы собирались какое-то время и очень долго обсуждали как начать. Потом Колодий сказал, что он больше не хочет этим заниматься и отклеился. Мы со Звонкиным потом писали эту статью очень долго.

Q. Но надо полагать, текст писал Звонкин? Непосредственно каждую букву?

A. Конечно решающую роль играл Звонкин но мы каждую фразу обсуждали вместе.

Q. Представляю себе ...

A. У нас были большие споры, скажем нужно ли здесь писать слово ``следовательно'' или уже это слишком много философии ... Потом, закончив МГУ, я остался ещё на один год и мы устроили семинар. . Q. Это какой год уже?

A. Это был 1970/71. У семинара было три руководителя: Колмогоров, Петри и я; потом Колмогоров уехал.

Q. На корабле?

A. Да. Потом он вернулся, а у меня начались неприятности и по-моему больше таких семинаров в те времена не было.

Q. А диссертация была когда написана? в 1971 году?

A. Я более или менее взял выдержки моих резултатов из нашей статьи со Звонкиным, и на этой основе написал диссертацию, да в 1971.

Q. Но в диссертации было определение префиксной сложности тоже, которого нет в Звонкине?

A. Да,

Q. А текст её существует?

A. У меня есть, в Бостоне.

(Вьюгин приносит сохранившийся текст диссертации.)

В.В. Тут даже отзыв Колмогорова.

A. Это не для диссертации когда мне писали для диссертации, партком настоял чтобы написали что я участия в общественной жизни не принимал.

В.В. это чтобы тебя взяли на работу - ты сам говорил - в какое-то место.

Q. Ну конечно --- общественная работа, в Смоленской области, грамота Смоленского обкома комсомола.

A. Потом ему запретили писать, что я принимал участие в общественной работе, более того, велели писать, что не принимал.

Q. Принимал негативное участие ... А почему тут чего-то такое исправлено? Не окончательный вариант?

A. Не могу сказать, окончательный ли.

Q. А вот то что у тебя хранится в Бостоне

A. У меня окончательный вариант, тот, который был послан официально

Q. А как это попало

В.В. По-моему, это чуть ли не Альберт Абрамович передал

A. То есть это может быть одна из четырёх копий.

Q. Тогда это такая редкая возможность, надо это присоединить к имеющимся архивам, у меня уже хранится спасённая мной из помойного ведра рукопись статьи Колмогорова 1970 года, её готовили как раз в 80-каком-то году готовили к публикации в УМН. Её перепечатали, Колмогоров видимо её читал просматривал, кто-то сверял --- работа какая-то техническая --- после чего (я дежурил у Колмогорова) её прямо выбросили в помойное ведро и я решил что нет, всё-таки лучше я совершу сомнительное действие и достал её из помойного ведра и спрятал и у меня теперь имеется автограф Колмогорова, немного посявканный, но совершенно аутентичный.

A. Ну мой автограф это может быть не в точности то же самое

Q. Не в точности, но всё равно и зато он гораздо чище и больше

A. Немного людей полезли бы в мусорное ведро за моим автографом

Q. А ты можешь это просканировать в Бостоне.

A. Могу просканировать свою и прислать тебе, у меня сейчас есть принтер, который по идее должен уметь сканировать.

Q. А почему в статье есть априорная вероятность на дереве, а на натуральных числах нету? просто к тому моменту это ещё не пришло в голову, или почему-то считалось, что дерево правильнее и другое просто не вошло в статью.

A. Я сделал [В ДАН-73 -ЛЛ] на последовательностях натуральных числах а не на двоичном дереве чтобы натуральные числа были просто частным случаем.

Q. Но в статье Звонкина Левина там двоичные последовательности.

A. Там двоичные, но там есть и примечание что можно определять сложность натурального числа кодируя его двоично как 0...01. Но в статье в докладах я хотел чтобы было одно понятие а другие получались тривиальными частными случаями без специальной оговорки.

Q. Но вот то, что префиксная сложность натуральных чисел, определённая с помощью кодирования, и логарифм априорной вероятности это одно и то же, это где впервые появилось?

A. Теорема о том, что они равны была позже, в 1974.

Q. То есть я подозреваю напечатана она была впервые в статье Гача ``О симметрии информации''.

A. В Проблемах передачи информации в 1974. Гач тоже 1974. Он ссылается на меня так что это не не имеет приоритетного значения. Резултаты статей 1973 года я на самом деле сделал зимой 1970/71 но долго не публиковал, пока у меня в апреле 1972 не начались серъёзные неприятности. Кто-то сказал, ты Левин человек сумасшедший; по крайней мере пока тебе разрешают ещё печатать статьи возьми всё опубликуй. Тогда я представил сразу несколько статей.

Q. А вот защита состоялась в Новосибирске, но голосование было отрицательным, а председателем совета был [Юрий] Ершов?

A. Нет Соболев, и Колмогоров говорил, что он ему выражал возмущение.

Q. Кто был возмущён и чем?

A. Соболев.

Q. Тем фактом, что таких отщепенцев допустили или что их потом провалили?

A. Что провалили.

Q. А что же председатель Совета возмущается своим собственным Советом?

A. Там peculiar вещь --- в протоколе отражено что в голосовании принимало участие в полтора раза больше людей, чем присутствовало. Ершов пришёл и вложил пачку бюллетеней отсутствующих.

В.В. Он там ещё выступил.

A. Ещё и выступил. Я Ершова не виню совершенно в том, что меня провалили это ему велели и он не мог ослушаться. В чём я его виню, это то что он сделал исключительно по своей инициативе. Тогда был короткий период, когда Учёный совет должен быть принимать мотивацию отрицательного решения и он туда включил фразу о том, что ``неясен его политический облик.'' Эта фраза мне нанесла гораздо больше вреда чем провал диссертации. Ну написал я плохую диссертацию, в следующем году могу написать хорошую и защитить в другом месте.

В.В. А кто эту фразу включил?

A. Ершов.

В.В. Ершов? Ты по-моему рассказывал что он выступил и сказал что непонятно где твои достижения потому что вроде как бы это и Колмогоров доказал.

A. Да он сказал, конечно есть замечательные результаты Колмогорова, не надо думать что у всех тут одинаковые заслуги. Но это мне большого вреда не принесло. А фраза о неясном политическом облике закрывала все пути.

Q. Неясен?

A. Неясен - может быть, такой же хороший как у Брежнева а может быть только как у Косыгина и где именно в этих пределах, им неясно :-). Но всем остальным было ясно, и это лишило меня возможности более или менее навсегда защитить диссертацию пока я не докажу что у меня исправился облик чего я сделать не мог. В общем-то это вынудило меня эмигрировать и я наверно должен перечислять ему 10 процентов своей зарплаты. Я уверен, что эту фразу никто его не заставлял включать. КГБ она бесполезна: преследовать меня они могли без какой-либо фразы в этом постановлении. Это он просто по своему характеру. Вот за что я его считаю скотиной, не за провал а за инициативу которую он не обязан был проявлять.

Q. Политическую сознательность, выходящую за рамки

A. Как говорят, above and beyond the call of duty.

------------

Q. С точки зрения определения случайности есть некоторая история - что был Мизес, потом Мизеса критиковал Вилль, который ввёл понятие мартингала, потом было неравенство, которое иногда называется неравенством Дуба, иногда неравенством Колмогорова, я не знаю, как правильно оно называется, в общем, неравенство, что мера тех случаев, когда мартингал достигает C, не больше 1/C.

A. Я в таких тривиальностях не умею различать ...

Q. И потом был Шнорр, который заинтересовался этим, написал целую книжку Zufalligkeit ...

A. Универсальная мера, делённая на claimed probability, это то же самое, что мартингал, полумартингал или как это называется.

Q. Супермартингал.

В.В. Супермартингал может быть это даже лучше.

A. Нет хуже. Универсальная мера инвариантна, для всех распределений одна и та же, а мартингал для каждого разный.

В.В. А ты знал тогда что такое мартингал как это всё используется.

A. Не могу сказать ... Вряд ли я много знал про теорию мартингалов, но это отношение унижерсальной меры к вероятности я знал. Я говорил Колмогорову что вот мне не нравится понятие дефекта случайности потому что Мартин-Лёф определяет его отдельно для каждой меры. А я хочу ввести одно понятие, такую монотонную сложность или универсальную меру, которая для всех распределений одна, и просто брать разницу между логарифмом вероятности и этой сложностью которая всегда будет дефектом случайности выраженным через величину не зависящую от распределения.

Q. Но вот там просто идея такая, что неслучайность последовательности означает, что какой-то мартингал на ней бесконечно выигрывает --- у Колмогорова, для него это была --- он когда-нибудь упоминал такую мотивацию? или он это не связывал?

A. Колмогоров вообще, по-моему, не знал никакого [перечислимого -ЛЛ] определения случайности, кроме аксиоматического определения Мартин-Лёфа потерявшего связь с колмогоровской сложностью. Колмогоров определил случайность как длина минус сложность; Мартин-Лёф увидел, что это неприменимо к неравномерным распределениям, а на бесконечных последовательностях равномерного распределения не бывает. Потому такого красивого определения как разница между чем-то вычислимым по мере и чем-то инвариантным, как сложность, он не придумал. Он определил для каждой меры дефект случайности как максимальную функцию удовлетворяющую некоторым аксиомам.

Q. Сейчас, но всё-таки Колмогоров в статье в Sankhya шестьдесят второго года он как бы рассматривал, обобщал определения Мизеса --- Чёрча.

A. Это не настоящее определение.

Q. Ну да не настоящее но тем не менее следующим шагом который Шнорр сделал пытаться рассмотреть не выбор подпоследовательности, а именно эти самые мартингалы --- Колмогоров в таких терминах никогда не говорил? не упоминал этого?

A. Я не понимаю разницы между супермартингалом и универсальной мерой, кроме недостатка мартингалов - зависимости от распределения. Поэтому я не очень понимаю сказанного в такой форме, но я от Колмогоров не слыхал никакого другого определения сложности, которая даёт сходимость не только для конечных последовательностей определённой длины, или другого чем у Мартин-Лёфа подхода к бесконечным последовательностям.

Q. А были ли какие-то контакты с Шнорром? Читал ли кто-либо эту книгу Шнорра? или наоборот, интересовался ли Шнорр Колмогоровским, была ли какая-то связь? В какой-то момент Питер [Гач] поехал к Шнорру в аспирантуру?

A. Это уже было всё существенно позже.

Q. 1979? 1978? То есть до этого Шнорр был совершенно независим и никто про него не знал?

A. Мы сослались на абсолютно всё о чём знали. Где тут моя библиография? Вот здесь статья Шнорра. Я её не читал, конечно, и про неё ничего не знал но сослался.

Q. Препринт 1970 года какой-то.

A. Видимо Колмогоров эту работу Шнорра знал, он по-немецки читал. (Он, по-моему, не очень хорошо понимал по-английски.) В этой статье этих мартингалов по-моему ещё не было. Я не знаю, ты можешь посмотреть.

В.В. Может быть, у меня есть какой-то препринт Шнорра.

Q. А откуда?

В.В. Мне Мучник когда-то передал Альберт Абрамыч много лет назад.

A. Во всяком случае если ты спрашиваешь про Колмогорова, то я думаю, он этот препринт знал, но я не думаю, что он знал какое-либо определение случайности, кроме Мартин-Лёфовского аксиоматического.

Q. Нет ну потом уже позже он видимо про эту самою монотонную сложность.

A. Ну да, позже он уже всё это знал конечно.

Q. А там -- с самого начала по-видимому Колмогоров этим интересовался, поскольку он настойчиво пишет про это в своих статьях, -- про эти самые бернуллиевы последовательности.

A. У Колмогорова было понятие конечной бернуллиевой последовательности, до Мартин-Лёфа. Оно выражало понятие независимых испытаний вне связи с тем, по какому именно параметру p определяется вероятность. Мартин-Лёф затем дал аксиоматическое определение для этого класса мер на бесконечных последовательностях. Это был именно специальный класс, там не было никакого обобщения. Случайность по равномерной мере Мартин-Лёф обобщил на все распределения вероятностей; бернуллиевость была только для этого специального класса мер и это определение стояло как-то отдельно. Мартин-Лёф определял бернуллиевость, но для последовательности фиксированной длинны, идея восходила к Колмогорову.

Q. Что она максимальной сложности.

A. При данном количестве нулей и единиц. А Мартин-Лёф обобщил это на бесконечные бернуллиевские. Я обобщил это на любой компактный класс мер в статье 1973 года.

Q. Которая ``Равномерные тесты случайности''?

A. Нет, до равномерных тестов случайности. Я там использовал определение, от которого потом отказался.

Q. Это где статья?

A. В Докладах есть статья, ``О понятии случайной последовательности'', где вводилась монотонная сложность. Там в конце я доказал что всякое конструктивно компактное множество мер имеет общий для всех этих мер универсальный тест, такой что выдерживающая его последовательность, всегда случайна по какой-то конкретной из этих мер. Это значит она выдерживает любой тест для этой меры, которому даже позволяется читать эту меру. Он всё равно не может никак выделить эту последовательность, она будет случайна в таком очень сильном смысле. Но это дурацкое - слишком сильное - определение случайности. Теорему это только усиливает, но для определение случайности, разрешать тестам зависеть от далёких знаков меры странно. Я это определение потом не использовал.

Q. А вот ещё. Кстати, я так как-то не знаю, есть ли какой-то критерий бернуллиевости в терминах бернуллиевости сложности начальных отрезков? я спрашивал у Гача, можно ли доказать, что последовательность бернуллиева, когда какая-нибудь скажем префиксная сложность начальных отрезков больше или равна чего-то, он сказал, что какой-то критерий есть, но по его мнению неудовлетворительный и я так и не успел его расспросить какой.

A. Некоторый straightforward критерий можно взять из этой теоремы что бернуллиевость означает что есть какая-то определённая частота p, такая что последовательность выдерживает любой тест при этой частоте.

В.В. Бесконечная?

A. Да.

Q. Но там получится всё-таки сложность с оракулом. А просто что-то такого типа: последовательность бернуллиевская тогда и только тогда, когда начальный отрезок длины n имеет префиксную сложность, близкую к максимуму, большую, чем логарифм Cnk.

A. Я ничего такого не помню.

В.В. Это и неверно.

A. Но для сложности с оракулом p, то это в точности будет верно.

В.В. Дело в том, что колмогоровское определение бернуллиевости это не случайность относительно бернуллиевских мер, колмогоровское определение бернуллиевости это случайность относительно класса exchangeable мер, которые очень близки к бернуллиевским но не совсем.

A. Что такое exchangeable?

В.В. Это которые инвариантны относительно перестановки её значение инвариантно относительно перестановки но это уже Вовк доказывал.

Q. А где это написано у Колмогорова?

A. У Колмогорова это нигде не написано

Q. А в каком смысле тогда это колмогоровское? Он как-то это говорил?

В.В. Нет, он этого я думаю даже не знал.

Q. Тогда я не понял утверждения --- Вы вроде говорите, что на самом деле Колмогоров определял бернуллиевские последовательности как exchangeable ...

В.В. Он определял их через сложность, но на самом деле это эквивалентно определению относительно класса exchangeable мер.

Q. И где это написано?

В.В. Ну это у меня в статье написано

Q. Ну да, только ничего понять нельзя

В.В. Можно если прочитать.

Q. В силу ложности ...

В.В. Это первый Вовк, у него есть заметка такая в Успехах математических наук, это была его дипломная работа.

A. Саша ты должен понять такую вещь --- понятие меры, по которой последовательность случайна, неоднозначно. Можно ввести меры, которые не бернуллиевские, но если последовательность случайна по ним, то она будет случайна по какой-то бернуллиевской мере. Например, возьми такую меру, напиши ноль и один, а потом каждый следующий знак пиши с вероятностью, равную частоте предыдущих. Это конечно не бернуллиевская мера. Она одна, но последовательность случайна по ней тогда и только тогда, когда существует такое число p, которое само по себе случайно по Мартин-Лёфу, и она бернуллиевская с этим p.

Q. То есть это более узкий класс последовательностей, чем бернуллиевские, потому что ещё требуется чтобы p было случайно ...

A. Да, но Володя говорит, что есть более широкий класс мер. И конечно, например эта мера не бернуллиевская а последовательность по ней случайна. Но это просто потому, что мера, по которой последовательность случайна, не определена однозначно: одна и та же последовательность может быть случайна по многим, даже взаимно ортогональным, мерам.

Q. Теперь ещё последнее, что я хочу спросить --- когда вообще впервые Колмогоров узнал о Чейтине [Chaitin]? он в некоторый момент пишет, называя его, правда, Шайтиным ...

A. История была такая. Когда мы отдали свою статью Колмогорову,

Q. Какую? Звонкин и Левин?

A. Да. Про Чейтина он по-моему в последний момент нам сказал его вставить. Он ещё дал статью Соломонова и сказал что нужно сослаться, у него тоже там есть похожие идеи. Это было для меня большой проблемой я по-английски совершенно не понимал.

Q. Настолько, что не мог списать название статьи Соломонова в библиографию?

A. Нет, списать мог, но я должен быть прочитать.

Q. Но о Шнорре почему-то не было такого вопроса даже, чтобы прочесть по-немецки.

A. Про остальных он просто сказал чтобы мы вписали ссылки, а про Соломонова он сказал, что у него-таки есть похожие идеи так что на него надо сослаться в тексте статьи, и я для этого должен был его прочитать.

Q. Но тоже не обязательно ...

A. Он мне сказал, а я еле-еле понимал по-английски, был undergraduate, и должен был читать эту статью. А там всё было неверно, ряды расходились, пределы не существовали, ничего никакого математического смысла не имело. Я не хотел писать никакой гадости, что там всё неправильно но сослаться должен был. Я выбрал обтекаемую форму: написал в abstractе, что у него близкие идеи, но не стал уточнять, какие именно. Остальных Колмогоров уже в последний момент сказал вписать в библиографию.

Q. А вообще насколько Колмогоров влиял на текст этой самой статьи?

A. Он очень подробно её всю прочитал сделал массу комментариев, у меня даже какие-то странички сохранились, а какие-то забрал Звонкин. В частности про какую-то мою теорему Колмогоров написал, теорема такая-то действительно интересна, но употребление одновременно двух эпитетов ``глубокая'' и ``нетривиальная'' лучше предоставить читателю. (Все смеются.)

В.В. ``Следующий глубокий нетривиальный результат был получен Левиным''.

Q. Да, изящно выразился Андрей Николаевич, надо отдать должное.

A. Я имел в виду что теорема казалось бы должна быть тривиальной (это по-моему как раз теорема о том, что если сложность отрезков при известной длине ограничена константой, то последовательность рекурсивна) но оказалась не такой, и доказательство гораздо более involved, чем можно было ожидать.

Q. А вот формула о том, что дефект бесконечной последовательности равен сумме отношений априорной вероятности к ...

A. Это уже в более поздней статье. На самом деле сразу, как только мы опубликовали статью со Звонкиным, я написал Колмогорову письмо перед тем как он уехал в своё плаванье. Я написал что если Вы на корабле будете этим заниматься, Вам может быть там будет интересны такие-то и такие-то вещи, в частности что последовательность случайна тогда и только тогда, когда монотонная сложность её префиксов совпадает.

Q. Даже не монотонная сложность, а такая численная формула что дефект случайности последовательности равен сумме по всем её начальным отрезкам отношения префиксной априорной (меры к) вероятности причём даже не на дереве, а как на натуральных числах. Это то, что я слышал в пересказе Володи который в свою очередь читал это в пересказе Гача но непонятно уже чего. Какова история вот этого? Володя, откуда это взял Гач?

В.В. Не знаю ... сам придумал.

A. В моей статье я определил понятие дополнительного теста. Это такая функция, что если её вычесть из логарифма вероятности, то она будет тестом. Я доказал, что среди дополнительных тестов есть максимальный, и это логарифм универсальной меры.

Q. Но здесь везде всё-таки мера на дереве, а в формуле из Гача там имеется префиксная то есть априорная мера, но именно на начальных отрезках как натуральных числах.

A. Это наверно результаты Гача, если рассматривается сложность

Q. начальных отрезков как натуральных чисел.

A. Если она используется для определения случайности бесконечной последовательности, то это наверно результат Гача. Мы со Звонкиным упоминали сложность натуральных чисел просто как замечание.

Q. Я хочу последний вопрос задать а вот формула симметрии информации с точностью до O(1) где появилась ещё в условии сложность --- это было впервые опубликовано видимо в статье Гача?

A. Да, то есть в моей диссертации этого ещё нет.

Q. То есть это ты рассказал Гачу, и он это поместил. А почему ты не сам?

A. Я мало печатал, редко и под давлением. Но на самом деле, тут у Гача очень большой вклад. Он доказал, --- это совершенно гениальное его наблюдение и на нём было всё основано, --- доказал, что сложность пары x и сложность x такая же, как сложность x; доказательство лёгкое, но по-моему замечательный факт, который я в свою очередь использовал.

Q. То есть с этого всё началось.

A. Гач мне это рассказал, а я потом сказал, что да, вот из этого вытекают ещё то-то и то-то ... и на самом деле Гач с этим фактом связал очень трудный результат, что есть такие числа, у которых сложность сложности x при известном x, максимально возможная. То есть, что функция сложности очень невычислима её output, given input имеет максимально возможную сложность. Отсюда вытекало нарушение на логарифм коммутативности информации, даже для префиксной сложности. Но я не использовал префиксную сложность натуральных чисел как механизм для определения дефекта случайности бесконечных последовательностей, то есть если это есть у Гача, то это его результат, не мой. Я использовал сложность натуральных чисел определяя случайность для распределений на натуральных числах, а префиксную сложность на бесконечных последовательностях.

Q. А вообще Колмогоров как-то реагировал? говорил ли он что-нибудь про префиксную и монотонную сложности, он прочёл все эти результаты, но какие-то более философские комментарии к этому не помнишь?

A. Очень философских не помню ... У меня на самом деле тогда было не очень много с ним контактов. Сразу когда я эти результаты --- даже не рассказал, а написал в письме и отдал ему --- он уехал на корабле.

Q. И это как-то осталось повисло.

A. Его долго не было, потом когда он вернулся, он уже сильно интересовался другим. Он меня просил доказать ему, во-первых, что коллективы Мизеса могут иметь маленькую сложность, и я ему это доказал. Он меня ещё просил доказать, что могут быть эти его функции, характеризующие сложность не как число, а как функцию длина программы, нужной, чтобы найти множество маленького размера, содержащее данное число. Я ему доказал, что это может быть любая ступенчатая функция с точностью до логарифма; потом это уже было замечание самого Колмогорова, что из этого вытекает, что вообще любая монотонная функция может быть сложностью с точностью до корня из n. Это его замечание, оно со сложностью не связано, это просто свойство монотонных функций.

Но я тогда же доказал, что все последовательности, у которых эта функция значительно отличается от диагонали, имеют много информации о halting problem и поэтому не встерчаются. Значит это не годится как механизм объяснения почему в некоторых случаях статистика применима в реальности, а в некоторых нет: таких последовательностей в реальности не бывает. Я к этому потерял интерес а Колмогоров по-моему не понял этого аргумента.

Q. И на этом обсуждения в общем более или менее закончились.

A. Да, как-то да... (Пришла жена Вьюгина Лена и обсуждение закончилось.)



http://www.cs.bu.edu/fac/lnd/dvi/diss/ -- на сайте Левина отзывы о диссертации, в том числе отзыв Колмогорова
Интересно. это где-то есть или, так сказать, первая публикация?
Мне казалось, что это было на сайте Левина, но я сейчас не нашёл. Там есть интересные отзывы о диссертации (в том числе Колмогорова, в котором он пишет о важности префиксной сложности и том, что это не развито в диссертации)
http://www.cs.bu.edu/fac/lnd/dvi/diss/
как, оказывается, недалеко живут свидетели и участники героических эпизодов истории науки!

а зачем Колмогоров плавал в океан?
Колмогоров был научным руководителем экспедиции на исследовательском корабле, если я правильно понимаю, там они изучали под его руководством турбулентность или что-то в этом роде (у Колмогорова на эту тему были знаменитые работы - к сожалению, я в этом совсем не понимаю). Кроме того, он вообще любил разные путешествия, так что, думаю, это тоже было мотивом изучать турбулентность не на бумаге, а в природе...
эти его функции (для тех, "кто не в теме" - сейчас это называют "структурные функции Колмогорова"). Все-таки из ответа Левина непонятно, понимал ли он, что утверждение верно в той формулировке, в которой оно приведено в нашей с Витаньи статье. Выражение "ступенчатая функция" в применении к функции натурального аргумента вообще непонятно.

Кстати, а когда состоялось это интервью?

Edited at 2013-04-06 05:58 am (UTC)
(Anonymous)
а где можно прочитать про коммутативность информации?
в статье Звонкина и Левина (первая публикация)

можно посмотреть также в ftp.mccme.ru/users/shen/kolmbook/kolmbook.pdf (учебник по колмогоровской сложности)
На кафедре в шкафу стоит какая-то книжка по Proof theory и там есть глава "Длины доказательств", написанная Пудлаком. В более умелых руках из идей Есенина-Вольпина что-то получилось. У Аввы ответить не могу, потому что он меня забанил (видимо, по "списку плохих людей", потому что я с ним вообще никогда ни о чём не спорил).
Этим занимаются в Петербурге Ицыксон и его коллеги - но я не думаю, что тут есть какая-то преемственность с Есениным-Вольпиным, хотя кто знает.
Самое прекрасное безумие на эту тему вот
http://www.jstor.org/discover/10.2307/2273760?uid=2129&uid=2&uid=70&uid=4&sid=21102206723337
Предлагается теория (некоторая аксиоматика нестандартного анализа), в которой можно практически развивать мат.анализ, при этом каждый конечный фрагмент этой теории имеет конечную модель. Поскольку мы за всю жизнь используем только конечное число аксиом, можно считать, что мы работаем в некоторой конечной модели и нестандартные числа -- это просто достаточно большие обычные.
Здравствуйте Александр!
Приглашаю Вас в педагогическое сообщество predu.