Памяти Андрея Петровича Ершова

[1]

Б. А. Трахтенброт

Начну с  двух цитат из моей статьи [1].

Цитата 1 (с первой страницы). «Главным образом, это история того, как мои интересы переместились от классической (математической) логики и вычислимости к информатике[2], а в особенности — к автоматам и сложности вычислений. В этих воспоминаниях я в основном пытался рассказать о научной, идеологической и человеческой обстановке тех лет (приблизительно 1945—1967)».

Цитата 2 (с предпоследней страницы). «Однако пришло время для новой тематики, подсказанной развитием в области семантики, верификации, лямбда-исчисления и схематологии. Но это уже другая история!»

Эту историю я еще не рассказывал. Она тесно затрагивает также  мои отношения с Андреем Петровичем Ершовым, которые развивались на протяжении тех 20 лет, которые мы прожили в Академгородке. На самом деле она распространяется и на отношения между многими студентами и сотрудниками обеих сторон. Нашему сближению способствовал рост моего интереса к тем вопросам теоретического программирования, которыми занимался Андрей Петрович. Это происходило в контексте академических и политических дебатов, формировавших направление исследований по информатике в СССР. Мне очень помогли позиция Андрея Петровича по этим вопросам и его активное сотрудничество с ведущими зарубежными научными центрами. Ниже я ограничусь лишь обрывочными воспоминаниями на эту тему. С этой целью я начну (раздел «Начало») с нашего знакомства и его краткой предыстории, а продолжу (раздел «Центробежные тенденции») рассказом о некоторых событиях в кибернетическом сообществе. К сожалению, их не обошли стороной разногласия и недружелюбные столкновения интересов. Затем (в разделе «Сближение») я остановлюсь на более подробном описании того благотворного влияния, которое оказали на наши взаимоотношения позиция и деятельность Андрея Петровича.

1. Начало

В 1960 г. я поступил на работу в отдел кибернетики новосибирского Института математики, возглавляемого Сергеем Львовичем Соболевым. Этот отдел был создан по инициативе Алексея Андреевича Ляпунова, который переехал в Академгородок позже — в 1962 г. О своей глубокой привязанности к Алексею Андреевичу и о его влиянии 
(с 1946 г.) на мою математическую карьеру я писал в статье [2]. С начала 50-х г. Алексей Андреевич и Сергей Всеволодович Яблонский[3] с энтузиазмом проводили и поощряли исследования под общей рубрикой «теоретическая кибернетика». В частности, туда входили теория переключательных схем, автоматы, теория программирования и лингвистика. Некоторые из ранних «теоретических кибернетиков», включая меня, начинали с образованием и опытом исследований в области математической логики, вычислимости и даже дескриптивной теории множеств (первоначальной страсти Алексея Андреевича). Информатику мы  воспринимали как разновидность прикладной логики.

Связь с логикой была очевидной и на Всесоюзном математическом конгрессе (Москва, 1956 г.), где теоретическая кибернетика была включена в секцию математической логики. В частности, именно там прозвучал доклад А. П. Ершова, С. С. Камынина и Э. З. Любимского «Автоматизация программирования»[4].

Еще до приезда в Академгородок я узнал от Алексея Андреевича о его студентах по теории программирования (в особенности — о Ершове и Римме Ивановне Подловченко).

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

Когда я приехал в Академгородок, Андрей Петрович уже был там и заведовал лабораторией, занимавшейся очень важными работами по системному программированию. Там же я встретил своих старых коллег и друзей Александра Александровича Зыкова[5] и Алексея Всеволодовича Гладкого[6]; оба они, как и мы с Яблонским, начинали когда-то с занятий математической логикой в аспирантуре у  Петра Сергеевича Новикова.

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

2. Центробежные тенденции

У Алексея Андреевича была идея организовать в Институте математики единый  центр, где были бы собраны воедино все исследования по теоретической кибернетике, включая программирование. Однако ее реализации воспрепятствовали существующие разногласия в определении кибернетики, ее основных направлений и отношения этих направлений к «настоящей» математике.

Отделение Вычислительного центра. Когда в 1964 г. Г. И. Марчук основал Вычислительный центр СО АН, Ершов решил переместить туда из Института математики свою лабораторию. Первоначально Ляпунов казался разочарованным этим решением Андрея Петровича, которое к тому же отражало некоторые разногласия между ними относительно значения языков программирования высокого уровня. Однако они сохранили хорошие отношения и продолжали сотрудничать (см. их совместную работу о формализации понятия программы[7]).

Появление независимого Вычислительного центра во многом способствовало стремительному развитию теории и практики программирования. Андрей Петрович стал лидером программирования в СССР; в конечном счете, он был избран председателем Научного совета по кибернетике при Академии наук.

