S. N. Artemov, L. D. Beklemishev, L. Ya. Borkin, A. M. Vershik, E. A. Hirsch, E. Ya. Dantsin, I. A. Ibragimov, E. V. Kalmens, V. Ya. Kreinovich, D. A. Koubenski, A. A. Lodkin, Yu. V. Matiyasevich, B. A. Novikov, V. P. Orevkov, A. L. Semenov, A. O. Slissenko, A. Kh. Shen, “Gregory Samuilovich Tseytin (obituary)”, Russian Math. Surveys, 78:3 (2023), 555

On 27 August, 2022, Gregory Samuilovich Tseytin, an outstanding Russian and American scientist in the field of mathematical logic and theoretical computer science, passed away.

Tseytin was born in Leningrad, USSR on 15 November, 1936. His mother Bella L’vovna Sapozhnikova was an economist engineer and his father Samuil Bentsionovich Tseytin was a teacher of mathematics. Both parents originated from Belarus, from large Jewish families. During the war, mother and son were evacuated to the Kirov Oblast’.

Gregory showed extraordinary abilities from his childhood years. In 1945, the eight-year-old Gregory entered the fifth grade of a secondary school. A special commission, consisting of the renowned university professors G. M. Fikhtenholz, V. A. Tartakowsky and D. K. Faddeev concluded that “Gregory’s development in the field of mathematics goes far beyond any norms. He is fluent in the material taught in high school…”. At the age of 9, Gregory won the first prize in high school competitions in mathematics and physics.

At school, Tseytin showed great interest in languages and was excellent in ice skating. At the age of 14 he graduated from the secondary school with a gold medal. Due to his age, he was not admitted to Leningrad State University. During the following year he attended the Faculty of Mathematics and Mechanics as a student at large. In September 1952, with the permission of the Ministry of Education, he was admitted as a second-year student; the personal participation of the rector A. D. Alexandrov played a role in this decision.

During his first years at the university, Gregory slowly got used to the student environment. On the one hand he was significantly younger than his fellow students, and on the other hand he knew much more than senior students. All this, together with the peculiarities of his upbringing (Gregory’s mother accompanied him to the university and waited for him there until the classes were over), made it difficult for him to socialize with his classmates. Gregory was always strict in adherence to formal rules in speech and actions. Those around him were pleasantly surprised by his youthful innocence and his thirst for contacts. Very soon he fully acclimatized. He began to show exceptional activity in his senior years — he participated in student activities, not limited to mathematics. He was active in the student scientific society, began publishing a student mathematical journal, took part in organizing an English club, published the first rotaprint collection of student and tourist songs, and worked in the virgin lands with student construction teams. In 1960 he was among the organizers and teachers of the Youth Mathematical School.

In his second year, Tseytin started taking A. A. Markov Jr’s five-part special course in the theory of algorithms, and he understood that he had found his teacher. Indeed, mathematical logic, like no other area of mathematics, suited his way of thinking. His first mathematical work “On the number of steps in an algorithm” was completed by the end of the second year. Probably, this student result became part of the paper [5]. Tseytin’s another student paper “Associative calculi with undecidable equivalence problems” contained the most important and topical results and was published in Doklady Akademii Nauk SSSR [1], [2].

A few words should be said about the history of this work. In 1947, Markov and an E. Post independently established the algorithmic unsolvability of the identity problem for finitely presented semigroups. This problem was formulated by A. Thue in 1914, long before the exact concept of an algorithm was introduced. Markov pointed out an unsolvable Thue system given by 33 relations in an alphabet of 13 generators. Tseytin constructed the following radically simpler example of a Thue system with an unsolvable identity problem with 5 generators and 7 relations:

$$ \begin{equation*} \begin{gathered} \, ac \leftrightarrow ca;\quad ad \leftrightarrow da; \\ bc \leftrightarrow cb;\quad bd \leftrightarrow db; \\ ce \leftrightarrow eca;\quad de \leftrightarrow edb; \\ cca \leftrightarrow ccae. \end{gathered} \end{equation*} \notag $$

