С. Н. Артемов, Я. М. Барздинь, Л. А. Бокуть, Ю. Ш. Гуревич, А. М. Дехтярь, Л. А. Левин, И. А. Ломазова, Ю. В. Матиясевич, В. А. Непомнящий, С. П. Новиков, А. Рабинович, В. Ю. Сазонов, А. О. Слисенко, В. А. Соколов, М. Б. Трахтенброт, Н. В. Шилов, “Борис Абрамович Трахтенброт (к столетию со дня рождения)”, УМН, 77:1(463) (2022), 191–195; Russian Math. Surveys, 77:1 (2022), 183

Борис Абрамович Трахтенброт (20.02.1921–19.09.2016), которому 20 февраля 2021 г. исполнилось бы сто лет, – один из создателей теоретических основ информатики, или Theoretical Computer Science, широко признанный и в СССР, и в мире. Его научная биография интересна также и в гуманистическом, и в историческом аспектах.

Б. А. Трахтенброт родился 20 февраля 1921 г. в Бессарабии, в поселке Бричево (исторически – Россия, Румыния, СССР, Молдова). В 1940 г. он начал изучать математику в Кишиневском педагогическом институте. С началом Великой Отечественной войны он эвакуировался вместе с институтом на Урал; Кишинев уже бомбили. До 1943 г. он был полностью лишен связи с семьей, разделенной и высланной из Бессарабии на Урал и в Сибирь в рамках массовой депортации в июне 1941 г. (парадоксальным образом это спасло его семью от Холокоста). Борис Абрамович не был призван на фронт из-за плохого зрения. В этот период нерегулярная учеба совмещалась с работой (на фабрике валенок, в газовом тресте).

Вернувшись из эвакуации в 1944 г., Б. А. Трахтенброт проработал год учителем математики в г. Бельцы. Он завершил высшее образование по математике в Черновицком университете (1945–1947 гг.). Параллельно с учебой Борис Абрамович активно участвовал в восстановлении богатейшей математической библиотеки ЧГУ, и это сыграло большую роль в его образовании и приобщении к науке. Ряд преподавателей ЧГУ были выходцами из московских математических школ. Большое влияние на Б. А. Трахтенброта оказал один из них – А. А. Бобров, ученик А. Н. Колмогорова. На его семинаре по книге Хаусдорфа Борис Абрамович увлекся дескриптивной теорией множеств. По совету А. А. Боброва (а несколько позже и Б. В. Гнеденко во Львове) Борис Абрамович встретился в Москве с А. Н. Колмогоровым, а затем с П. С. Новиковым и А. А. Ляпуновым. Подробная беседа с выдающимся математиком Петром Сергеевичем Новиковым (1901–1975) была решающей – он заинтересовал Бориса Абрамовича современными тенденциями в математической логике и теории вычислимости и предложил быть его научным руководителем.

В 1947–1950 гг. Б. А. Трахтенброт был аспирантом в Институте математики Украинской АН в Киеве. Директор института М. А. Лаврентьев предоставил ему возможность долгосрочных научных визитов в Москву для работы под руководством П. С. Новикова. В итоге основным результатом его кандидатской диссертации была теорема Трахтенброта о неразрешимости множества логических формул первого порядка, истинных на конечных моделях. Фактически этот классический результат оказался фундаментальным вкладом в бурно развивавшуюся позже теорию конечных моделей.

В это же время Б. А. Трахтенброт часто посещал “Большой логический семинар” в МГУ, тесно общаясь с А. А. Ляпуновым, А. Н. Колмогоровым, С. А. Яновской и с молодыми, в последующем именитыми коллегами. Одним из участников этого семинара был А. С. Есенин-Вольпин, сын знаменитого поэта. Борис Абрамович впервые встретился с ним в 1949 г. в Черновцах. А. С. Есенин-Вольпин прибыл в ЧГУ по назначению, после своей защиты, но так и не приступил к преподаванию там математической логики, так как вскоре был выслан в Караганду. Но Борис Абрамович и Александр Сергеевич продолжали поддерживать близкие контакты из-за общности научных интересов, а их последняя встреча состоялась уже в Иерусалиме в 2009 г.