Дальнейшая перегруппировка. Процесс самоидентификации различных исследовательских групп привел к дальнейшему расщеплению и перегруппировкам среди «кибернетиков», остававшихся в Институте математики. Зыков организовал свой собственный семинар по теории графов, откуда вышла сильная группа исследователей в этой области. Гладкий занялся исследованиями по математической лингвистике —  сначала в отделе алгебры и математической логики, возглавляемом Анатолием Ивановичем Мальцевым. Сам же я продолжал работать в области логики и автоматов. Затем я начал исследования по сложности вычислений, продолжая тесные связи с семинаром «Алгебра и логика». Позднее мы с А. В. Гладким совместными усилиями организовали собственный семинар «Алгоритмы и автоматы», послуживший основой для нашего нового отдела автоматов и математической лингвистики.

Со временем стало ясно, что у нас как-то не складываются отношения с институтскими логиками и дискретными математиками. В этой ситуации все большее значение приобретало идеологическое и практическое сближение с Ершовым и его отделом.

Отношения с логиками. Мои сотрудники, студенты и я сам активно участвовали в мальцевском семинаре «Алгебра и логика», докладывая на нем результаты по теории вычислимости, формальным языкам и т. п. (эти результаты впоследствии публиковались в  одноименном журнале). Тем не менее, с самого начала как в Институте математики, так и в университете, мы числились при отделе кибернетики.

Наше сотрудничество с отделом Мальцева осложнялось весьма прохладными отношениями, сложившимися между ним и А. А. Ляпуновым.

В 1966—1967 г. Анатолий Иванович решил организовать новый отдельный Институт алгебры и дискретной математики. По его плану, обсуждавшемуся на специальном заседании Ученого совета Института математики, новый институт должен был включать в себя также отделы теории автоматов и математической лингвистики. В то время я возглавлял исследования в этой области, однако Анатолий Иванович меня не пригласил участвовать в этом проекте. В институте это не осталось незамеченным. Для меня лично это обстоятельство не было вдохновляющим.

Так или иначе, тогда это предложение поддержки не получило, а после смерти Мальцева в 1967 г. к его рассмотрению больше не возвращались.

Уход Ляпунова. В 1970 г. Ляпунов и сам покинул Институт математики и перешел с частью отдела кибернетики в Институт гидродинамики.

Отношения с дискретными математиками. Многие из них, вслед за Яблонским, были категоричны в своем мнении, утверждая, что работа Яблонского 1959 г. была подлинным доказательством гипотезы перебора. Я принадлежал к числу критически относившихся к этим заявлениям и опирался в своих аргументах на теорию сложности (см. статью [3]). К сожалению, чисто академическая полемика переросла в опасную ситуацию. Этому способствовал и моральный климат в тогдашнем советском математическом сообществе, сказавшийся и на  специалистах по информатике. В отделении математики Академии наук СССР Яблонский играл ощутимую роль во всех  вопросах: контроле над конференциями, научными контактами с зарубежными странами, публикациями, в подтверждении и полуофициальном одобрении результатов, присвоении научных степеней. В дискретной математике он был полновластным судьей и нейтрализoвал даже  такого математика, как Колмогоров.

Среди множества примеров:

Леонид Анатольевич Левин[8].  Его кандидатская диссертация была «зарезана» по политическим мотивам. По договоренности с А. Н. Колмогоровым я представил ее Совету по защитам нашего Института математики.

Михаил Иосифович Дегтярь[9]. Был моим аспирантом и многолетним сотрудником по теме «сложность вычислений». Его защите, возможно, помешали антисемитские настроения: его диссертация по теории сложности провалилась, но это решение впоследствии было пересмотрено после протестов видных математиков. В частности, А. Н. Колмогоров энергично поддерживал его работу на совете по защитам мехмата МГУ.

Я. M. Барздинь. Был моим аспирантом, а затем в течение года — докторантом у Колмогорова. Oн не разделял некоторые из научных предпочтений Яблонского. Много лет чинили препятствия в утверждении его докторской диссертации.

3. Сближение

Хочу отметить те обстоятельства, которые на неблагоприятном фоне (см.  выше) содействовали моему сближению с А. П. Ершовым.

1. Дружеская атмосфера. Она была очень важна в те  времена, когда конфликты и соперничество из академических институтов перетекали в сферу личных отношений. К счастью, они не затронули ни отдел программирования, ни университетскую кафедру, которыми руководил А. П. Ершов. Цитируя В. Е. Котова: «В годы застоя А. П. сумел создать вокруг себя “свободную зону”, в которой преобладала здоровая политическая и человеческая атмосфера, полностью отличная от той, что была вовне; это очень облегчало нашу жизнь и работу».