One of the ideas that allowed Tseytin to construct such a simple example was to use a group with an unsolvable identity problem, existence of which had been established shortly before by P. S. Novikov. For more than a decade, Tseytin’s example remained the simplest example of an undecidable associative calculus. Subsequently, Tseytin’s ideas were used by other mathematicians to construct compact universal (with respect to embedding) Thue systems and simple examples of unsolvable Thue semisystems, which were more interesting for computer science.

In 1956 Tseytin received his master degree in mathematics and entered the postgraduate course with Markov as his scientific advisor. For some time he dealt with problems in constructive mathematics developed by the Markov–Shanin school. Tseytin’s significant achievement was the proof of the non-existence of a constructive real function defined on a closed interval that takes values of different signs at its endpoints and does not have a constructive root on this interval. On the other hand he also proved that there is no algorithm that, given any constructive function with the same property, produces a constructive root on this interval. Tseytin’s remarkable discovery was the first non-trivial (and unexpected) positive result in this area (the continuity theorem), which consisted in the fact that any constructive mapping of a constructive complete separable metric space into another constructive metric space is continuous (in constructive mathematics, continuity implies the existence of an algorithm that finds $\delta$ from $\varepsilon$). This remarkable theorem was a fundamental strengthening of Markov’s earlier result on the absence of constructive discontinuities in constructive functions.

In 1959 Tseytin started as a junior researcher in the Research Institute for Mathematics and Mechanics at Leningrad State University. In 1960 he defended his Ph.D. thesis “Algorithmic operators in constructive complete separable metric spaces”. His official opponents were V. A. Uspensky and N. A. Shanin. For several years he continued to study constructive mathematics. Based on new results, partly obtained together with I. D. Zaslavsky, in 1968 Tseytin defended his D.Sc. thesis [4]. His official opponents were Markov, B. A. Trakhtenbrot, and Shanin. In that work Tseytin summed up his research in the field of constructive mathematics, and never returned to this subject.

Tseytlin’s another major research topic was computational complexity theory. He was a pioneer in the analysis of lower bounds for the time complexity of algorithms and the lengths of proofs for propositional formulae. Back in 1957 he proved the lower bound $n^2 \log^{-2}n$ for the time complexity of inverting a word by means of Markov’s normal algorithms. Earlier, in 1954 Tseytin proved [5] that a Turing machine in which it is allowed to cut and paste cells can be used as a computational model. Subsequenly, in 1969, with the help of a very ingenious construction, Tseytin obtained the exact lower bound $c\cdot n^2$, where the constant $c$ is determined by the algorithm [6]. Note that this computational model is stronger than the original Turing machine.

There are three concepts introduced by Tseytin that are permanently used in the theory of proof complexity. The first concept is Tseytin’s extension rule, which allows one to introduce new variables and use them to denote arbitrary formulae. This rule makes even a rather weak system – the resolution method – so strong that we still cannot prove exponential lower bounds for the resulting system, and do not even have good candidates for complex formulae. The second concept is Tseytin’s formulae (also known as Tseitin’s tautologies): these are systems of linear equations over a finite field, constructed in accordance with a graph. These are formulae for which a superpolynomial lower bound for the complexity of propositional proofs was proved for the first time in complexity theory. Namely, this was Tseytin’s estimate for the method of regular resolutions. This work [3] had a great influence on further studies of the complexity of propositional proofs and became one of the most cited works of the Russian school in the field of mathematical logic and algorithm theory. The third concept is Tseytin’s translation of Boolean schemata into propositional formulae, which has become a standard technique in computational complexity theory.

After defending his D.Sc. thesis, Tseytin’s interests finally switched to the field of computer science, and he quickly became the informal leader of the Leningrad programming school. In particular, he noted that the main difference between computer science and mathematics, even though the same objects were considered, was the crucial role of the human factor in computer science [9]. He was fascinated by the new field of activity, which combined rigorous mathematical methods with social aspects, due to the collective nature of software creation and the need to adapt the product to the perception of people, the problem of program protections, and so on. At that time Tseytin admitted to his colleagues that he no longer considered himself a mathematician.

