Успехи математических наук, 2023, том 78, выпуск 3(471), страницы 170–176 DOI: https://doi.org/10.4213/rm10092 (Mi rm10092)

DOI: https://doi.org/10.4213/rm10092

Англоязычная версия:
Russian Mathematical Surveys, 2023, Volume 78, Issue 3, Pages 555–561
DOI: https://doi.org/10.4213/rm10092e

Реферативные базы данных:

Zoom inZoom out

27 августа 2022 г. ушел из жизни выдающийся российский и американский ученый в области математической логики и теоретической информатики Григорий Самуилович Цейтин.

Григорий Самуилович родился в Ленинграде 15 ноября 1936 г. Мать, Берта Львовна Сапожникова, была инженером-экономистом, отец, Самуил Бенцианович Цейтин, – преподавателем математики. Родители были выходцы из Белоруссии, из многодетных еврейских семей. Во время войны Берта Львовна с сыном находились в эвакуации в Кировской области.

Гера Цейтин несомненно был вундеркиндом и с детства проявил неординарные способности. В 1945 г. восьмилетний Григорий поступил в пятый класс 203-й школы. Специальная комиссия, состоявшая из профессоров Г. М. Фихтенгольца, В. А. Тартаковского и Д. К. Фаддеева, заключила: “Развитие Геры в области математики далеко выходит за пределы всяких норм. Для него совершенно доступен уже в настоящее время круг вопросов, входящих в программу курса математики в 10-летней школе…”. В девятилетнем возрасте Гера стал победителем олимпиады по математике для 10-го и по физике для 9-го классов. В школе он проявлял большой интерес к языкам, отлично катался на коньках. В четырнадцать лет Григорий окончил школу с медалью, но по формальным причинам из-за возраста не был принят в ЛГУ и первый курс матмеха посещал как вольнослушатель. В сентябре 1952 г., с разрешения Министерства высшего образования, он был принят студентом на второй курс; в этом решении сыграло роль личное участие ректора А. Д. Александрова.

В первые годы учебы Григорий медленно осваивался в студенческой среде; с одной стороны, он был существенно младше своих сокурсников, а с другой – знал значительно больше, чем студенты старших курсов. И это, вместе с особенностями его воспитания (мама сопровождала Геру в университет и ожидала его там до окончания лекций), затрудняло контакты с товарищами по курсу. Особенностью Григория Самуиловича всегда было строгое соблюдение в речи и поступках формальных правил. Окружающих приятно удивляла его детская доверчивость и жажда общения. В университетские годы он очень скоро преодолел свойственную бывшим вундеркиндам обособленность, окончил музыкальную школу для взрослых, полностью акклиматизировался и на старших курсах стал проявлять исключительную активность (участие в кружках, и не только математических). Он был среди организаторов и преподавателей юношеской математической школы (ЮМШ, 1960 г.), активизировал деятельность студенческого научного общества (СНО), начал издавать студенческий математический журнал, принимал участие в организации английского клуба, выпустил первый ротапринтный сборник студенческих и туристских песен, ездил на целину.

На втором курсе Григорий начинает слушать пятисеместровый специальный курс А. А. Маркова “Теория алгорифмов”, и ему стало ясно, что он нашел своего учителя. Действительно, математическая логика, как никакая другая область математики, подходила ему по складу его ума. Первая научная работа “О числе шагов в алгорифме” была выполнена к концу учебного года. Судя по всему, этот студенческий результат вошел в текст работы [5]. Дипломная работа Г. C. Цейтина “Ассоциативное исчисление с неразрешимой проблемой эквивалентности” содержала важнейшие и актуальные результаты и была опубликована в “Докладах АН СССР” [1], [2].