Те послевоенные годы были непростым временем. Tитанам науки в СССР приходилось бороться с идеологическими обвинениями в адрес математической логики и кибернетики, порой ценой каких-то весьма неприятных уступок. Вскоре это коснулось и Бориса Абрамовича лично.

После защиты с блеском кандидатской диссертации в 1950 г. (его оппонентами были А. Н. Колмогоров, А. А. Ляпунов и Б. В. Гнеденко) Б. А. Трахтенброт начал работать в Пензенском педагогическом институте. Он попал туда в результате трудного поиска места работы, проходившего на фоне “борьбы с космополитизмом”. Здесь его ждало тяжелое испытание, начавшееся со сделанного им на семинаре доклада на тему “Метод символических исчислений в математике” и длившееся почти весь 1951 год. По следам этого доклада его объявили “идеалистом типа Карнапа” – абсурдное, но довольно опасное обвинение, особенно в свете вышедшей незадолго до этого работы Сталина “Марксизм и вопросы языкознания”. К счастью, старшие московские коллеги П. С. Новиков, А. А. Ляпунов, А. Н. Колмогоров, А. Г. Курош и С. А. Яновская смогли его защитить. Да и сам Борис Абрамович оказался настоящим бойцом, с честью вышедшим из этого сражения. Эта волнующая документальная история изложена в [1], [2].

По рекомендации участников московского “Большого логического семинара”, чтобы обезопасить себя в будущем и фактически способствовать закреплению научных позиций формальных методов, Б. А. Трахтенброт опубликовал в журнале “Математика в школе” статью “Алгоритмы и машинное решение задач” (1956 г.). Затем она была переработана в приобретшую в СССР широкую популярность одноименную книгу (1957, 1960; расширенная версия “Алгоритмы и вычислительные автоматы” вышла в 1974 г.), переведенную на 12 языков мира. Ряд крупных ученых высоко оценили ее как прекрасное, увлекательное и доступное введение в предмет [3], [4]. После выхода в свет этой книги министерство образования организовало в Пензе всероссийскую конференцию “Алгоритмы и ЭВМ” с участием П. С. Новикова, А. И. Мальцева, О. Б. Лупанова и других видных ученых.

Помимо преподавания, Б. А. Трахтенброт продолжил исследования по рекурсивной неотделимости и неполноте формальных теорий, начатые в кандидатской диссертации, работал над классификацией рекурсивных операторов и, вместе с А. В. Кузнецовым (1927–1987), распространил исследование на частично-рекурсивные операторы в пространстве Бэра.

Но постепенно он стал склоняться к исследованиям в области теоретической кибернетики, которые тогда активно продвигали А. А. Ляпунов и С. В. Яблонский; сюда входили теория переключательных схем, минимизация булевых функций, кодирование, автоматы, схемы программ и т. д. В 1958 г. Борис Абрамович получил важнейший результат, который после работ Р. Бюхи и К. Эльгота стал широко известен как теорема Бюхи–Эльгота–Трахтенброта о выразительной эквивалентности конечных автоматов и слабой монадической логики второго порядка. Он также написал две книги: “Введение в теорию конечных автоматов” с Н. Е. Кобринским (1910–1985), опубликованную в 1962 г., и “Конечные автоматы (поведение и синтез)” с Я. М. Барздинем, вышедшую в свет в 1970 г. Обе книги были изданы также за рубежом на английском языке.