Tseytin taught numerous courses. A notable example was his multi-part course on the theory of algorithms and recursive functions, which was taught over five semesters. His manner of teaching was by far non-standard. He explained all the ideas, tricks, and algorithms, but the main emphasis in his lectures was on complex open problems. He encouraged listeners to ask non-trivial questions, to come up with new problems and new ideas, which he valued more than a simple reproduction of the class material. In order to come up with new ideas, students had to put in a lot of effort, and many students commented that they learned more from Tseytin’s lectures than from other professors who taught them.

- Whatever Tseytin did, be it programming or stove repair, he did it better than others.

- Tseytin’s talks at department meetings were always a celebration of thought.

Inspired by Noam Chomsky’s pioneering research in formal grammars published in the late 1950s, Tseytin became interested in machine processing of texts in natural languages. One facet of this problem was automatic translation from one language to another. Subsequently, other problems emerged that required a deep understanding of the mechanisms underlying natural languages and their description in a form suitable for computer applications. In the 1960s, Tseytin headed a new research group at Leningrad University, whose goal was to create experimental systems in this area. This group subsequently became the Laboratory of Mathematical Linguistics, and then changed its name to the Laboratory of Intelligent Systems. At that time, many renowned scientists tried to automate translation from any language to any other. To Tseytin, an avid polyglot and an Esperanto enthusiast, this idea was especially close. Over years, he developed a programming framework based on semantic networks that combined methods of linguistics, formal logic, and system programming. Automatic translation built on semantic networks has never competed with modern translation tools based on statistical methods, but Tseytin’s methods were capable of extracting the meaning of a text and rendering it in applicable areas, such as understanding of natural language, synthesis of computer programs, and artificial intelligence. The computer scientists working with Tseytin achieved practical results that were quite advanced even by today’s standards, except they did it in the 1980s-90s, using the computers available at that time.

It was typical of Tseytin to reevaluate his research priorities based on the new results and ideas. In the late 1960s, inspired by the new trends in the theory of algorithmic languages, he focused his research on this field and away from mathematical logic. His later (1981) report of this transition [8] contains very insightful observations about the problems of language processing and artificial intelligence that are still relevant today.

Also at the same time and influenced by the same ideas, a strong group of computer scientists was formed at the Department of Computer Science and the Research Institute of Mathematics and Mechanics, who were engaged in the development of compilers for various programming languages. Tseytin was especially interested in Algol-68, a language with a very rich syntax, whose implementation presented a serious scientific challenge. Suffice it to say that only two complete compilers of this language have ever been implemented. Tseytin headed the project at the initial stage, developed the basic ideas, and in 1968 joined international cooperation on the development and implementation of this language [7]. S. S. Lavrov, an eminent authority in mathematical logic and computer science, wrote that it was under the influence of this remarkable work that the Leningrad school of programming was born and developed. He also noted that even if Algol-68 had not found any application, the emergence of the Tseytin programming school alone would have been an excellent justification of its existence.

The times were changing, and Tseytin began to work with foreign research and development companies, who also built commercial software. In 1990–1995, Tseytin worked with a group on making changes to the MS DOS operating system and building a text database. Next, in 1995–1996, he worked with the Italian company Microstar Software Ltd. At the same time Tseytin did not see St. Petersburg University as the place where he could continue to work at full strength and enjoy the same academic freedom.