Следует сказать несколько слов об истории этой работы. В 1947 г. А. А. Марков и Э. Пост независимо установили алгоритмическую неразрешимость проблемы тождества для конечно определенных полугрупп. Эта проблема была сформулирована А. Туэ в 1914 г. задолго до появления точного понятия алгоритма. Марков указал неразрешимую систему Туэ^1[x]1Система Туэ – это способ задания конечно определенной полугруппы посредством соотношений между образующими; в отечественной литературе системы Туэ называют также ассоциативными исчислениями., задаваемую 33 соотношениями в алфавите из 13 образующих. Г. С. Цейтин построил следующий радикально более простой пример системы Туэ с неразрешимой проблемой тождества с 5 образующими и 7 соотношениями:

Одна из идей, которая позволила Г. С. Цейтину построить такой простой пример, состояла в использовании группы с неразрешимой проблемой тождества, существование которой незадолго до этого установил П. С. Новиков. Более десяти лет пример Цейтина оставался простейшим примером неразрешимого ассоциативного исчисления. В дальнейшем конструкции Цейтина были использованы другими исследователями для построения универсальных (по вложению) компактных систем Туэ и простых примеров неразрешимых полусистем Туэ, более интересных для информатики. 

Окончив матмех в 1956 г., Г. С. Цейтин поступил в аспирантуру к А. А. Маркову. Некоторое время он занимался проблемами конструктивной математики, разрабатываемыми школой Маркова–Шанина. Существенным достижением Г. С. Цейтина было доказательство несуществования конструктивной вещественной функции, определенной на отрезке, принимающей значения разных знаков на его концах и не имеющей конструктивного корня на этом отрезке. С другой стороны, им же было доказано, что не существует алгорифма^2[x]2Написание “алгорифм”, характерное для ленинградской школы Маркова, мы здесь сохранили в память о том времени., который по любой конструктивной функции с тем же свойством строит конструктивный корень в отрезке. Замечательным открытием Г. С. Цейтина является первый в этой области нетривиальный (и неожиданный) положительный результат (теорема о непрерывности), состоящий в том, что любое конструктивное отображение конструктивного полного сепарабельного метрического пространства в другое конструктивное метрическое пространство непрерывно (в конструктивной математике под непрерывностью подразумевается наличие алгорифма, находящего $\delta$ по $\varepsilon$). Эта замечательная теорема является принципиальным усилением более раннего результата А. А. Маркова об отсутствии конструктивных разрывов у конструктивных функций. В 1959 г. Григорий Самуилович поступил на работу младшим научным сотрудником НИИ математики и механики ЛГУ. В 1960 г. он защитил кандидатскую диссертацию на тему “Алгорифмические операторы в конструктивных полных сепарабельных метрических пространствах” (оппонентами были В. А. Успенский и Н. А. Шанин). В течение нескольких лет он еще продолжал заниматься конструктивной математикой. По новым результатам, частично полученным совместно с И. Д. Заславским, в 1968 г. Г. С. Цейтин защитил докторскую диссертацию [4], оппонентами по которой были А. А. Марков, Б. А. Трахтенброт и Н. А. Шанин. Здесь Григорий Самуилович подвел итог своей работы в конструктивном направлении. В дальнейшем он более не принимал участия в разработке этой тематики.

Другой большой темой исследований Г. С. Цейтина была теория сложности. Он был пионером в анализе нижних оценок временно́й сложности алгорифмов и длин доказательств для пропозициональных формул. Еще в 1957 г. он доказал нижнюю оценку $n^2 \log^{-2}n$ временно́й сложности обращения слова нормальными алгорифмами А. А. Маркова. Перед этим в 1954 г. им было доказано^3[x]3Опубликовано лишь в 1971 г. [5], что в качестве модели вычислений можно взять машину Тьюринга, в которой есть возможность выреза́ть и вставлять ячейки. Впоследствии в 1969 г. с помощью очень остроумной конструкции Григорий Самуилович получил точную нижнюю оценку $c\cdot n^2$, где константа $c$ определяется алгорифмом [6]. Заметим, что используемая вычислительная модель сильнее обычной машины Тьюринга.