2. Общие научные и преподавательские интересы. Примерно в 1970 г.  два новых научных направления повлияли на сближение наших точек зрения. Одно из них касалось главным образом программистского сообщества и возникло с появлением Алгола-68 и связанных с ним свежих идей, выдвинутых А. ван Вейнгаарденом и его коллективом. Другое началось с теории Скотта—Стрейчи  o  семантических областях и o денотационной семантикe. Предложенная в ответ на глубокие потребности теории программирования, в более широком контексте эта теория представляла собой научный прорыв и для сообщества логиков. Андрей Петрович всегда оставался человеком со вкусом к концептуальным источникам математической логики и теории алгоритмов. Таким образом, мы сознавали общность наших интересов в следующих темах.

(2.1) Теория схем программ: семантика, логика, выразительная сила, разрешимость, полнота. Для Андрея Петровича это было возрождением ранних работ Ляпунова—Янова—Ершова. Первый же мой результат по этой теме был опубликован в сборнике «Теоретическое программирование», который выходил в Вычислительном центре под редакцией Ершова.

(2.2) Модели параллелизма. В отделе Ершова велись исследования в области асинхронного программирования (В. Е. Котов, А. С. Нариньяни). Я имел хорошую возможность изучить этот предмет как официальный оппонент по их кандидатским диссертациям. С другой стороны, аспекты параллелизма, затронутые в работах Скотта, заинтересовали В. Ю. Сазонова из Института математики и М. Б. Трахтенброта из отдела А. П. Ершова.

(2.3) Преподавательская деятельность. В дополнение к нашей основной работе в Сибирском отделении Академии наук и я, и Ершов работали по совместительству в Новосибирском университете. Долгое время Андрей Петрович возглавлял там кафедру, на которой я читал курсы лекций и руководил студентами-дипломниками и аспирантами. Со временем часть этих студентов поступала на работу в Вычислительный центр или Институт математики.

3. Сотрудничество с международным сообществом. Андрей Петрович поддерживал хорошие, близкие отношения с большинством крупнейших ученых-программистов со всего мира, а также сотрудничал с ведущими зарубежными научными центрами. Это происходило в годы, когда поездка за рубеж, а особенно в «капстраны», была редкой привилегией[10].

К счастью, Андрей Петрович,  этой привилегией обладавший, чувствовал себя глубоко обязанным и делал все от него зависящее, чтобы облегчить изоляцию для тех, кого официальные научные учреждения в СССР ограничивали в контактах с зарубежными коллегами.

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

С другой стороны, Ершов был организатором ряда международных симпозиумов по теоретическому программированию, в которых принимали участие влиятельные зарубежные ученые. Именно там я и мои коллеги познакомились с Милнером, Парком, Патерсоном, Хоаром, Дейкстрой, Маккарти, Шварцем, Кнутом, Бауэром, Нива, Земанеком, Штрассеном, ван Вейнгаарденом... Кульминацией стал поистине незабываемый симпозиум «Алгоритм в современной математике и ее приложениях» (Ургенч, Узбекистан, 1979 г.). Он был задуман как научное паломничество в Хорезм, на родину «алгоритма», под председательством А. П. Ершова и Д. Кнута. Кнут вспоминал: «За эту неделю особенное впечатление произвело на нас то, как блестяще Ершов выступал в многочисленных ролях руководителя симпозиума — организатора, философа, докладчика, переводчика и редактора».

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

Валерий Александрович Непомнящий[11] был первым «мостиком» между моей группой в Институте математики и коллективом
А. П. Ершова в Вычислительном центре. Свои исследования Валерий Александрович начал с проблем вычислимости, а затем, с середины 60-х, продолжал их в Вычислительном центре, сконцентрировавшись на задачах верификации, тестирования, операторных алгоритмов, схем и т. д.

Валерий Николаевич Агафонов[12] работал со мной в Институте математики над задачами сложности алгоритмов и вычислений. Также он сотрудничал с А. П. Ершовым и другими коллегами из Вычислительного центра, и это сотрудничество было очень действенным даже после моего отъезда из Академгородка. Вот некоторые темы его монографий, учебных пособий и статей: синтаксический анализ, семантика и типы данных языков программирования, обработка информации, спецификация программ. Кроме того, В. Н. Агафонов был редактором большого числа переводов. Многие из этих работ выходили с предисловием или комментариями А. П. Ершова.

4. Расставание

Из Ургенча я возвращался вместе с Ершовым. Поздней сентябрьской ночью, уставшие и молчаливые, мы ехали из аэропорта в Академгородок. О чем думал Андрей Петрович? Скорее всего, о только что закончившейся прекрасной конференции. Мои же мысли на эту тему были перемешаны с тревогой. Незадолго до конференции я принял трудное, не подлежащее пока разглашению решение об эмиграции. Предстояли три этапа с непредсказуемыми поворотами и результатами: получение заграничного приглашения, оповещение институтского руководства и, наконец, подача заявления на выездную визу. Разумеется, превыше всего угнетала травматическая перспектива расставания (быть может, навсегда) с близкими людьми.