In 1997, at the invitation of IBM, Tseytin spent several months at their Almaden Research Center in California, doing research in phenomenal data mining. In the spring of 1999 he continued this work in Ireland, at Trinity College Dublin (for this work, see [10], where he also taught a class in data mining.

Later in 1999 Tseytin received an invitation to the United States to participate in a natural language processing project at the University of New Mexico. This project only lasted one year, after which Tseytin decided to stay in the USA for good. With the support of prominent experts from different countries, he applied for permanent residency status under the Extraordinary Ability category. One person who wrote a recommendation letter was a Stanford University professor John McCarthy, an outstanding expert in the field of mathematical logic, computer science and the author of the concept of artificial intelligence. He was very familiar with Tseytin ’s research, highly valued his work, and facilitated his visit in 1997. He significantly helped Tseytin in the first years of his life and work in the USA. In 2002, Tseytin received the status of a permanent US resident. He became an American citizen in 2008.

In 2000 Tseytin moved to the San Jose, CA area. He first worked at Rational Software Co. until 2009. During this period he received four patents. After that, Tseytin worked for four years in Stanford University, where he was building a system of automatic learning for schoolchildren in the project of the famous American philosopher and logician Patrick Suppes. Unfortunately, during all his years in the US, Tseytin did not quite succeed in finding an adequate application for his extraordinary capabilities.

Throughout his life, Tseytin was very active in the scientific community. He was a member of the Leningrad (later St. Petersburg) Mathematical Society almost from the time of its resumption in 1959, and made many presentations at its meetings. Starting in 1989, he became deeply involved in the work of the St. Petersburg Union of Scientists (SPbSU), serving as a member of its coordinating council. After his departure, SPbSU instructed Tseytin to be the union’s representative in the United States.

Tseytin was a member of the Association for Computing Machinery (ACM). In 2006, ACM awarded him the honorary title of Distinguished Scientist. He was also a member of the American Logic Programming Association.

The love for the Esperanto language, which he learned in his youth, led him to work in the St. Petersburg Esperanto organization. After moving to the USA, he continued to promote the language and in 2017–2020 served as a secretary of the regional Esperanto organization in San Francisco.

Tseytin had a huge and rare gift. People around him admired his mathematical talent, which was realized in many of his remarkable works. His achievements have been universally recognized by the scientific community. Yet any sense of superiority was completely foreign to him. People were often surprised with his genuine kindness and sincere willingness to help colleagues in any work. His talent was not only in the generation of new ideas, but also in his perseverance in completing their implementation. It is challenging to match rare abilities with suitable professional opportunities, and unfortunately, there are times when some gifts have no currency. Tseytin had periods when his abilities were not in demand, or economic conditions impeded his professional progress. We will remember this amazing scientist and a wonderful and generous person, who, despite formidable obstacles, managed to bring to life so many of his ideas.

Citation: S. N. Artemov, L. D. Beklemishev, L. Ya. Borkin, A. M. Vershik, E. A. Hirsch, E. Ya. Dantsin, I. A. Ibragimov, E. V. Kalmens, V. Ya. Kreinovich, D. A. Koubenski, A. A. Lodkin, Yu. V. Matiyasevich, B. A. Novikov, V. P. Orevkov, A. L. Semenov, A. O. Slissenko, A. Kh. Shen, “Gregory Samuilovich Tseytin (obituary)”, Russian Math. Surveys, 78:3 (2023), 555–561

Citation in format AMSBIB

\Bibitem{ArtBekBor23}

\by S.~N.~Artemov, L.~D.~Beklemishev, L.~Ya.~Borkin, A.~M.~Vershik, E.~A.~Hirsch, E.~Ya.~Dantsin, I.~A.~Ibragimov, E.~V.~Kalmens, V.~Ya.~Kreinovich, D.~A.~Koubenski, A.~A.~Lodkin, Yu.~V.~Matiyasevich, B.~A.~Novikov, V.~P.~Orevkov, A.~L.~Semenov, A.~O.~Slissenko, A.~Kh.~Shen

\paper Gregory Samuilovich Tseytin (obituary)

\jour Russian Math. Surveys

\yr 2023

\vol 78

\issue 3

\pages 555--561

\mathnet{http://mi.mathnet.ru//eng/rm10092}

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

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

\adsnasa{https://adsabs.harvard.edu/cgi-bin/bib_query?2023RuMaS..78..555A}

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

List of cited publications of G. S. Tseytin