Три понятия, введенные Г. С. Цейтиным, постоянно употребляются в теории сложности доказательств. Первое – цейтинское правило расширения, позволяющее вводить новые переменные и обозначать ими произвольные формулы. Даже довольно слабую систему – метод резолюций – это правило делает столь сильной, что мы до сих пор не умеем доказывать для полученной системы экспоненциальные нижние оценки, и даже не имеем хороших кандидатов на сложные формулы. Второе – цейтинские формулы (системы линейных уравнений над конечным полем, построенные по графу), они были первыми формулами в теории сложности, для которых удалось доказать суперполиномиальную нижнюю оценку сложности пропозициональных доказательств, а именно оценку Цейтина для метода регулярных резолюций. Эта работа [3] оказала большое влияние на дальнейшие исследования сложности пропозициональных доказательств и стала одной из самых цитируемых работ российской школы в области математической логики и теории алгоритмов. Наконец, третья идея – цейтинский перевод булевых схем в пропозициональные формулы, ставший стандартным приемом в теории сложности вычислений.

После того как Григорий Самуилович защитил докторскую диссертацию, его интересы окончательно переключились в область информатики, и он быстро стал неформальным лидером ленинградской школы программирования. Является большой удачей, что Г. С. Цейтин, математик высочайшего уровня, стал пионером и классиком в новой науке – информатике (этот термин он считал более удачным, чем “computer science”) и обосновал ее самостоятельность и специфику. В частности, он отмечал, что главное отличие информатики от математики, “хотя бы и рассматривались одни и те же объекты, состоит в том, что в информатике определяющим является человеческий фактор” [9]. Его увлекла новая область деятельности, которая сочетала строгие математические методы с социальной спецификой, обусловленной как коллективным характером производства программ, так и необходимостью адаптации результата деятельности программистов к восприятию людьми, проблемой защиты программ и т. п. Увлекла настолько, что в то время Григорий Самуилович сам в беседах с коллегами порой отмечал, что больше не считает себя математиком.

Неотъемлемой стороной деятельности Г. С. Цейтина было преподавание. Среди прочитанных им многочисленных курсов отметим пятисеместровый курс по теории алгоритмов и рекурсивных функций. Его лекции совсем не походили на стандартные курсы с множеством формул и доказательств. Он объяснял все идеи, приемы и алгоритмы, но основной упор в его лекциях делался на сложные открытые задачи. Он призывал слушателей задавать нетривиальные вопросы, выходить с новыми задачами, новыми идеями – и это он ценил больше, чем простое воспроизведение того, чему он учил. Для того чтобы придумывать новые идеи, студентам приходилось прилагать много усилий на его занятиях и между ними, и многие студенты отмечали, что лекции Григория Самуиловича научили их большему, чем другие предметы по компьютерной тематике.

Из отзывов коллег: “Чем бы Г. С. Цейтин ни занялся: программированием или ремонтом примусов – у него это получится лучше, чем у других”; “Его доклады на семинаре кафедры были не просто интересны – это всегда был праздник мысли”.