В марте 1980 г. было получено приглашение из Израиля, и я приступил к последующим этапам. Прежде всего я посетил Андрея Петровича, информировал его о моих делах и просил его помощи. Такая помощь касалась тех, чье положение осложняли мои планы. Андрей Петрович быстро проявил ожидаемое мной сочувствие и готовность помогать во всем. Начну с моего старшего сына Марка, ученика Ершова и многолетнего сотрудника отдела программирования. Марк и его семья не собирались тогда эмигрировать, и Андрей Петрович обещал заботиться о дальнейшем статусе Марка. Другой пример: Андрей Петрович охотно взял на себя ответственность за завершение диссертаций и дипломных работ, начатых под моим руководством. Впоследствии все обещанное и немало сверх того Андрей Петрович выполнил аккуратно.

После первоначального отказа мне, жене и младшему сыну были выданы выездные визы. Настало время отъезда. Ершов позвонил мне домой и договорился о прощальном визите к нам... Мы уехали в декабре 1980 г. Больше я Андрея Петровича не видел. 22 сентября 1983 г. он мне послал из Парижа вышедшие незадолго до того труды конференции с надписью «...на добрую память об Ургенче». Это было последнее послание, полученное от Андрея Петровича. Потом стали поступать из Новосибирска тревожные вести...

Список литературы

1. Trakhtenbrot B. A. From Logic to Theoretical Computer Science// People and Ideas in Theoretical Computer Science/ Ed. by C. S. Calude.­ —   Springer, 1998.­ —   P. 314—341
2. Трахтенброт Б. А. Вспоминая Алексея Андреевича (пятидесятые годы)//  Конференция, посвященная 90-летию со дня рождения А. А. Ляпунова.­ —  Новосибирск, Академгородок,  2001.­ —  http://www.ict.nsc.ru/ws/sea_doc.phtml?ru+19
3. Trakhtenbrot B. A. A Survey of Russian Approaches to Perebor// Annals of the History of Computing.­ —  1984.­ —  Vol. 6, N 4.­ —  P. 384—400.

Примечания

[1] © Трахтенброт Б. А., 2005. Написано специально для настоящего сборника. Перевод с англ. А. А. Бульонковой.

[2] В оригинале — computer science  (Прим. переводчика).

[3] Сергей Всеволодович Яблонский (1924—1998) — академик, один из основателей отечественной школы математической кибернетики и дискретной математики. С 1958 г. С. В. Яблонский возглавил отдел математической кибернетики ИПМ АН СССР, созданный им совместно с А. А. Ляпуновым.

[4] Ершов А. П., Камынин С. С., Любимский Э. З. Автоматизация программирования// Тр. Третьего Всесоюзн. математ. съезда. Москва, июнь—июль 1956 г. Т. 2.— М., 1956. — С. 74—76.

[5] Александр Александрович Зыков (р. 1922) — математик, д. ф.-м. н., специалист по теории графов, работал в ИМ СО АН, в настоящее время работает в Одессе.

[6] Алексей Всеволодович Гладкий (р. 1928) — д. ф.-м. н., одним из первых в СССР начал заниматься математической лингвистикой, в НГУ создал и возглавил Отделение математической лингвистики, в настоящее время — в Москве.

[7] А. П. Ершов, А. А. Ляпунов. О формализации понятия программы// Кибернетика. — 1967. — № 5. — С. 40—57.

[8] Леонид Анатольевич Левин (р. 1948), один из лучших учеников А. Н. Колмогорова, основные работы по теории сложности и теории информации, один из первооткрывателей NP-полных проблем. Родился в Днепропетровске, в настоящее время — профессор Бостонского университета.

[9] Михаил Иосифович Дегтярь (р. 1946) — выпускник НГУ, аспирант Б. А. Трахтенброта, в настоящее время — профессор университета в Твери. Область научных интересов — теория сложности, мультиагентные системы.

[10] Я, например, впервые побывал в зарубежной командировке в 1967 г. в Польше, по приглашению Института математики Польской академии наук, но посещение западной страны стало для меня возможным только в 1981 г., после эмиграции в Израиль.

[11] Валерий Александрович Непомнящий (р. 1940) — к. ф.-м. н., сотрудник отдела программирования, в настоящее время — заведующий лабораторией теоретического программирования ИСИ СО РАН.

[11] Валерий Николаевич Агафонов (1940—1997) — математик, специалист в области теории сложности и теоретических основ обработки информации, много лет работал в ИМ СО АН, последние годы жизни — в Твери.

6 июля 2005
Из сборника «Андрей Петрович Ершов — ученый и человек». Новосибирск, 2006 г.
Перепечатываются с разрешения редакции.