С января 1960 г. Б. А. Трахтенброт начал работать в новом Институте математики Сибирского отделения АН СССР по приглашению его директора С. Л. Соболева. Борис Абрамович стал сотрудником отдела теоретической кибернетики, созданного по инициативе А. А. Ляпунова, а также профессором Новосибирского государственного университета. В 1967 г. совместно с А. В. Гладким (1928–2018) они создали в Институте математики отдел теории автоматов и математической лингвистики. Сотрудниками, студентами и аспирантами, связанными с Борисом Абрамовичем и отделом, были в разные периоды В. Агафонов (1940–1997), Я. Барздинь, Н. Белякин (1936–2016), А. Коршунов (1936–2019) (оба последовали за Б. А. из Пензы), В. Бояркин, А. Вайсер, М. Валиев (1942–2018), М. Дехтярь (1946–2018), А. Диковский (1945–2014), М. Кратко (1936–2018), З. Литвинцева, И. Ломазова, С. Матвеева, Л. Модина (1945–2017), В. Непомнящий (1939–2021), Л. Ореховская, В. Сазонов, М. Соколовский, Р. Фрейвалд (1942–2016), Д. Ходжаев. Помимо них в семинаре “Алгоритмы и автоматы” участвовали С. Артёмов, М. Канович, Е. Кинбер, В. Котов, Л. Лисовик, Г. Плесневич, Р. Плюшкявичус, А. Слисенко, М. Тайцлин (1936–2013), Г. Цейтин… – всех не перечесть.

В этот чрезвычайно плодотворный период Б. А. Трахтенброт работал над вопросами теории автоматов и теории сложности, такими как автосводимость алгоритмических проблем, частотные и вероятностные вычисления, формализация проблемы перебора и др. (подробности и ссылки см. в [1], [5]). Преподавание и исследования по теории сложности привели его к публикации учебного пособия – на самом передовом научном уровне – “Сложность алгоритмов и вычислений” (1967). Были также получены фундаментальные результаты:

– теорема Бородина–Трахтенброта о существовании сколь угодно больших разрывов в иерархии классов сложности;

– теорема об автосводимости, утверждающая существование алгоритмических проблем произвольной сложности, которые невозможно упростить путем автосведения;

– техника следов (разработана совместно с Я. М. Барздинем независимо от М. О. Рабина, Ю. Хартманиса и Ф. Хенни) для получения нижних оценок сложности вычислений; она часто включается в современные курсы по теории вычислимости.

В 1970-е гг. Борис Абрамович с сотрудниками стал с большим энтузиазмом заниматься теорией программирования, охватывая в университетских спецкурсах и на семинаре “Алгоритмы и автоматы” такие темы, как семантические и логические проблемы языков программирования высокого уровня, схемы программ, программные логики, спецификация и верификация программ, функциональные и императивные языки, лямбда-исчисление. Так значительно укрепились общие научные интересы с А. П. Ершовым и его коллегами в ВЦ СОАН СССР [6].

В декабре 1980 г. Б. А. Трахтенброт эмигрировал в Израиль, где стал профессором Школы компьютерных наук Тель-Авивского университета (с 1991 г. – professor emeritus). Эмиграция в социально-политических реалиях начала 1980-х годов могла привести к полной потере связи с учениками в СССР. Однако ситуация изменялась так стремительно, что Борис Абрамович смог приехать в СССР на конференцию уже в 1989 г. С тех пор он не раз бывал в России и приглашал многих своих коллег в Израиль.

После переезда в Израиль Борис Абрамович заинтересовался рядом новых тем, исследования по которым он проводил в содружестве с израильскими и американскими коллегами. Среди этих новых направлений – семантика алголоподобных языков (с Дж. Хальперном и А. Р. Мейером), сети параллельных процессов и парадигмы непрерывного времени (с А. Рабиновичем и Й. Хиршфельдом), гибридные и реактивные системы [1]. Наряду с этим Борис Абрамович предпринял также много усилий [7], [8] для привлечения внимания (в первую очередь – западных ученых) к научным достижениям и научной жизни в СССР в области Computer Science.

Б. А. Трахтенброт тонко чувствовал и понимал концептуальное значение зарождавшихся новых научных направлений и замечательно ставил задачи. Его ученики внесли вклад практически во все основные направления – схемы программ, автоматы, семантику языков программирования, теорию сложности, программные логики, верификацию программ, алгебраические спецификации типов данных, теорию параллелизма.