После появления в конце 1950-х годов пионерских работ Н. Хомского по формальным грамматикам Г. С. Цейтин начал интересоваться машинной обработкой текстов на естественных языках. Одной из граней этой проблемы стал автоматический перевод с одного языка на другой; впоследствии появились другие задачи, в которых требовалось глубокое понимание механизмов, лежащих в основе естественных языков, и их описание в форме, пригодной для компьютерных приложений. В 1960-х годах Г. С. Цейтин возглавил в Ленинградском университете исследовательскую группу по созданию экспериментальных систем в этой области. На основе этой группы была создана лаборатория математической лингвистики, впоследствии переименованная в лабораторию интеллектуальных систем. В то время много выдающихся ученых по всему миру работали над задачей автоматизации перевода с любого языка на любой другой. Г. С. Цейтину, хорошо владевшему несколькими языками, активному пропагандисту языка международного общения эсперанто, эта идея была особенно близка. Она, наряду с упомянутой выше причиной, способствовала постепенному отходу Григория Самуиловича от математической логики к программированию. В течение ряда лет он разработал оригинальную систему программирования на семантических сетях, соединив в ней знания из филологии с идеями из формальной логики и методами системного программирования. Хотя автоматический перевод в рамках этой системы так и не смог составить конкуренцию современным системам перевода, основанным на статистических методах, идеи, предложенные Г. С. Цейтиным, еще ждут своего часа. В отличие от промышленных систем перевода, разработанные им методы позволяют извлекать из текста заложенный в нем смысл, используя перебор с возвратом на основе заготовленных словарных статей, вычисляемые атрибуты и т. п. Еще тридцать лет назад, при технике, не сравнимой по вычислительной мощности с современной, сотрудникам лаборатории удавалось получать в областях понимания естественного языка, синтеза программ, искусственного интеллекта практические результаты, вполне достойные и по нынешним меркам.

Григорию Самуиловичу было свойственно относиться к математическому творчеству и научной деятельности с высоких позиций и пересматривать их время от времени. В частности, его фактический переход от математической логики к теории алгоритмических языков следовал тем изменениям, которые происходили в научных представлениях. Исследование проблем языка и искусственного интеллекта связано у него с глубоким пониманием этих тенденций. Проницательные наблюдения Григория Самуиловича на эту тему остаются актуальными и сегодня (см. работу [8]).

В то же время и под влиянием тех же идей на кафедре математического обеспечения ЭВМ и в НИИ математики и механики ЛГУ сформировалась сильная группа ученых и программистов, занимавшихся разработкой трансляторов для различных языков программирования. Особенно заинтересовал Григория Самуиловича Алгол-68 – язык с очень богатым синтаксисом, реализация которого представляла большую сложность и несомненный научный интерес. Достаточно сказать, что в мире существует только два компилятора этого языка. Г. С. Цейтин возглавил проект на начальной стадии, разработал базовые идеи и в 1968 г. включился в международное сотрудничество по разработке и реализации этого языка [7]. Как писал один из самых авторитетных специалистов по математической логике и программированию С. С. Лавров, именно под влиянием этой замечательной работы зародилась и получила развитие ленинградская школа программирования. По выражению С. С., “даже если бы Алгол-68 не нашел в нашей стране никакого применения, … появление цейтинской школы с лихвой оправдало бы его существование”.

Постепенно Г. С. Цейтин начал сотрудничать с иностранными исследовательскими группами, занимающимися практической информатикой. Так, в 1990–1995 гг. он работает с группой по модификации операционной системы MS DOS и построению текстовой базы данных, в 1995–1996 гг. – с итальянской компанией Microstar Software Ltd. Г. С. Цейтину становится слишком тесно в рамках, предоставляемых подразделениями Петербургского университета. Он больше не видит для себя возможности работать в полную силу. К этому надо добавить несправедливые и неуместные упреки к нему со стороны администрации по поводу его деятельности в качестве заведующего лабораторией, лектора (он не получил даже звания профессора).

В 1997 г. по приглашению фирмы IBM Г. С. Цейтин провел несколько месяцев в исследовательском центре Альмаден в Калифорнии, занимаясь исследованиями в области интеллектуального анализа данных (phenomenal data mining). В 1999 г. он продолжил эти занятия в Ирландии, в Тринити-колледже в Дублине (об этой работе см. в [10]).

В 1999 г. Г. С. Цейтин получил приглашение в США для участия в проекте по обработке естественного языка в университете штата Нью-Мексико. По финансовым причинам через год этот проект прекратился, но Г. С. Цейтин принял решение остаться в США. При поддержке виднейших специалистов из разных стран он подал заявление на вид на жительство по статье “иностранец выдающихся способностей”. Одну из рекомендаций написал профессор Стэнфордского университета Джон Маккарти, выдающийся специалист в области математической логики, информатики и автор концепции искусственного интеллекта. Он был хорошо знаком с работами Г. С. Цейтина, высоко их ценил, способствовал его визиту в 1997 г. и существенно помог Григорию Самуиловичу в первые годы пребывания и работы в США. В 2002 г. Г. С. Цейтин получил статус постоянного жителя Америки, а в 2008 г. – американское гражданство.

