In Memoriam: Boris Trakhtenbrot, 1921-2016

Boris (Boaz) Avraamovich Trakhtenbrot, an Israeli and Russian mathematician who worked in the areas of mathematical logic, algorithms, theory of computation and cybernetics, passed away Sept. 19 at the age of 95.

Trakhtenbrot was born Feb. 20, 1921 in Bricheva, a village in Northern Bessarabia (now known as Moldova).  He attended high school in the neighboring towns of Belts and Soroka, and in 1940 enrolled in the Faculty of Physics and Mathematics of the Moldovian Pedagogical Institute in Kishinev. After than city was bombed at the outset of World War II in June 1941, he relocated to Chkalov (now Orenburg), and enrolled in the local pedagogical institute. In 1942, he and his family move to Buguruslan, but his studies were often interrupted during the war years.

In 1945, having passed the exams to qualify to teach high school math, Trakhtenbrot enrolled in the University of Chernovsty (Ukraine) to pursue the equivalent of a master’s degree, which he received in 1947. He spent the next three years studying mathematical logic and computability at the Kiev Mathematics Institute of the Ukrainian Academy of Sciences, where he received his Ph.D. in 1950. He also received a (Soviet) Doctor of Sciences degree in 1962.

From 1950 to 1960, Trakhtenbrot held positions at the Pedagogical and Polytechnic Institutes of Penza, Russia.

From 1960 to 1980, he conducted research at the Mathematical Institute of the USSR Academy of Sciences’ Siberian branch, and lectured at Novosibirsk State University in Akademgorodok, Novosibirsk. He joined Novosibirsk’s Department of Theoretical Cybernetics when it was launched in 1961, and worked there with J.M. Barzdin on the basic concepts of computational complexity.

After immigrating to Israel in 1981, he became a professor of computer science at Tel Aviv University. In the years before his retirement in 1991, he also visited and collaborated with many Western universities and research centers.

In 1964, Trakhtenbrot discovered and proved a fundamental result in theoretical computer science called the Gap theorem, regarding the complexity of computable functions.He also discovered and proved what is now called Trakhtenbrot’s theorem, which states the problem of validity in first-order logic (FO) on the class of all finite models is undecidable, and that the class of valid sentences over finite models is not recursively enumerable (though it is co-recursively enumerable). The theorem was first published in 1950, in the paper "The Impossibility of an Algorithm for the Decidability Problem on Finite Classes."

In 2011, the European Association for Theoretical Computer Science (EATCS) awarded Trakhtenbrot, then about to turn 90, its annual Distinguished Achievements Award. The organization described him as "unquestionably a principal founding father of the discipline of computer science, a preeminent distinguished researcher, and a most illustrious leader and disseminator," as well as "a grand visionary who pioneered many fascinating directions and concepts, which have had enormous impact."

Further, the organization said, "for over half a century, Trakhtenbrot has been making seminal contributions to virtually all of the central aspects of theoretical computer science, inaugurating numerous brand-new areas of investigation. The list of topics in which Trakhtenbrot has made his lasting mark is breathtaking in its scope: decidability problems in logic and schematology of programs, finite automata theory, the connection between infinite automata and monadic second-order logic, complexity of algorithms, abstract complexity, algorithmic logic, probabilistic computation, program verification, the lambda calculus and foundations of programming languages, programming semantics, and much more. The entire body of his work demonstrates the same unique melding of supreme mathematical prowess, combined with profound depth and thoroughness. His operative style has always been patient in-depth survey of existing literature, uncompromising evaluation and critical comparison of existing approaches, followed by extraordinary and prescient contributions.

"…Trankhtenbrot’s contributions are astounding under any measure; his undaunted spirit should be heralded as an inspiration to the rest of the world."

Trakhtenbrot published about 100 papers and four books:

• Introduction to the Theory of Finite Automata (co-authored with N.E. Kobrinski);
• Algorithms and Automatic Computing Machines;
• Complexity of Algorithms and Computations, and
• Finite Automata: Behavior and Synthesis (co-authored with J.M. Barzdin).

He married Berta I. Rabinovich in 1947; she passed away in 2013. They had two sons, Mark (who was part of a team that received the ACM Software System Award for 2007) and Yossef, and five grandchildren.

Lawrence M. Fisher is Senior Editor/News for ACM Magazines.