Неоценимая роль Б. А. Трахтенброта в области Theoretical Computer Science как “столпа компьютерных наук” отмечена посвященным ему сборником [9] (см. также [10], [11]). В 1997 г. Университет им. Ф. Шиллера в Йене присвоил ему докторскую степень honoris causa. В 2011 г. он был удостоен престижной премии Европейской ассоциации теоретической информатики (EATCS) [12] за “обширный и широко признанный вклад в теоретическую информатику на протяжении всей научной карьеры”. Отражением высокого авторитета Б. А. Трахтенброта служит и то, что он был приглашенным профессором в ведущих университетах США, Великобритании, Германии, Франции, Швеции, Голландии, Польши и других стран. Он также был приглашенным докладчиком на многих престижных конференциях – таких как ICALP, STOC и другие.

На сайте [13] можно послушать воспоминания учеников, коллег и Марка Трахтенброта (сына) о Борисе Абрамовиче (см. также предисловие к [9] и [3], [11]), увидеть его научную родословную (см. также [5]), фотографии и материалы семинара, посвященного его столетию.

Вспоминая Бориса Абрамовича, нельзя не помянуть его верную спутницу жизни Берту Исааковну (1921–2013). Многие из нас пользовались теплым гостеприимством этой замечательной семьи. Мы также отдаем дань памяти ученикам и ближайшим коллегам Бориса Абрамовича, которых уже нет с нами (см. выше и [14]).

Борис Абрамович Трахтенброт прожил долгую и счастливую жизнь и создал свою школу – Школу Трахтенброта с прекрасной научной и нравственной атмосферой. Он скончался в г. Реховот (Израиль) 19 сентября 2016 г. в возрасте 95 лет.

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

Образец цитирования: С. Н. Артемов, Я. М. Барздинь, Л. А. Бокуть, Ю. Ш. Гуревич, А. М. Дехтярь, Л. А. Левин, И. А. Ломазова, Ю. В. Матиясевич, В. А. Непомнящий, С. П. Новиков, А. Рабинович, В. Ю. Сазонов, А. О. Слисенко, В. А. Соколов, М. Б. Трахтенброт, Н. В. Шилов, “Борис Абрамович Трахтенброт (к столетию со дня рождения)”, УМН, 77:1(463) (2022), 191–195; Russian Math. Surveys, 77:1 (2022), 183–188

Цитирование в формате AMSBIB

\RBibitem{ArtBarBok22}

\by С.~Н.~Артемов, Я.~М.~Барздинь, Л.~А.~Бокуть, Ю.~Ш.~Гуревич, А.~М.~Дехтярь, Л.~А.~Левин, И.~А.~Ломазова, Ю.~В.~Матиясевич, В.~А.~Непомнящий, С.~П.~Новиков, А.~Рабинович, В.~Ю.~Сазонов, А.~О.~Слисенко, В.~А.~Соколов, М.~Б.~Трахтенброт, Н.~В.~Шилов

\paper Борис Абрамович Трахтенброт (к~столетию со дня рождения)

\jour УМН

\yr 2022

\vol 77

\issue 1(463)

\pages 191--195

\mathnet{http://mi.mathnet.ru/rm10048}

\crossref{https://doi.org/10.4213/rm10048}

\mathscinet{http://mathscinet.ams.org/mathscinet-getitem?mr=4582592}

\zmath{https://zbmath.org/?q=an:1485.01044}

\adsnasa{https://adsabs.harvard.edu/cgi-bin/bib_query?2022RuMaS..77..183A}

\transl

\jour Russian Math. Surveys

\yr 2022

\vol 77

\issue 1

\pages 183--188

\crossref{https://doi.org/10.1070/RM10048}

\isi{https://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=Publons&SrcAuth=Publons_CEL&DestLinkType=FullRecord&DestApp=WOS_CPL&KeyUT=000790541000001}

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