В 2000 г. Г. С. Цейтин переехал в Калифорнию, в район Сан-Хосе, и начал работу в фирме Rational Software, которая продолжалась до 2009 г. В этот период им были получены 4 патента. После этого четыре года он проработал в Стэнфордском университете, где занимался построением системы автоматического обучения школьников в проекте известного американского философа и логика Патрика Суппеса.

К сожалению, в течение всех лет жизни в Америке Григорию Самуиловичу не вполне удалось найти адекватное применение своим огромным возможностям.

На протяжении всей своей жизни Г. С. Цейтин отдавал много времени активной работе в научных сообществах. Он был членом Ленинградского (потом Санкт-Петербургского) математического общества почти со времени возобновления его деятельности в 1959 г. и сделал много докладов на его заседаниях. Начиная с 1989 г. и до своего отъезда в США Григорий Самуилович посвятил много усилий основанию и работе Санкт-Петербургского союза ученых (СПбСУ), членом координационного совета которого он был со дня основания. После отъезда СПбСУ поручил ему быть представителем союза в США.

Ассоциация вычислительной математики (ACM), членом которой был Г. С. Цейтин, присвоила ему почетное звание выдающегося ученого в 2006 г. Он был также членом Ассоциации логического программирования (ALP).

Любовь к языку эсперанто, которым Григорий Самуилович овладел в юношеские годы, привела его к работе в секции эсперанто еще в Санкт-Петербурге, а после переезда в США он по-прежнему участвовал в пропаганде и изучении этого языка; в частности, в 2017–2020 гг. он был секретарем региональной организации эсперантистов в Сан-Франциско.

Г. С. Цейтин был наделен от природы огромным и редким даром; его математический талант поражал окружающих и реализовался во многих его замечательных трудах. Его достижения были повсеместно признаны ученым миром. В то же время Григорий Самуилович был совершенно лишен даже тени высокомерия, в нем начисто отсутствовало чувство превосходства и сознания своего преимущества перед окружающими. Его неподдельная доброта, бескорыстная готовность помочь коллегам в любой работе подчас удивляла людей. Его талант распространялся не только на продуцирование  новых идей, но и на их реализацию, вплоть до создания работающих согласно этим идеям устройств. К сожалению, нельзя сказать, что эти редкие качества обеспечили ему условия для полноценной и успешной работы, которая адекватно была бы востребована обществом. Его биография ясно иллюстрирует это печальное явление. Но в нашей памяти Григорий Самуилович останется как удивительный ученый, сумевший воплотить в жизнь хотя бы часть своего универсума, и замечательный добрый человек, с которым нам довелось встретиться. 

Более полный список работ Г.С. Цейтина можно найти на сайте Санкт-Петербургского математического общества: http://www.mathsoc.spb.ru/pers/tseytin/bib.html.

Список цитированных работ Г. С. Цейтина
1.	Г. С. Цейтин, “Относительно проблемы распознавания свойств ассоциативных исчислений”, Докл. АН СССР, 107:2 (1956), 209–212
2.	Г. С. Цейтин, “Ассоциативное исчисление с неразрешимой проблемой эквивалентности”, Докл. АН СССР, 107:3 (1956), 370–371
3.	Г. С. Цейтин, “О сложности вывода в исчислении высказываний”, Исследования по конструктивной математике и математической логике. II, Зап. науч. сем. ЛОМИ, 8, Изд-во “Наука”, Ленинград. отд., Л., 1968,  234–259      ; англ. пер.: G. S. Tseitin, “On the complexity of derivation in propositional calculus”, Semin. Math., 8, V. A. Steklov Math. Inst., Leningrad, 1970, 115–125; Automation of reasoning, v. 2, Classical papers on computational logic, 1967–1970, Springer-Verlag, Berlin–New York, 1983, 466–483
4.	Г. С. Цейтин, Исследования по конструктивному анализу (конструктивные вещественные числа и точечно-определенные функции), Автореф. дисс. … докт. физ.-матем. наук, ЛГУ, Л., 1968
5.	Г. С. Цейтин, “Приведенная форма нормальных алгорифмов и теорема о линейном ускорении”, Исследования по конструктивной математике и математической логике. IV, Зап. науч. сем. ЛОМИ, 20, Изд-во “Наука”, Ленинград. отд., Л., 1971,  234–242      ; англ. пер.: G. S. Tseitin, “Reduced form of normal algorithms and a linear acceleration theorem”, J. Soviet Math., 1:1 (1973), 148–153
6.	Г. С. Цейтин, “Нижняя оценка числа шагов для обращающего нормального алгорифма и других аналогичных алгорифмов”, Исследования по конструктивной математике и математической логике. IV, Зап. науч. сем. ЛОМИ, 20, Изд-во “Наука”, Ленинград. отд., Л., 1971, 243–262      ; англ. пер.: G. S. Tseitin, “Lower estimate of the number of steps for an inverting normal algorithm and other similar algorithms”, J. Soviet Math., 1:1 (1973), 154–168
7.	Г. С. Цейтин (ред.), Алгол 68: методы реализации, Изд-во Ленингр. ун-та, Л., 1976, 224 с.
8.	Г. С. Цейтин, “От логицизма к процедурализму. На автобиографическом материале”, Алгоритмы в современной математике и ее приложениях, Ч. 2, ВЦ СОАН, Новосибирск, 1982, 181–193; пер. с англ.: G. S. Tseytin, “From logicism to proceduralism (an autobiographical account)”, Algorithms in modern mathematics and computer science (Urgench, 1979), Lecture Notes in Comput. Sci., 122, Springer, Berlin–New York, 1981, 390–396
9.	Г. С. Цейтин, “Является ли математика частью информатики?”, Компьютерные инструменты в образовании, 1999, №  5, 3–7
10.	G. Tseytin, M. Hofmann, M. O'Mahony, D. Lyons, “Tracing individual public transport customers from an anonymous transaction database”, J. Public Transp., 9:4 (2006), 47–60

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

\RBibitem{ArtBekBor23}
\by С.~Н.~Артемов, Л.~Д.~Беклемишев, Л.~Я.~Боркин, А.~М.~Вершик, Э.~А.~Гирш, Е.~Я.~Данцин, И.~А.~Ибрагимов, Е.~В.~Кальменс, В.~Я.~Крейнович, Д.~А.~Кубенский, А.~А.~Лодкин, Ю.~В.~Матиясевич, Б.~А.~Новиков, В.~П.~Оревков, А.~Л.~Семенов, А.~О.~Слисенко, А.~Х.~Шень
\paper Григорий Самуилович Цейтин (некролог)
\jour УМН
\yr 2023
\vol 78
\issue 3(471)
\pages 170--176
\mathnet{http://mi.mathnet.ru/rm10092}
\crossref{https://doi.org/10.4213/rm10092}
\mathscinet{http://mathscinet.ams.org/mathscinet-getitem?mr=4673248}
\adsnasa{https://adsabs.harvard.edu/cgi-bin/bib_query?2023RuMaS..78..555A}
\transl
\jour Russian Math. Surveys
\yr 2023
\vol 78
\issue 3
\pages 555--561
\crossref{https://doi.org/10.4213/rm10092e}
\isi{https://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=Publons&SrcAuth=Publons_CEL&DestLinkType=FullRecord&DestApp=WOS_CPL&KeyUT=001146055900005}